Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In this paper, we study a novel form of continuous nearest neighbor queries in the presence of obstacles, namely continuous obstructed nearest neighbor (CONN) search. It considers the impact of obstacles on the distance between objects, which is ignored by most of spatial queries. Given a data set P, an obstacle set O, and a query line segment q in a two-dimensional space, a CONN query retrieves the nearest neighbor of each point on q according to the obstructed distance, i.e., the shortest path between them without crossing any obstacle. We formulate CONN search, analyze its unique properties, and develop algorithms for exact CONN query processing, assuming that both P and O are indexed by conventional data-partitioning indices (e.g., R-trees). Our methods tackle the CONN retrieval by performing a single query for the entire query segment, and only process the data points and obstacles relevant to the final result, via a novel concept of control points and an efficient quadratic-based split point computation algorithm. In addition, we extend our solution to handle the continuous obstructed k-nearest neighbor (COkNN) search, which finds the k (≥1)nearest neighbors to every point along q based on obstructed distances. A comprehensive experimental evaluation using both real and synthetic datasets has been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms.

REFERENCES

• 1: 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 [doi>10.1145/93597.98741]
• 2: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 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: Hyung-Ju Cho , Chin-Wan Chung, An efficient and scalable approach to CNN queries in a road network, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 5: E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
• 6: 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
• 7: J. Feng and T. Watanabe. A fast method for continuous nearest target objects query on road network. In VSMM, pages 182--191, 2002.
• 8: Yunjun Gao , Baihua Zheng , Gencai Chen , Wang-Chien Lee , Ken C. K. Lee , Qing Li, Visible Reverse k-Nearest Neighbor Queries, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1203-1206, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.201]
• 9: Yunjun Gao , Baihua Zheng , Wang-Chien Lee , Gencai Chen, Continuous visible nearest neighbor queries, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia [doi>10.1145/1516360.1516378]
• 10: Subir Kumar Ghosh , David M. Mount, An output sensitive algorithm for computing visibility graphs, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, p.11-19, October 12-14, 1987 [doi>10.1109/SFCS.1987.6]
• 11: 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 [doi>10.1145/602259.602266]
• 12: A. Henrich. A distance-scan algorithm for spatial access structures. In GIS, pages 136--143, 1994.
• 13: 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]
• 14: Mohammad R. Kolahdouzan , Cyrus Shahabi, Alternative Solutions for Continuous K Nearest Neighbor Queries in Spatial Network Databases, Geoinformatica, v.9 n.4, p.321-341, December 2005 [doi>10.1007/s10707-005-4575-8]
• 15: S. Nutanong, E. Tanin, and R. Zhang. Visible nearest neighbor queries. In DASFAA, pages 876--883, 2007.
• 16: 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
• 17: S. H. Park, J.-H. Lee, and D.-H. Kim. Spatial clustering based on moving distance in the presence of obstacles. In DASFAA, pages 1024--1027, 2007.
• 18: 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 [doi>10.1145/223784.223794]
• 19: 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
• 20: Micha Sharir , Amir Schorr, On shortest paths in polyhedral spaces, SIAM Journal on Computing, v.15 n.1, p.193-215, Feb. 1986 [doi>10.1137/0215014]
• 21: 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
• 22: 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
• 23: 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]
• 24: 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
• 25: 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
• 26: Anthony K. H. Tung , Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han, Constraint-based clustering in large databases, Proceedings of the 8th International Conference on Database Theory, p.405-419, January 04-06, 2001
• 27: X. Wang and H. J. Hamilton. Clustering spatial data in the presence of obstacles. International Journal on Artificial Intelligence Tools, 14(1--2):177--198, 2005.
• 28: Xin Wang , Camilo Rostoker , Howard J. Hamilton, Density-based spatial clustering in the presence of obstacles and facilitators, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.446-458, September 20-24, 2004, Pisa, Italy
• 29: C. Xia, D. Hsu, and A. K. H. Tung. A fast filter for obstructed nearest neighbor queries. In BNCOD, pages 203--215, 2004.
• 30: 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
• 31: J. Zhang, D. Papadias, K. Mouratidis, and M. Zhu. Spatial queries in the presence of obstacles. In EDBT, pages 366--384, 2004.
• 32: Baihua Zheng , Wang-Chien Lee , Dik Lun Lee, On Searching Continuous k Nearest Neighbors in Wireless Data Broadcast Systems, IEEE Transactions on Mobile Computing, v.6 n.7, p.748-761, July 2007 [doi>10.1109/TMC.2007.1004]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
continuous nearest neighbor, continuous obstructed nearest neighbor, nearest neighbor, obstacle, spatial database