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

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

References

[1] Roussopoulos N, Kelley S, Vincent F. Nearest neighbor queries. ACM SIGMOD Record, 1995, 24(2): 71–79

[2] Seidl T, Kriegel H. Optimal multi-step k-nearest neighbor search. ACM SIGMOD Record, 1998, 27(2): 154–165

[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

[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

[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’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’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

[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

[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

[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

[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

[22] Okabe A, Boots B, Sugihara K, Chiu S N. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley, 2000

[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

[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’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

[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

[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

[32] Brinkhoff T. A framework for generating network-based moving objects. GeoInformatica, 2002, 6(2): 153-180

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg