Continuous visible nearest neighbor queries

ABSTRACT

In this paper, we identify and solve a new type of spatial queries, called continuous visible nearest neighbor (CVNN) search. Given a data set P, an obstacle set O, and a query line segment q, a CVNN query returns a set of (p, R) tuples such that p ε P is the nearest neighbor (NN) to every point r along the interval R ε q as well as p is visible to r. Note that p may be NULL, meaning that all points in P are invisible to all points in R, due to the obstruction of some obstacles in O. In this paper, we formulate the problem and propose efficient algorithms for CVNN query processing, assuming that both P and O are indexed by R-trees. In addition, we extend our techniques to several variations of the CVNN query. Extensive experiments verify the efficiency and effectiveness of our proposed algorithms using both real and synthetic datasets.

REFERENCES

• 1: T. Asano, S. K. Ghosh, and T. C. Shermer. Visibility in the plane. In Handbook of Computation Geometry. Elsevier, 2000.
• 2: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: King Lum Cheung , Ada Wai-Chee Fu, Enhanced nearest neighbour search on the R-tree, ACM SIGMOD Record, v.27 n.3, p.16-21, Sept. 1, 1998 [doi>10.1145/290593.290596]
• 4: Ke Deng , Heng Tao Shen , Kai Xu , Xuemin Lin, Surface k-NN Query Processing, Proceedings of the 22nd International Conference on Data Engineering, p.78, April 03-07, 2006 [doi>10.1109/ICDE.2006.152]
• 5: Vladimir Estivill-Castro , Ickjai Lee, AUTOCLUST+: Automatic Clustering of Point-Data Sets in the Presence of Obstacles, Proceedings of the First International Workshop on Temporal, Spatial, and Spatio-Temporal Data Mining-Revised Papers, p.133-146, September 12, 2000
• 6: Hakan Ferhatosmanoglu , Ioana Stanoi , Divyakant Agrawal , Amr El Abbadi, Constrained Nearest Neighbor Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.257-278, July 12-15, 2001
• 7: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 8: 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]
• 9: Haibo Hu , Dik Lun Lee, Range Nearest-Neighbor Query, IEEE Transactions on Knowledge and Data Engineering, v.18 n.1, p.78-91, January 2006 [doi>10.1109/TKDE.2006.15]
• 10: M. Kofler, M. Gervautz, and M. Gruber. R-trees for organizing and visualizing 3D GIS databases. Journal of Visualization and Computer Animation, 11(3):129--143, 2000.
• 11: F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng. On trip planning queries in spatial databases. In SSTD, 2005.
• 12: Kyriakos Mouratidis , Dimitris Papadias , Marios Hadjieleftheriou, Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066230]
• 13: Kyriakos Mouratidis , Dimitris Papadias , Spiridon Bakiras , Yufei Tao, A Threshold-Based Algorithm for Continuous Monitoring of k Nearest Neighbors, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1451-1464, November 2005 [doi>10.1109/TKDE.2005.172]
• 14: Kyriakos Mouratidis , Man Lung Yiu , Dimitris Papadias , Nikos Mamoulis, Continuous nearest neighbor monitoring in road networks, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 15: S. Nutanong, E. Tanin, and R. Zhang. Visible nearest neighbor queries. In DASFAA, 2007.
• 16: Dimitris Papadias , Qiongmao Shen , Yufei Tao , Kyriakos Mouratidis, Group Nearest Neighbor Queries, Proceedings of the 20th International Conference on Data Engineering, p.301, March 30-April 02, 2004
• 17: Dimitris Papadias , Yufei Tao , Kyriakos Mouratidis , Chun Kit Hui, Aggregate nearest neighbor queries in spatial databases, ACM Transactions on Database Systems (TODS), v.30 n.2, p.529-576, June 2005 [doi>10.1145/1071610.1071616]
• 18: Apostolos Papadopoulos , Yannis Manolopoulos, Performance of Nearest Neighbor Queries in R-Trees, Proceedings of the 6th International Conference on Database Theory, p.394-408, January 08-10, 1997
• 19: 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
• 20: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 21: Lidan Shou , Jason Chionh , Zhiyong Huang , Yixin Ruan , Kian-Lee Tan, Walking Through a Very Large Virtual Environment in Real-time, Proceedings of the 27th International Conference on Very Large Data Bases, p.401-410, September 11-14, 2001
• 22: L. Shou, Z. Huang, and K. L. Tan. HDoV-tree: The structure, the storage, the speed. In ICDE, 2003.
• 23: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 24: Zhexuan Song , Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.79-96, July 12-15, 2001
• 25: Yufei Tao , Dimitris Papadias, Time-parameterized queries in spatio-temporal databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564730]
• 26: Yufei Tao , Dimitris Papadias , Xiang Lian, Reverse kNN search in arbitrary dimensionality, Proceedings of the Thirtieth international conference on Very large data bases, p.744-755, August 31-September 03, 2004, Toronto, Canada
• 27: Yufei Tao , Dimitris Papadias , Qiongmao Shen, Continuous nearest neighbor search, Proceedings of the 28th international conference on Very Large Data Bases, p.287-298, August 20-23, 2002, Hong Kong, China
• 28: Anthony K. H. Tung , Jean Hou , Jiawei Han, Spatial Clustering in the Presence of Obstacles, Proceedings of the 17th International Conference on Data Engineering, p.359-367, April 02-06, 2001
• 29: Xiaopeng Xiong , Mohamed F. Mokbel , Walid G. Aref, SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases, Proceedings of the 21st International Conference on Data Engineering, p.643-654, April 05-08, 2005 [doi>10.1109/ICDE.2005.128]
• 30: Xiaohui Yu , Ken Q. Pu , Nick Koudas, Monitoring k-Nearest Neighbor Queries over Moving Objects, Proceedings of the 21st International Conference on Data Engineering, p.631-642, April 05-08, 2005 [doi>10.1109/ICDE.2005.92]
• 31: Osmar R. Zaïane , Chi-Hoon Lee, Clustering Spatial Data in the Presence of Obstacles: a Density-Based Approach, Proceedings of the 2002 International Symposium on Database Engineering & Applications, p.214-223, July 17-19, 2002
• 32: Jun Zhang , Nikos Mamoulis , Dimitris Papadias , Yufei Tao, All-Nearest-Neighbors Queries in Spatial Databases, Proceedings of the 16th International Conference on Scientific and Statistical Database Management, p.297, June 21-23, 2004 [doi>10.1109/SSDBM.2004.12]
• 33: J. Zhang, D. Papadias, K. Mouratidis, and M. Zhu. Spatial queries in the presence of obstacles. In EDBT, 2004.