Abstract
Despite the ubiquity of physical obstacles (e.g., buildings, hills, and blindages, etc.) in the real world, most of spatial queries ignore the obstacles. In this article, we study a novel form of continuous nearest-neighbor queries in the presence of obstacles, namely continuous obstructed nearest-neighbor (CONN) search, which considers the impact of obstacles on the distance between objects. 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 p ∈ P of each point p′ on q according to the obstructed distance, the shortest path between p and p′ without crossing any obstacle in O. We formalize 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 CONN retrieval by performing a single query for the entire query line segment, and only process the data points and obstacles relevant to the final query result via a novel concept of control points and an efficient quadratic-based split point computation approach. Then, we extend our techniques to handle variations of CONN queries, including (1) continuous obstructed k nearest neighbor (COkNN) search which, based on obstructed distances, finds the k (≥ 1) nearest neighbors (NNs) to every point along q; and (2) trajectory obstructed k nearest-neighbor (TOkNN) search, which, according to obstructed distances, returns the k NNs for each point on an arbitrary trajectory (consisting of several consecutive line segments). Finally, we explore approximate COkNN (ACOkNN) retrieval. Extensive experiments with both real and synthetic datasets demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.
Supplemental Material
Available for Download
Supplemental movie, image and appendix files for, Continuous nearest-neighbor search in the presence of obstacles
- Beckmann, N., Kriegel, H.-P., Schneider, R., and Seeger, B. 1990. The R<sup>*</sup>-tree: An efficient and robust access method for points and rectangles. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). 322--331. Google ScholarDigital Library
- Berg, M. De, Kreveld, M. Van, Overmars, M., and Schwarzkopf, O. 2000. Computational Geometry: Algorithms and Applications 2nd Ed. Springer-Verlag. Google ScholarDigital Library
- Chen, J., Dewitt, D., Tian, F., and Wang, Y. 2000. NiagaraCQ: A scalable continuous query system for Internet databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). 379--390. Google ScholarDigital Library
- Cheung, K. L. and Fu, A. W.-C. 1998. Enhanced nearest neighbour search on the R-tree. SIGMOD Rec. 27, 3, 16--21. Google ScholarDigital Library
- Cho, H.-J. and Chung, C.-W. 2005. An efficient and scalable approach to CNN queries in a road network. In Proceedings of the International Conference on Very large Data Bases (VLDB). 865--876. Google ScholarDigital Library
- Dijkstra, E. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269--271.Google ScholarDigital Library
- Estivill-Castro, V. and Lee, I. 2000. Autoclust+: Automatic clustering of point-data sets in the presence of obstacles. In Proceedings of the International Workshop on Temporal, Spatial, and Spatio-Temporal Data Mining (TSDM). 133--146. Google ScholarDigital Library
- Feng, J. and Watanabe, T. 2002. A fast method for continuous nearest target objects query on road network. In Proceedings of the International Conference on Virtual Systems and Multimedia (VSMM). 182--191.Google Scholar
- Gao, Y. and Zheng, B. 2009. Continuous obstructed nearest neighbor queries in spatial databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). 577--590. Google ScholarDigital Library
- Gao, Y., Zheng, B., Chen, G., Lee, W.-C., Lee, Ken C. K., and Li, Q. 2009a. Visible reverse k-nearest neighbor query processing in spatial databases. IEEE Trans. Knowl. Data Eng. 21, 9, 1314--1327. Google ScholarDigital Library
- Gao, Y., Zheng, B., Lee, W.-C., and Chen, G. 2009b. Continuous visible nearest neighbor queries. In Proceedings of the International Conference on Extending Database Technology (EDBT). 144--155. Google ScholarDigital Library
- Ghosh, S. K. and Mount, D. M. 1987. An output sensitive algorithm for computing visibility graphs. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS). 11--19. Google ScholarDigital Library
- Guttman, A. 1984. R-trees: A dynamic index structure for spatial searching. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). 47--57. Google ScholarDigital Library
- Henrich, A. 1994. A distance-scan algorithm for spatial access structures. In Proceedings of the ACM Workshop on Advances in Geographic Information Systems (GIS). 136--143.Google Scholar
- Hershberger, J. and Suri, S. 1999. An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput. 28, 6, 2215--2256. Google ScholarDigital Library
- Hjaltason, G. R. and Samet, H. 1999. Distance browsing in spatial databases. ACM Trans. Datab. Syst. 24, 2, 265--318. Google ScholarDigital Library
- Huang, Y.-K., Liao, S.-J., and Lee, C. 2009. Evaluating continuous k-nearest neighbor query on moving objects with uncertainty. Inf. Syst. 34, 4--5, 415--437. Google ScholarDigital Library
- Iwerks, G. S., Samet, H., and Smith, K. 2003. Continuous k-nearest neighbor queries for continuously moving points with updates. In Proceedings of the International Conference on Very large Data Bases (VLDB). 512--523. Google ScholarDigital Library
- Kolahdouzan, M. R. and Shahabi, C. 2005. Alternative solutions for continuous k nearest neighbor queries in spatial network databases. GeoInformatica 9, 4, 321--341. Google ScholarDigital Library
- Korn, F. and Muthukrishnan, S. 2000. Influence sets based on reverse nearest neighbor queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). 201--212. Google ScholarDigital Library
- Li, C., Gu, Y., Li, F., and Chen, M. 2010. Moving k-nearest neighbor query over obstructed regions. In Proceedings of the Asia-Pacific Web Conference on Advances in Web Technologies and Applications (APWeb). 29--35. Google ScholarDigital Library
- Li, Y., Yang, J., and Han, J. 2004. Continuous k-nearest neighbor search for moving objects. In Proceedings of the International Conference on Scientific and Statistical Database Management (SSDBM). 123--126. Google ScholarDigital Library
- Liu, F., Hua, K. A., and Do, T. T. 2007. A P2P technique for continuous k-nearest-neighbor query in road networks. In Proceedings of the International Conference on Database and Expert Systems Applications (DEXA). 264--276. Google ScholarDigital Library
- Mouratidis, K., Hadjieleftheriou, M., and Papadias, D. 2005a. Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). 634--645. Google ScholarDigital Library
- Mouratidis, K. and Papadias, D. 2007. Continuous nearest neighbor queries over sliding windows. IEEE Trans. Knowl. Data Eng. 19, 6, 789--803. Google ScholarDigital Library
- Mouratidis, K., Papadias, D., Bakiras, S., and Tao, Y. 2005b. A threshold-based algorithm for continuous monitoring of k nearest neighbors. IEEE Trans. Knowl. Data Eng. 17, 11, 1451--1464. Google ScholarDigital Library
- Mouratidis, K., Yiu, M., Papadias, D., and Mamoulis, N. 2006. Continuous nearest neighbor monitoring in road networks. In Proceedings of the International Conference on Very large Data Bases (VLDB). 43--54. Google ScholarDigital Library
- Nutanong, S., Tanin, E., and Zhang, R. 2007. Visible nearest neighbor queries. In Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA). 876--883. Google ScholarDigital Library
- Nutanong, S., Zhang, R., Tanin, E., and Kulik, L. 2008. The V<sup>*</sup>-Diagram: A query dependent approach to moving kNN queries. Proc. VLDB 1, 1, 1095--1106. Google ScholarDigital Library
- Nutanong, S., Zhang, R., Tanin, E., and Kulik, L. 2010. Analysis and evaluation of V<sup>*</sup>-kNN: An efficient algorithm for moving kNN queries. VLDB J. 19, 3, 307--332. Google ScholarDigital Library
- Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. 2000. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams 2nd Ed. Wiley. Google ScholarCross Ref
- Park, S. H., Lee, J.-H., and Kim, D.-H. 2007. Spatial clustering based on moving distance in the presence of obstacles. In Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA). 1024--1027. Google ScholarDigital Library
- Roussopoulos, N., Kelley, S., and Vincent, F. 1995. Nearest neighbor queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). 71--79. Google ScholarDigital Library
- Sellis, T., Roussopoulos, N., and Faloutsos, C. 1987. The R<sup>+</sup>-tree: A dynamic index for multi-dimensional objects. In Proceedings of the International Conference on Very large Data Bases (VLDB). 507--518. Google ScholarDigital Library
- Sharir, M. and Schorr, A. 1986. On shortest paths in polyhedral spaces. SIAM J. Comput. 15, 1, 193--215. Google ScholarDigital Library
- Sistla, P., Wolfson, O., Chamberlain, S., and Dao, S. 1997. Modeling and querying moving objects. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 422--432. Google ScholarDigital Library
- Song, Z. and Roussopoulos, N. 2001. K-nearest neighbor search for moving query point. In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases (SSTD). 79--96. Google ScholarDigital Library
- Tao, Y. and Papadias, D. 2002. Time parameterized queries in spatio-temporal databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). 334--345. Google ScholarDigital Library
- Tao, Y., Papadias, D., Lian, X., and Xiao, X. 2007. Multidimensional reverse kNN search. VLDB J. 16, 3, 293--316. Google ScholarDigital Library
- Tao, Y., Papadias, D., and Shen, Q. 2002. Continuous nearest neighbor search. In Proceedings of the International Conference on Very large Data Bases (VLDB). 287--298. Google ScholarDigital Library
- Terry, D., Goldberg, D., Nichols, D., and Oki, B. 1992. Continuous queries over append-only databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). 321--330. Google ScholarDigital Library
- Tung, A. K. H., Hou, J., and Han, J. 2001a. Spatial clustering in the presence of obstacles. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 359--367. Google ScholarDigital Library
- Tung, A. K. H., Ng, R. T., Lakshmanan, L. V. S., and Han, J. 2001b. Constraint-based clustering in large databases. In Proceedings of the International Conference on Database Theory (ICDT). 405--419. Google ScholarDigital Library
- Wang, X. and Hamilton, H. J. 2005. Clustering spatial data in the presence of obstacles. Int. J. Artif. Intell. Tools 14, 1--2, 177--198.Google ScholarCross Ref
- Wang, X., Rostoker, C., and Hamilton, H. J. 2004. Density-based spatial clustering in the presence of obstacles and facilitators. In Proceedings of the European Conference on Principles of Data Mining and Knowledge Discovery (PKDD). 446--458. Google ScholarDigital Library
- Wu, W., Guo, W., and Tan, K. L. 2007. Distributed processing of moving k-nearest-neighbor query on moving objects. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 1116--1125.Google Scholar
- Xia, C., Hsu, D., and Tung, A. K. H. 2004. A fast filter for obstructed nearest neighbor queries. In Proceedings of the British National Conference on Databases (BNCOD). 203--215.Google Scholar
- Xiong, X., Mokbel, M. F., and Aref, W. G. 2005. SEA-CNN: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 643--654. Google ScholarDigital Library
- Xu, H., Li, Z., Lu, Y., Deng, K., and Zhou, X. 2010. Group visible nearest neighbor queries in spatial databases. In Proceedings of the International Conference on Web-Age Information Management (WAIM). 333--344. Google ScholarDigital Library
- Yu, X., Pu, K., and Koudas, N. 2005. Monitoring k-nearest neighbor queries over moving objects. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 631--642. Google ScholarDigital Library
- Zaiane, O. R. and Lee, C.-H. 2002. Clustering spatial data in the presence of obstacles: A density-based approach. In Proceedings of the International Database Engineering and Applications Symposium (IDEAS). 214--223. Google ScholarDigital Library
- Zhang, J., Papadias, D., Mouratidis, K., and Zhu, M. 2004. Spatial queries in the presence of obstacles. In Proceedings of the International Conference on Extending Database Technology (EDBT). 366--384.Google Scholar
- Zhang, J., Zhu, M., Papadias, D., Tao, Y., and Lee, D. L. 2003. Location-based spatial queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD). 443--454. Google ScholarDigital Library
Index Terms
- Continuous nearest-neighbor search in the presence of obstacles
Recommendations
Range-based Obstructed Nearest Neighbor Queries
SIGMOD '16: Proceedings of the 2016 International Conference on Management of DataIn this paper, we study a novel variant of obstructed nearest neighbor queries, namely, range-based obstructed nearest neighbor (RONN) search. A natural generalization of continuous obstructed nearest-neighbor (CONN), an RONN query retrieves the ...
Continuous obstructed nearest neighbor queries in spatial databases
SIGMOD '09: Proceedings of the 2009 ACM SIGMOD International Conference on Management of dataIn 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 ...
On efficient obstructed reverse nearest neighbor query processing
GIS '11: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsIn this paper, we study a new form of reverse nearest neighbor (RNN) queries, i.e., obstructed reverse nearest neighbor (ORNN) search. It considers the impact of obstacles on the distance between objects, which is ignored by the existing work on RNN ...
Comments