Spatial Queries in the Presence of Obstacles

作者: Jun Zhang , Dimitris Papadias , Kyriakos Mouratidis , Manli Zhu

DOI: 10.1007/978-3-540-24741-8_22

关键词:

摘要: Despite the existence of obstacles in many database applications, traditional spatial query processing utilizes Euclidean distance metric assuming that points space are directly reachable. In this paper, we study queries presence obstacles, where obstructed between two is defined as length shortest path connects them without crossing any obstacles. We propose efficient algorithms for most important types, namely, range search, nearest neighbors, e-distance joins and closest pairs, considering both data objects indexed by R-trees. The effectiveness proposed solutions verified through extensive experiments.

参考文章(25)
Subir Kumar Ghosh, David M. Mount, An output-sensitive algorithm for computing visibility SIAM Journal on Computing. ,vol. 20, pp. 888- 910 ,(1991) , 10.1137/0220055
Y Ioannidis, M Stonebraker, L Shapiro, T Sellis, R-M Kung, E Hanson, Heuristic search in database systems Proceedings from the first international workshop on Expert database systems. pp. 537- 548 ,(1986)
Takao Asano, Tetsuo Asano, Leonidas Guibas, John Hershberger, Hiroshi Imai, Visibility of disjoint polygons Algorithmica. ,vol. 1, pp. 49- 63 ,(1986) , 10.1007/BF01840436
Gísli R. Hjaltason, Hanan Samet, Distance browsing in spatial databases ACM Transactions on Database Systems. ,vol. 24, pp. 265- 318 ,(1999) , 10.1145/320248.320255
Michel Pocchiola, Gert Vegter, Minimal tangent visibility graphs Computational Geometry: Theory and Applications. ,vol. 6, pp. 303- 314 ,(1996) , 10.1016/0925-7721(95)00016-X
Michel Pocchiola, Gert Vegter, Pseudo-triangulations: theory and applications symposium on computational geometry. pp. 291- 300 ,(1996) , 10.1145/237218.237398
Micha Sharir, Amir Schorr, On Shortest Paths in Polyhedral Spaces ,(2015)
Michel Pocchiola, Gert Vegter, Computing the visibility graph via pseudo-triangulations Proceedings of the eleventh annual symposium on Computational geometry - SCG '95. pp. 248- 257 ,(1995) , 10.1145/220279.220306
Emo Welzl, Constructing the visibility graph for n-line segments in O(n2) time Information Processing Letters. ,vol. 20, pp. 167- 171 ,(1985) , 10.1016/0020-0190(85)90044-4
Stéphane Rivière, Topologically sweeping the visibility complex of polygonal scenes Proceedings of the eleventh annual symposium on Computational geometry - SCG '95. pp. 436- 437 ,(1995) , 10.1145/220279.220339