VGQ-Vor: extending virtual grid quadtree with Voronoi diagram for mobile <italic>k</italic> nearest neighbor queries over mobile objects

doi:10.1007/s11704-012-2069-z

Front Comput Sci

2013, Vol. 7

Issue (1) : 44-54 https://doi.org/10.1007/s11704-012-2069-z

RESEARCH ARTICLE

VGQ-Vor: extending virtual grid quadtree with Voronoi diagram for mobile k nearest neighbor queries over mobile objects

Botao WANG¹(

), Jingwei QU¹, Xiaosong WANG¹, Guoren WANG¹, Masaru KITSUREGAWA²

1. Department of Information Science and Engineering, Northeastern University, Shenyang 110004, China; 2. Institute of Industrial Science, the University of Tokyo, Tokyo 153-8505, Japan

Download: PDF(723 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Performing mobile k nearest neighbor (MkNN) queries whilst also being mobile is a challenging problem. All the mobile objects issuing queries and/or being queried aremobile. The performance of this kind of query relies heavily on the maintenance of the current locations of the objects. The index used for mobile objects must support efficient update operations and efficient query handling. This study aims to improve the performance of the MkNN queries while reducing update costs. Our approach is based on an observation that the frequency of one region changing between being occupied or not by mobile objects is much lower than the frequency of the position changes reported by the mobile objects. We first propose an virtual grid quadtree with Voronoi diagram(VGQ-Vor), which is a two-layer index structure that indexes regions occupied by mobile objects in a quadtree and builds a Voronoi diagram of the regions. Then we propose a moving k nearest neighbor (kNN) query algorithm on the VGQ-Vor and prove the correctness of the algorithm. The experimental results show that the VGQ-Vor outperforms the existing techniques (Bx-tree, Bdual-tree) by one to three orders of magnitude in most cases.

Keywords location based services mobile k nearest neighbor query mobile object index Voronoi diagram

Corresponding Author(s): WANG Botao,Email:wangbotao@ise.neu.edu.cn

Issue Date: 01 February 2013

Cite this article:

Botao WANG,Jingwei QU,Xiaosong WANG, et al. VGQ-Vor: extending virtual grid quadtree with Voronoi diagram for mobile k nearest neighbor queries over mobile objects[J]. Front Comput Sci, 2013, 7(1): 44-54.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-012-2069-z
https://academic.hep.com.cn/fcs/EN/Y2013/V7/I1/44

1	Roussopoulos N, Kelley S, Vincent F. Nearest neighbor queries. ACM SIGMOD Record , 1995, 24(2): 71–79 doi: 10.1145/568271.223794
2	Seidl T, Kriegel H. Optimal multi-step k-nearest neighbor search. ACM SIGMOD Record , 1998, 27(2): 154–165 doi: 10.1145/276305.276319
3	Chaudhuri S, Gravano L. Evaluating top-k selection queries. In: Proceedings of the 25th International Conference on Very Large Data Bases . 1999, 397–410
4	Kalashnikov D, Prabhakar S, Hambrusch S. Main memory evaluation of monitoring queries over moving objects. Distributed and Parallel Databases , 2004, 15(2): 117-135 doi: 10.1023/B:DAPD.0000013068.25976.88
5	Cai Y, Hua K, Cao G. Processing range-monitoring queries on heterogeneous mobile objects. In: Proceedings of the 2004 IEEE International Conference on Mobile Data Management . 2004, 27-38
6	Song Z, Roussopoulos N. k-nearest neighbor search for moving query point. Advances in Spatial and Temporal Databases , 2001, 79-96
7	Tao Y, Papadias D, Shen Q. Continuous nearest neighbor search. In: Proceedings of the 28th International Conference on Very Large Data Bases . 2002, 287-298 doi: 10.1016/B978-155860869-6/50033-0
8	Kolahdouzan M, Shahabi C. Voronoi-based k nearest neighbor search for spatial network databases. In: Proceedings of the 30th International Conference on Very Large Data Bases . 2004, 840-851
9	Nutanong S, Zhang R, Tanin E, Kulik L. The v-diagram: a querydependent approach to moving knn queries. Proceedings of the VLDB Endowment* , 2008, 1(1): 1095-1106
10	Sharifzadeh M, Shahabi C. Vor-tree: R-trees with voronoi diagrams for efficient processing of spatial nearest neighbor queries. Proceedings of the VLDB Endowment , 2010, 3(1-2): 1231-1242
11	Yu X, Pu K, Koudas N. Monitoring k-nearest neighbor queries over moving objects. In: Proceedings of the 21st International Conference on Data Engineering . ICDE&rsquo;05 . 2005, 631-642
12	Xiong X, Mokbel M, Aref W. Sea-cnn: scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In: Proceedings of the 21st International Conference on Data Engineering . ICDE&rsquo;05 . 2005, 643-654
13	Mouratidis K, Yiu M, Papadias D, Mamoulis N. Continuous nearest neighbor monitoring in road networks. In: Proceedings of the 32nd International Conference on Very Large Data Bases . 2006, 43-54
14	Fan P, Li G, Yuan L, Li Y. Vague continuous k-nearest neighbor queries over moving objects with uncertain velocity in road networks. Information Systems , 2012, 37(1): 13-32 doi: 10.1016/j.is.2011.08.002
15	?altenis S, Jensen C, Leutenegger S, Lopez M. Indexing the positions of continuously moving objects. ACM SIGMOD Record , 2000, 29(2): 331-342
16	Tao Y, Papadias D, Sun J. The TPR-tree: an optimized spatiotemporal access method for predictive queries. In: Proceedings of the 29th International Conference on Very Large Data Bases* . 2003, 790-801
17	Patel J, Chen Y, Chakka V. STRIPES: an efficient index for predicted trajectories. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data . 2004, 635-646 doi: 10.1145/1007568.1007639
18	Silva Y N, Xiong X P, Aref W G. The RUM-tree: supporting frequent updates in R-trees using memos. The VLDB Journal , 2009, 18(3): 719-738 doi: 10.1007/s00778-008-0120-3
19	Jensen C, Lin D, Ooi B. Query and update efficient B⁺-tree based indexing of moving objects. In: Proceedings of the 30th International Conference on Very Large Data Bases . 2004, 768-779
20	Tao Y, Xiao X. Primal or dual: which promises faster spatiotemporal search? The VLDB Journal , 2008, 17(5): 1253-1270 doi: 10.1007/s00778-007-0064-z
21	Chen S, Ooi B, Tan K, Nascimento M. ST²B-tree: a self-tunable spatiotemporal b⁺-tree index for moving objects. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data . 2008, 29-42 doi: 10.1145/1376616.1376622
22	Okabe A, Boots B, Sugihara K, Chiu S N. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley , 2000 doi: 10.1002/9780470317013
23	Wang B, Chen H, Ma J, Kitsuregawa M, Wang G. Design and implementation of mobile object index based on covered area. Journal of Frontiers of Computer Science and Technology , 2010, 4(1): 64-72
24	Chen Z, Shen H, Zhou X, Yu J. Monitoring path nearest neighbor in road networks. In: Proceedings of the 35th SIGMOD International Conference on Management of Data . 2009, 591-602 doi: 10.1145/1559845.1559907
25	Zheng K, Trajcevski G, Zhou X, Scheuermann P. Probabilistic range queries for uncertain trajectories on road networks. In: Proceedings of the 14th International Conference on Extending Database Technology . 2011, 283-294
26	Xiong X, Aref W. R-trees with update memos. In: Proceedings of the 22nd International Conference on Data Engineering . ICDE&rsquo;06 . 2006, 22-22
27	Guttman A. R-trees: a dynamic index structure for spatial searching. Readings in Database Systems , 1988, 599-609
28	Zhang R, Jagadish H, Dai B, Ramamohanarao K. Optimized algorithms for predictive range and kNN queries on moving objects. Information Systems , 2010, 35(8): 911-932 doi: 10.1016/j.is.2010.05.004
29	Güting R, Behr T,Xu J. Efficient k-nearest neighbor search on moving object trajectories. The VLDB Journal , 2010, 19(5): 687-714 doi: 10.1007/s00778-010-0185-7
30	Chen S, Jensen C, Lin D. A benchmark for evaluating moving object indexes. Proceedings of the VLDB Endowment , 2008, 1(2): 1574-1585
31	Finkel R, Bentley J. Quad trees a data structure for retrieval on composite keys. Acta Informatica , 1974, 4(1): 1-9 doi: 10.1007/BF00288933
32	Brinkhoff T. A framework for generating network-based moving objects. GeoInformatica , 2002, 6(2): 153-180 doi: 10.1023/A:1015231126594

[1]	Quanjun YIN, Long QIN, Yong PENG, Wei DUAN. Learning real-time search on c-space GVDs[J]. Front. Comput. Sci., 2017, 11(6): 1036-1049.
[2]	Xiao PAN,Weizhang CHEN,Lei WU,Chunhui PIAO,Zhaojun HU. Protecting personalized privacy against sensitivity homogeneity attacks over road networks in mobile services[J]. Front. Comput. Sci., 2016, 10(2): 370-386.

Viewed

Full text

Abstract

Cited

Shared

Discussed