skip to main content
tutorial

Continuous Spatial Query Processing: A Survey of Safe Region Based Techniques

Published:23 May 2018Publication History
Skip Abstract Section

Abstract

In the past decade, positioning system-enabled devices such as smartphones have become most prevalent. This functionality brings the increasing popularity of location-based services in business as well as daily applications such as navigation, targeted advertising, and location-based social networking. Continuous spatial queries serve as a building block for location-based services. As an example, an Uber driver may want to be kept aware of the nearest customers or service stations. Continuous spatial queries require updates to the query result as the query or data objects are moving. This poses challenges to the query efficiency, which is crucial to the user experience of a service. A large number of approaches address this efficiency issue using the concept of safe region. A safe region is a region within which arbitrary movement of an object leaves the query result unchanged. Such a region helps reduce the frequency of query result update and hence improves query efficiency. As a result, safe region-based approaches have been popular for processing various types of continuous spatial queries. Safe regions have interesting theoretical properties and are worth in-depth analysis. We provide a comparative study of safe region-based approaches. We describe how safe regions are computed for different types of continuous spatial queries, showing how they improve query efficiency. We compare the different safe region-based approaches and discuss possible further improvements.

Skip Supplemental Material Section

Supplemental Material

References

  1. I. Afyouni, C. Ray, S. Ilarri, and C. Claramunt. 2012. Algorithms for continuous location-dependent and context-aware queries in indoor environments. In SIGSPATIAL. 329--338. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. I. Afyouni, C. Ray, S. Ilarri, and C. Claramunt. 2014. A PostgreSQL extension for continuous path and range queries in indoor mobile environments. Pervasive Mobile Comput. 15, C (2014), 128--150. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. P. K. Agarwal, L. Arge, and J. Erickson. 2003. Indexing moving points. J. Comput. Syst. Sci. 66, 1 (2003), 207--243. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. H. Al-Khalidi, D. Taniar, J. Betts, and S. Alamri. 2013. On finding safe regions for moving range queries. Math. Comput. Model. 58, 5--6 (2013), 1449--1458.Google ScholarGoogle ScholarCross RefCross Ref
  5. H. Al-Khalidi, D. Taniar, J. Betts, and S. Alamri. 2014. Monitoring moving queries inside a safe region. Sci. World J. 2014 (2014). Google ScholarGoogle ScholarCross RefCross Ref
  6. M. E. Ali, E. Tanin, R. Zhang, and L. Kulik. 2010. A motion-aware approach for efficient evaluation of continuous queries on 3D object databases. VLDB J. 19, 5 (2010), 603--632. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. D. Amagata, T. Hara, and S. Nishio. 2015. Distributed top-k query processing on multi-dimensional data with keywords. In SSDBM. 10:1--10:12. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Android. 2017. Creating and Monitoring Geofences. Retrieved from https://developer.android.com/training/location/geofencing.html.Google ScholarGoogle Scholar
  9. Apple. 2017. Region Monitoring. Retrieved from https://developer.apple.com/library/content/documentation/UserExperience/Conceptual/LocationAwarenessPG/RegionMonitoring/RegionMonitoring.html.Google ScholarGoogle Scholar
  10. M. Attique, H.-J. Cho, and T.-S. Chung. 2016. CORE: Continuous monitoring of reverse k nearest neighbors on moving objects in road networks. Computer and Information Science 2015, Roger Lee (Ed.). Springer International Publishing, Cham, 109--124.Google ScholarGoogle Scholar
  11. R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis. 2001. Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects. Technical Report TR-66. TimeCenter.Google ScholarGoogle Scholar
  12. R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis. 2002. Nearest neighbor and reverse nearest neighbor queries for moving objects. In International Database Engineering & Applications Symposium. 44--53. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. R. Benetis, C. S. Jensen, G. Karciauskas, and S. Saltenis. 2006. Nearest and reverse nearest neighbor queries for moving objects. VLDB J. 15, 3 (2006), 229--249. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. M. D. Berg, M. V. Kreveld, M. Overmars, and O. C. Schwarzkopf. 2000. Computational Geometry: Algorithms and Applications. Springer. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. C. Böhm, S. Berchtold, and D. A. Keim. 2001. Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. Comput. Surv. 33, 3 (2001), 322--373. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. S. Börzsönyi, D. Kossmann, and K. Stocker. 2001. The skyline operator. In ICDE. 421--430. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Y. Cai, K. A. Hua, and G. Cao. 2004. Processing range-monitoring queries on heterogeneous mobile objects. In MDM. 27--38.Google ScholarGoogle Scholar
  18. X. Cao, L. Chen, G. Cong, C. S. Jensen, Q. Qu, A. Skovsgaard, D. Wu, and M. L. Yiu. 2012. Spatial keyword querying. In ER. 16--29. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi. 2011. Collective spatial keyword querying. In SIGMOD. 373--384. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. B. Chazelle and H. Edelsbrunner. 1987. An improved algorithm for constructing kth-order Voronoi diagrams. IEEE Trans. Comput. 100, 11 (1987), 1349--1354. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. M. A. Cheema, L. Brankovic, X. Lin, W. Zhang, and W. Wang. 2010. Multi-guarded safe zone: An effective technique to monitor moving circular range queries. In ICDE. 189--200.Google ScholarGoogle Scholar
  22. M. A. Cheema, L. Brankovic, X. Lin, W. Zhang, and W. Wang. 2011. Continuous monitoring of distance-based range queries. IEEE Trans. Know. Data Eng. 23, 8 (2011), 1182--1199. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. M. A. Cheema, W. Zhang, X. Lin, Y. Zhang, and X. Li. 2012. Continuous reverse k nearest neighbors queries in euclidean space and in spatial networks. VLDB J. 21, 1 (2012), 69--95. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. L. Chen, G. Cong, and X. Cao. 2013a. An efficient query indexing mechanism for filtering geo-textual data. In SIGMOD. 749--760. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. L. Chen, G. Cong, X. Cao, and K.-L. Tan. 2015. Temporal spatial-keyword top-k publish/subscribe. In ICDE. 255--266.Google ScholarGoogle Scholar
  26. L. Chen, G. Cong, C. S. Jensen, and D. Wu. 2013b. Spatial keyword query processing: An experimental evaluation. In PVLBD 6, 3 (2013), 217--228. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. H.-J. Cho and C.-W. Chung. 2005. An efficient and scalable approach to CNN queries in a road network. In VLDB. 865--876. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. H.-J. Cho, K. Ryu, and T.-S. Chung. 2014. An efficient algorithm for computing safe exit points of moving range queries in directed road networks. Inform. Syst. 41 (2014), 1--19. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. F. M. Choudhury, Z. Bao, J. S. Culpepper, and T. Sellis. 2017. Monitoring the top-m rank aggregation of spatial objects in streaming queries. In ICDE. 585--596. Google ScholarGoogle ScholarCross RefCross Ref
  30. C.-Y. Chow, M. F. Mokbel, and H. V. Leong. 2011. On efficient and scalable support of continuous queries in mobile peer-to-peer environments. IEEE Trans. Mobile Comput. 10, 10 (2011), 1473--1487. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. P. Ciaccia, M. Patella, and P. Zezula. 1997. M-tree: An efficient access method for similarity search in metric spaces. In VLDB. 426--435. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. G. Cong and C. S. Jensen. 2016. Querying geo-textual data: Spatial keyword queries and beyond. In SIGMOD. 2207--2212. Google ScholarGoogle ScholarDigital LibraryDigital Library
  33. G. Cong, C. S. Jensen, and D. Wu. 2009. Efficient retrieval of the top-k most relevant spatial web objects. PVLDB 2, 1 (2009), 337--348. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. T. T. Do, K. A. Hua, and C. S. Lin. 2009. ExtRange: Continuous moving range queries in mobile peer-to-peer networks. In MDM. 317--322. Google ScholarGoogle ScholarDigital LibraryDigital Library
  35. M. Erwig and F. Hagen. 2000. The graph voronoi diagram with applications. Networks 36, 3 (2000), 156--163. Google ScholarGoogle ScholarCross RefCross Ref
  36. R. A. Finkel and J. L. Bentley. 1974. Quad trees a data structure for retrieval on composite keys. Acta Inform. 4, 1 (1974), 1--9. Google ScholarGoogle ScholarDigital LibraryDigital Library
  37. S. Fortune. 1987. A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 1-4 (1987), 153--174. Google ScholarGoogle ScholarDigital LibraryDigital Library
  38. V. Gaede and O. Günther. 1998. Multidimensional access methods. Comput. Surv. 30, 2 (1998), 170--231. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. B. Gedik and L. Liu. 2004. MobiEyes: Distributed processing of continuously moving queries on moving objects in a mobile system. In EDBT. 67--87.Google ScholarGoogle Scholar
  40. B. Gedik and L. Liu. 2006. MobiEyes: A distributed location monitoring service using moving location queries. IEEE Trans. Mobile Comput. 5, 10 (2006), 1384--1402. Google ScholarGoogle ScholarDigital LibraryDigital Library
  41. B. Gedik, K.-L. Wu, P. Yu, and L. Liu. 2004. Motion adaptive indexing for moving continual queries over moving objects. In CIKM. 427--436. Google ScholarGoogle ScholarDigital LibraryDigital Library
  42. Y. Gu, G. Liu, J. Qi, H. Xu, G. Yu, and R. Zhang. 2016a. The moving k diversified nearest neighbor query. IEEE Trans. Knowl. Data Eng. 28, 10 (2016), 2778--2792. Google ScholarGoogle ScholarDigital LibraryDigital Library
  43. Y. Gu, H. Zhang, Z. Wang, and G. Yu. 2016b. Efficient moving k nearest neighbor queries over line segment objects. World Wide Web 19, 4 (2016), 653--677. Google ScholarGoogle ScholarDigital LibraryDigital Library
  44. L. Guo, J. Shao, H. Aung, and K.-L. Tan. 2015. Efficient continuous top-k spatial keyword queries on road networks. GeoInformatica 19, 1 (2015), 29--60. Google ScholarGoogle ScholarDigital LibraryDigital Library
  45. A. Guttman. 1984. R-trees: A dynamic index structure for spatial searching. In SIGMOD. 47--57. Google ScholarGoogle ScholarDigital LibraryDigital Library
  46. T. Hashem, L. Kulik, and R. Zhang. 2013. Countering overlapping rectangle privacy attack for moving kNN queries. Inform. Syst. 38, 3 (2013), 430--453. Google ScholarGoogle ScholarDigital LibraryDigital Library
  47. A. M. Hendawi and M. F. Mokbel. 2012. Predictive spatio-temporal queries: A comprehensive survey and future directions. In International Workshop on Mobile Geographic Information Systems. 97--104. Google ScholarGoogle ScholarDigital LibraryDigital Library
  48. G. R. Hjaltason and H. Samet. 1999. Distance browsing in spatial databases. ACM Trans. Database Syst. 24, 2 (1999), 265--318. Google ScholarGoogle ScholarDigital LibraryDigital Library
  49. Y.-L. Hsueh, R. Zimmermann, and W.-S. Ku. 2009. Adaptive safe regions for continuous spatial queries over moving objects. In DASFAA. 71--76. Google ScholarGoogle ScholarDigital LibraryDigital Library
  50. H. Hu, J. Xu, and D. L. Lee. 2005. A generic framework for monitoring continuous spatial queries over moving objects. In SIGMOD. 479--490. Google ScholarGoogle ScholarDigital LibraryDigital Library
  51. J.-L. Huang and C.-C. Huang. 2013. A proxy-based approach to continuous location-based spatial queries in mobile environments. IEEE Trans. Knowl. Data Eng. 25, 2 (2013), 260--273. Google ScholarGoogle ScholarDigital LibraryDigital Library
  52. W. Huang, G. Li, K.-L. Tan, and J. Feng. 2012. Efficient safe-region construction for moving top-k spatial keyword queries. In CIKM. 932--941. Google ScholarGoogle ScholarDigital LibraryDigital Library
  53. S. Ilarri, E. Mena, and A. Illarramendi. 2006. Location-dependent queries in mobile contexts: Distributed processing using mobile agents. IEEE Trans. Mobile Comput. 5, 8 (2006), 1029--1043. Google ScholarGoogle ScholarDigital LibraryDigital Library
  54. S. Ilarri, E. Mena, and A. Illarramendi. 2010. Location-dependent query processing: Where we are and where we are heading. Comput. Surv. 42, 3 (2010), 12:1--12:73. Google ScholarGoogle ScholarDigital LibraryDigital Library
  55. T. Imielinski and B. Badrinath. 1992. Querying in highly mobile distributed environments. In VLDB. 41--52. Google ScholarGoogle ScholarDigital LibraryDigital Library
  56. G. S. Iwerks, H. Samet, and K. Smith. 2003. Continuous k-nearest neighbor queries for continuously moving points with updates. In VLDB. 512--523. Google ScholarGoogle ScholarDigital LibraryDigital Library
  57. G. S. Iwerks, H. Samet, and K. P. Smith. 2006. Maintenance of k-nn and spatial join queries on continuously moving points. ACM Trans. Database Syst. 31, 2 (2006), 485--536. Google ScholarGoogle ScholarDigital LibraryDigital Library
  58. C. S. Jensen, J. Kolárvr, T. B. Pedersen, and I. Timko. 2003. Nearest neighbor queries in road networks. In GIS. 1--8. Google ScholarGoogle ScholarDigital LibraryDigital Library
  59. C. S. Jensen, D. Lin, and B. C. Ooi. 2004. Query and update efficient B-tree based indexing of moving objects. In VLDB. 768--779. Google ScholarGoogle ScholarDigital LibraryDigital Library
  60. D. V. Kalashnikov, S. Prabhakar, S. E. Hambrusch, and W. G. Aref. 2002. Efficient evaluation of continuous range queries on moving objects. In DEXA. 731--740. Google ScholarGoogle ScholarDigital LibraryDigital Library
  61. M. R. Kolahdouzan and C. Shahabi. 2004a. Continuous k-nearest neighbor queries in spatial network databases. In STDBM. 33--40.Google ScholarGoogle Scholar
  62. M. R. Kolahdouzan and C. Shahabi. 2004b. Voronoi-based k nearest neighbor search for spatial network databases. In VLDB. 840--851. Google ScholarGoogle ScholarDigital LibraryDigital Library
  63. M. R. Kolahdouzan and C. Shahabi. 2005. Alternative solutions for continuous k nearest neighbor queries in spatial network databases. GeoInformatica 9, 4 (2005), 321--341. Google ScholarGoogle ScholarDigital LibraryDigital Library
  64. N. Koudas, B. C. Ooi, K.-L. Tan, and R. Zhang. 2004. Approximate NN queries on streams with guaranteed error/performance bounds. In VLDB. 804--815. Google ScholarGoogle ScholarDigital LibraryDigital Library
  65. J. Krumm. 2009. A survey of computational location privacy. Pers. Ubiquitous Comput. 13, 6 (2009), 391--399. Google ScholarGoogle ScholarDigital LibraryDigital Library
  66. L. Kulik and E. Tanin. 2006. Incremental rank updates for moving query points. In GIScience. 251--268. Google ScholarGoogle ScholarDigital LibraryDigital Library
  67. J. Lee, S. Kang, Y. Lee, S. J. Lee, and J. Song. 2009. BMQ-processor: A high-performance border-crossing event detection framework for large-scale monitoring applications. IEEE Trans. Know. Data Eng. 21, 2 (2009), 234--252. Google ScholarGoogle ScholarDigital LibraryDigital Library
  68. C. Li, Y. Gu, J. Qi, G. Yu, R. Zhang, and Q. Deng. 2016. INSQ: An influential neighbor set based moving kNN query processing system. In ICDE. 1338--1341.Google ScholarGoogle Scholar
  69. C. Li, Y. Gu, J. Qi, G. Yu, R. Zhang, and W. Yi. 2014. Processing moving kNN queries using influential neighbor sets. PVLDB 8, 2 (2014), 113--124. Google ScholarGoogle ScholarDigital LibraryDigital Library
  70. C. Li, Y. Gu, J. Qi, and G. Yu. 2015. A safe region based approach to moving KNN queries in obstructed space. Know. Inform. Syst. 45, 2 (2015), 417--451. Google ScholarGoogle ScholarDigital LibraryDigital Library
  71. Z. Li, K. C. K. Lee, B. Zheng, W.-C. Lee, D. Lee, and X. Wang. 2011. IR-tree: An efficient index for geographic document search. IEEE Trans. Knowl. Data En. 23, 4 (2011), 585--599. Google ScholarGoogle ScholarDigital LibraryDigital Library
  72. M. F. Mokbel and W. G. Aref. 2008. SOLE: Scalable on-line execution of continuous queries on spatio-temporal data streams. VLDB J. 17, 5 (2008), 971--995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  73. M. F. Mokbel, T. M. Ghanem, and W. G. Aref. 2003. Spatio-temporal access methods. IEEE Data Eng. Bull. 26, 2 (2003), 40--49.Google ScholarGoogle Scholar
  74. M. F. Mokbel, X. Xiong, and W. G. Aref. 2004. SINA: Scalable incremental processing of continuous queries in spatio-temporal databases. In SIGMOD. 623--634. Google ScholarGoogle ScholarDigital LibraryDigital Library
  75. K. Mouratidis, S. Bakiras, and D. Papadias. 2009. Continuous monitoring of spatial queries in wireless broadcast environments. IEEE Trans. Mobile Comput. 8, 10 (2009), 1297--1311. Google ScholarGoogle ScholarDigital LibraryDigital Library
  76. K. Mouratidis, D. Papadias, S. Bakiras, and Y. Tao. 2005b. A threshold-based algorithm for continuous monitoring of k nearest neighbors. IEEE Trans. Knowl. Data Eng. 17, 11 (2005), 1451--1464. Google ScholarGoogle ScholarDigital LibraryDigital Library
  77. K. Mouratidis, D. Papadias, and M. Hadjieleftheriou. 2005a. Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring. In SIGMOD. 634--645. Google ScholarGoogle ScholarDigital LibraryDigital Library
  78. L.-V. Nguyen-Dinh, W. G. Aref, and M. F. Mokbel. 2010. Spatio-temporal access methods: Part 2 (2003 - 2010). IEEE Data Eng. Bull. 33, 2 (2010), 46--55.Google ScholarGoogle Scholar
  79. J. Nievergelt, H. Hinterberger, and K. C. Sevcik. 1984. The grid file: An adaptable, symmetric multikey file structure. ACM Trans. Database Syst. 9, 1 (1984), 38--71. Google ScholarGoogle ScholarDigital LibraryDigital Library
  80. S. Nutanong, R. Zhang, E. Tanin, and L. Kulik. 2008. The V*-diagram: A query dependent approach to moving kNN queries. PVLDB 1, 1 (2008), 1095--1106. Google ScholarGoogle ScholarDigital LibraryDigital Library
  81. S. Nutanong, R. Zhang, E. Tanin, and L. Kulik. 2010. Analysis and evaluation of V*-kNN: An efficient algorithm for moving kNN queries. VLDB J. 19, 3 (2010), 307--332. Google ScholarGoogle ScholarDigital LibraryDigital Library
  82. Y. Ohsawa and H. Htoo. 2016. Versatile safe-region generation method for continuous monitoring of moving objects in the road network distance. In DASFAA. 377--392. Google ScholarGoogle ScholarCross RefCross Ref
  83. A. Okabe, B. Boots, and K. Sugihara. 1992. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Inc. Google ScholarGoogle ScholarDigital LibraryDigital Library
  84. J. Orenstein and T. Merrett. 1984. A class of data structures for associative searching. In PODS. 181--190. Google ScholarGoogle ScholarDigital LibraryDigital Library
  85. D. Pfoser, C. S. Jensen, and Y. Theodoridis. 2000. Novel approaches in query processing for moving object trajectories. In VLDB. 395--406. Google ScholarGoogle ScholarDigital LibraryDigital Library
  86. S. Prabhakar, Y. Xia, D. V. Kalashnikov, W. G. Aref, and S. E. Hambrusch. 2002. Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. IEEE Trans. Comput. 51, 10 (2002), 1124--1140. Google ScholarGoogle ScholarDigital LibraryDigital Library
  87. F. P. Preparata and M. Shamos. 1985. Computational Geometry: An Introduction. Springer. Google ScholarGoogle ScholarDigital LibraryDigital Library
  88. J. Rocha-Junior, O. Gkorgkas, S. Jonassen, and K. Nørvåg. 2011. Efficient processing of top-k spatial keyword queries. In SSTD. 205--222. Google ScholarGoogle ScholarDigital LibraryDigital Library
  89. N. Roussopoulos, S. Kelley, and F. Vincent. 1995. Nearest neighbor queries. In SIGMOD. 71--79. Google ScholarGoogle ScholarDigital LibraryDigital Library
  90. S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. 2000. Indexing the positions of continuously moving objects. In SIGMOD. 331--342. Google ScholarGoogle ScholarDigital LibraryDigital Library
  91. R. Seidel. 1988. Constrained Delaunay Triangulations and Voronoi Diagrams with Obstacles. Technical Report 260. IIG-TU Graz, Austria.Google ScholarGoogle Scholar
  92. M. Sharifzadeh and C. Shahabi. 2010. VoR-tree: R-trees with voronoi diagrams for efficient processing of spatial nearest neighbor queries. PVLDB 3, 1--2 (2010), 1231--1242. Google ScholarGoogle ScholarDigital LibraryDigital Library
  93. R. I. D. Silva, D. F. Macedo, and J. M. S. Nogueira. 2014. Spatial query processing in wireless sensor network—A survey. Inform. Fusion 15 (2014), 32--43. Google ScholarGoogle ScholarDigital LibraryDigital Library
  94. A. P. Sistla, O. Wolfson, and B. Xu. 2015. Continuous nearest-neighbor queries with location uncertainty. VLDB J. 24, 1 (2015), 25--50. Google ScholarGoogle ScholarDigital LibraryDigital Library
  95. C. Smith. 2016. By the Numbers: 20 Important Foursquare Stats. Retrieved from http://expandedramblings.com/index.php/by-the-numbers-interesting-foursquare-user-stats/.Google ScholarGoogle Scholar
  96. Z. Song and N. Roussopoulos. 2001. K-nearest neighbor search for moving query point. In SSTD. 79--96. Google ScholarGoogle ScholarDigital LibraryDigital Library
  97. Y. Tao and D. Papadias. 2002. Time-parameterized queries in spatio-temporal databases. In SIGMOD. 334--345. Google ScholarGoogle ScholarDigital LibraryDigital Library
  98. Y. Tao, D. Papadias, and Q. Shen. 2002. Continuous nearest neighbor search. In VLDB. 287--298. Google ScholarGoogle ScholarDigital LibraryDigital Library
  99. H. Wang and R. Zimmermann. 2007. Location-based query processing on moving objects in road networks. In VLDB. 321--332.Google ScholarGoogle Scholar
  100. H. Wang and R. Zimmermann. 2011. Processing of continuous location-based range queries on moving objects in road networks. IEEE Trans. Knowl. Data Eng. 23, 7 (2011), 1065--1078. Google ScholarGoogle ScholarDigital LibraryDigital Library
  101. X. Wang, Y. Zhang, W. Zhang, X. Lin, and W. Wang. 2014b. Selectivity estimation on streaming spatio-textual data using local correlations. PVLDB 8, 2 (2014), 101--112. Google ScholarGoogle ScholarDigital LibraryDigital Library
  102. X. Wang, Y. Zhang, W. Zhang, X. Lin, and W. Wang. 2015. AP-tree: Efficiently support continuous spatial-keyword queries over stream. In ICDE. 1107--1118.Google ScholarGoogle Scholar
  103. Y. Wang, R. Zhang, C. Xu, J. Qi, Y. Gu, and G. Yu. 2014a. Continuous visible k nearest neighbor query on moving objects. Inform. Syst. 44 (2014), 1--21. Google ScholarGoogle ScholarCross RefCross Ref
  104. P. G. D. Ward, Z. He, R. Zhang, and J. Qi. 2014. Real-time continuous intersection joins over large sets of moving objects using graphic processing units. VLDB J. 23, 6 (2014), 965--985. Google ScholarGoogle ScholarDigital LibraryDigital Library
  105. D. Wu, M. L. Yiu, and C. S. Jensen. 2013. Moving spatial keyword queries: Formulation, methods, and analysis. ACM Trans. Database Syst. 38, 1 (2013), 7:1--7:47. Google ScholarGoogle ScholarDigital LibraryDigital Library
  106. D. Wu, M. L. Yiu, C. S. Jensen, and G. Cong. 2011. Efficient continuously moving top-k spatial keyword query processing. In ICDE. 541--552. Google ScholarGoogle ScholarDigital LibraryDigital Library
  107. X. Xiong, M. F. Mokbel, and W. G. Aref. 2005. SEA-CNN: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In ICDE. 643--654. Google ScholarGoogle ScholarDigital LibraryDigital Library
  108. B. Yang, H. Lu, and C. S. Jensen. 2010. Probabilistic threshold k nearest neighbor queries over moving objects in symbolic indoor space. In EDBT. 335--346. Google ScholarGoogle ScholarDigital LibraryDigital Library
  109. M. L. Yiu, E. Lo, and D. Yung. 2011. Authentication of moving kNN queries. In ICDE. 565--576. Google ScholarGoogle ScholarDigital LibraryDigital Library
  110. M. Yu, G. Li, and J. Feng. 2015. A cost-based method for location-aware publish/subscribe services. In CIKM. 693--702. Google ScholarGoogle ScholarDigital LibraryDigital Library
  111. X. Yu, K. Q. Pu, and N. Koudas. 2005. Monitoring k-nearest neighbor queries over moving objects. In ICDE. 631--642. Google ScholarGoogle ScholarDigital LibraryDigital Library
  112. D. Yung, M. L. Yiu, and E. Lo. 2012. A safe-exit approach for efficient network-based moving range queries. Data Knowl. Eng. 72 (2012), 126--147. Google ScholarGoogle ScholarDigital LibraryDigital Library
  113. K. Zeberga, R. Jin, H.-J. Cho, and T.-S. Chung. 2017. A safe-region approach to a moving k-rnn queries in a directed road network. J. Circuits, Syst. Comput. 26, 5 (2017), 1--18. Google ScholarGoogle ScholarCross RefCross Ref
  114. J. Zhang, M. Zhu, D. Papadias, Y. Tao, and D. L. Lee. 2003. Location-based spatial queries. In SIGMOD. 443--454. Google ScholarGoogle ScholarDigital LibraryDigital Library
  115. R. Zhang, H. V. Jagadish, B. T. Dai, and K. Ramamohanarao. 2010. Optimized algorithms for predictive range and kNN queries on moving objects. Information Systems 35, 8 (2010), 911--932. Google ScholarGoogle ScholarDigital LibraryDigital Library
  116. R. Zhang, D. Lin, R. Kotagiri, and E. Bertino. 2008. Continuous intersection joins over moving objects. In ICDE. 863--872. Google ScholarGoogle ScholarDigital LibraryDigital Library
  117. R. Zhang, B. C. Ooi, and K.-L. Tan. 2004. Making the pyramid technique robust to query types and workloads. In ICDE. 313--324. Google ScholarGoogle ScholarDigital LibraryDigital Library
  118. R. Zhang, J. Qi, D. Lin, W. Wang, and R. C.-W. Wong. 2012. A highly optimized algorithm for continuous intersection join queries over moving objects. VLDB J. 21, 4 (2012), 561--586. Google ScholarGoogle ScholarDigital LibraryDigital Library
  119. B. Zheng, K. Zheng, X. Xiao, H. Su, H. Yin, X. Zhou, and G. Li. 2016. Keyword-aware continuous kNN query on road networks. In ICDE. 871--882. Google ScholarGoogle ScholarCross RefCross Ref

Index Terms

  1. Continuous Spatial Query Processing: A Survey of Safe Region Based Techniques

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          • Published in

            cover image ACM Computing Surveys
            ACM Computing Surveys  Volume 51, Issue 3
            May 2019
            796 pages
            ISSN:0360-0300
            EISSN:1557-7341
            DOI:10.1145/3212709
            • Editor:
            • Sartaj Sahni
            Issue’s Table of Contents

            Copyright © 2018 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 23 May 2018
            • Accepted: 1 March 2018
            • Revised: 1 January 2018
            • Received: 1 November 2016
            Published in csur Volume 51, Issue 3

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • tutorial
            • Research
            • Refereed

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader