Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring

ABSTRACT

Given a set of objects P and a query point q, a k nearest neighbor (k-NN) query retrieves the k objects in P that lie closest to q. Even though the problem is well-studied for static datasets, the traditional methods do not extend to highly dynamic environments where multiple continuous queries require real-time results, and both objects and queries receive frequent location updates. In this paper we propose conceptual partitioning (CPM), a comprehensive technique for the efficient monitoring of continuous NN queries. CPM achieves low running time by handling location updates only from objects that fall in the vicinity of some query (and ignoring the rest). It can be used with multiple, static or moving queries, and it does not make any assumptions about the object moving patterns. We analyze the performance of CPM and show that it outperforms the current state-of-the-art algorithms for all problem settings. Finally, we extend our framework to aggregate NN (ANN) queries, which monitor the data objects that minimize the aggregate distance with respect to a set of query points (e.g., the objects with the minimum sum of distances to all query points).

REFERENCES

• 1: Thomas Brinkhoff, A Framework for Generating Network-Based Moving Objects, Geoinformatica, v.6 n.2, p.153-180, June 2002 [doi>10.1023/A:1015231126594]
• 2: Rimantas Benetis , Christian S. Jensen , Gytis Karciauskas , Simonas Saltenis, Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects, Proceedings of the 2002 International Symposium on Database Engineering & Applications, p.44-53, July 17-19, 2002
• 3: {CHC04} Cai, Y., Hua, K., Cao, G. Processing Range - Monitoring Queries on Heterogeneous Mobile Objects. MDM, 2004.
• 4: {FSAA01} Ferhatosmanoglu, H., Stanoi, I., Agrawal, D., Abbadi, A. Constrained Nearest Neighbor Queries. SSTD, 2001.
• 5: {GL04} Gedik, B., Liu, L. MobiEyes: Distributed Processing of Continuously Moving Queries on Moving Objects in a Mobile System. EDBT, 2004.
• 6: {H84} Henrich, A. A Distance Scan Algorithm for Spatial Access Structures. ACM GIS, 1984.
• 7: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 8: {KMS02} Korn, F., Muthukrishnan, S. Srivastava, D. Reverse Nearest Neighbor Aggregates Over Data Streams. VLDB, 2002.
• 9: {KOTZ04} Koudas, N., Ooi, B., Tan, K., Zhang, R. Approximate NN queries on Streams with Guaranteed Error/performance Bounds. VLDB, 2004.
• 10: Mohamed F. Mokbel , Xiaopeing Xiong , Walid G. Aref, SINA: scalable incremental processing of continuous queries in spatio-temporal databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007638]
• 11: {PSTM04} Papadias, D., Shen, Q., Tao, Y., Mouratidis, K. Group Nearest Neighbor Queries. ICDE, 2004.
• 12: Sunil Prabhakar , Yuni Xia , Dmitri V. Kalashnikov , Walid G. Aref , Susanne E. Hambrusch, Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects, IEEE Transactions on Computers, v.51 n.10, p.1124-1140, October 2002 [doi>10.1109/TC.2002.1039840]
• 13: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 14: {SR01} Song, Z., Roussopoulos, N. K-Nearest Neighbor Search for Moving Query Point. SSTD, 2001.
• 15: Ioana Stanoi , Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, Discovery of Influence Sets in Frequently Updated Databases, Proceedings of the 27th International Conference on Very Large Data Bases, p.99-108, September 11-14, 2001
• 16: Yufei Tao , Dimitris Papadias, Spatial queries in dynamic environments, ACM Transactions on Database Systems (TODS), v.28 n.2, p.101-139, June 2003 [doi>10.1145/777943.777944]
• 17: {XMA05} Xiong, X., Mokbel, M., Aref, W. SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases. ICDE, 2005.
• 18: {YPK05} Yu, X., Pu, K., Koudas, N. Monitoring K-Nearest Neighbor Queries Over Moving Objects. ICDE, 2005.
• 19: Jun Zhang , Manli Zhu , Dimitris Papadias , Yufei Tao , Dik Lun Lee, Location-based spatial queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872812]