Spatial range query in wireless broadcast environment

doi:10.11772/j.issn.1001-9081.2015.06.1762

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (6): 1762-1765.DOI: 10.11772/j.issn.1001-9081.2015.06.1762

Previous Articles Next Articles

Spatial range query in wireless broadcast environment

MA Xiaoqin, PENG Xiufen, YANG Li

Department of Mathematics and Computer Science, Chizhou University, Chizhou Anhui 247000, China

Received:2015-01-07 Revised:2015-04-12 Online:2015-06-12

无线广播环境下的空间范围查询处理

马小琴, 彭秀芬, 杨利

池州学院数学与计算机科学系, 安徽池州 247000

通讯作者: 马小琴(1982-),女,安徽安庆人,讲师,硕士,主要研究方向:移动数据库、数据库;czumxq@163.com
作者简介:彭秀芬(1979-),女,安徽池州人,讲师,硕士,主要研究方向:生物网络;杨利(1980-),男,湖北武汉人,实验师,硕士,主要研究方向:无线网络。
基金资助:
安徽省优秀青年人才基金资助项目(2013SQRL096ZD);池州学院自然科学研究项目(2014ZRZ010)。

Abstract

Abstract:

In order to realize fast and energy-efficient spatial range query in wireless broadcast environment, a Range Query based on Grid Spatial Index (RQGSI) algorithm was proposed. On the server, grid spatial index was established for all data objects to shorten tuning time, and then the meshed grid was scheduled according to the Hilbert curve filling order to optimize access time. On the client, the query processing algorithm was designed for filtering and pruning the data objects. Finally, the simulation experiments verified the performance of the proposed RQGSI. The experimental results show that, compared with the R-tree Index (RI) algorithm, the RQGSI algorithm reduces tuning time by about 10%, decreases access time approximately by 8%, and it can achieve faster and lower energy consumption range query.

Key words: wireless broadcast, spatial range query, grid spatial index, tuning time, Hilbert curve, access time

摘要：

为实现无线广播环境下快速且低能耗的空间范围查询,提出了一种基于网格空间索引的范围查询处理算法(RQGSI)。该算法在服务器端对空间数据对象建立网格空间索引以缩短调谐时间,并按Hilbert曲线填充顺序对划分后的网格进行调度以优化访问时间;在客户端设计了查询处理算法对数据对象进行过滤和剪枝;最后,通过模拟实验验证了RQGSI算法的性能。实验结果表明,RQGSI算法比基于R树的索引(RI)算法在调谐时间上降低约10%,在访问时间上降低约8%,RQGSI算法可以实现更快且更低能耗的范围查询。

关键词: 无线广播, 空间范围查询, 网格空间索引, 调谐时间, Hilbert曲线, 访问时间

CLC Number:

TP311.13

MA Xiaoqin, PENG Xiufen, YANG Li. Spatial range query in wireless broadcast environment[J]. Journal of Computer Applications, 2015, 35(6): 1762-1765.

马小琴, 彭秀芬, 杨利. 无线广播环境下的空间范围查询处理[J]. 计算机应用, 2015, 35(6): 1762-1765.

References

[1] GAO Y, ZHENG B, CHEN G, et al. Continuous visible nearest neighbor query processing in spatial databases [J]. The VLDB Journal, 2011, 20(3): 371-396.
[2] HUANG Y-K, CHEN C-C, LEE C. Continuous k-nearest neighbor query for moving objects with uncertain velocity [J]. GeoInformatica, 2009, 13(1): 1-25.
[3] MOURATIDIS K, YIU M L, PAPADIAS D, et al. Continuous nearest neighbor monitoring in road networks [C]//Proceedings of the 2006 32nd International Conferences on Very Large Data Bases. New York: ACM, 2006: 43-54.
[4] HUANG Y-K, CHEN Z-W, LEE C. Continuous k-nearest neighbor query over moving objects in road network [C]//Proceedings of the 2009 Joint International Conferences on Asia-Pacific Web and Web-Age Information Management, LNCS 5446. Berlin: Springer, 2009: 27-38.
[5] ZHENG B, XU J, LEE W-C, et al. Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services [J]. The VLDB Journal, 2006, 15(1): 21-39.
[6] LI Y, LI G, ZHANG C, et al. Optimizing the nearest neighbor query processing under wireless broadcast environments [J]. Journal of Huazhong University of Science and Technology: Natural Science Edition, 2013, 41(2): 76-80.(李艳红, 李国徽, 张聪, 等.无线广播环境下最近邻查询处理的性能优化[J].华中科技大学学报:自然科学版, 2013, 41(2):76-80.)
[7] GEDIK B, SINGH A, LIU L. Energy efficient exact kNN search in wireless broadcast environments [C]//GIS'04: Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems. New York: ACM, 2004: 137-146.
[8] LIU C-M, FU S-Y. Effective protocols for kNN search on broadcast multi-dimensional index trees [J]. Information Systems, 2008, 33(1): 18- 35.
[9] PARK K, CHOO H, VALDURIEZ P. A scalable energy-efficient continuous nearest neighbor search in wireless broadcast systems [J]. Wireless Networks, 2010, 16(4): 1011-1031.
[10] ZHENG B, LEE W-C, LEE K C K, et al. A distributed spatial index for error-prone wireless data broadcast [J]. The VLDB Journal, 2009, 18(4): 959-986.
[11] YU P. Research on data broadcast scheduling and air indexing in wireless environments [D]. Shanghai: Fudan University, 2008.(余平.无线数据广播调度与索引技术研究[D].上海:复旦大学, 2008.)
[12] MOKBEL M F, AREF W G, KAMEL L. Analysis of multi-dimensional space-filling curves [J]. GeoInformatica, 2003, 7(3): 179-209.
[13] VERMA S, KUMARI S, RAKHEE, et al. Time efficient indexing technique for querying location dependent data in wireless broadcast[J].International Journal of Computer Application, 2010, 7(10): 1-6.

Spatial range query in wireless broadcast environment

无线广播环境下的空间范围查询处理

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

[1]	He-gang FU Ran LI. Collaborative filtering algorithm based on real-time user feedback [J]. Journal of Computer Applications, 2011, 31(07): 1744-1747.
[2]	. Hybrid indexing of moving objects based on BX-tree [J]. Journal of Computer Applications, 2010, 30(1): 22-24.
[3]	. Multi-node wireless broadcasting retransmission scheme based on network coding [J]. Journal of Computer Applications, 2008, 28(4): 849-852.
[4]	ZHOU Yong, HE Jian-nong, TU Ping. Technique of auto-selection multi-layers grid spatial index [J]. Journal of Computer Applications, 2005, 25(06): 1401-1404.