Hanan Samet
Jagan Sankaranarayanan
ABSTRACT
An algorithm is presented for finding the k nearest neighbors in a spatial network in a best-first manner using network distance. The algorithm is based on precomputing the shortest paths between all possible vertices in the network and then making use of an encoding that takes advantage of the fact that the shortest paths from vertex u to all of the remaining vertices can be decomposed into subsets based on the first edges on the shortest paths to them from u. Thus, in the worst case, the amount of work depends on the number of objects that are examined and the number of links on the shortest paths to them from q, rather than depending on the number of vertices in the network. The amount of storage required to keep track of the subsets is reduced by taking advantage of their spatial coherence which is captured by the aid of a shortest path quadtree. In particular, experiments on a number of large road networks as well as a theoretical analysis have shown that the storage has been reduced from O(N3) to O(N1.5) (i.e., by an order of magnitude equal to the square root). The precomputation of the shortest paths along the network essentially decouples the process of computing shortest paths along the network from that of finding the neighbors, and thereby also decouples the domain S of the query objects and that of the objects from which the neighbors are drawn from the domain V of the vertices of the spatial network. This means that as long as the spatial network is unchanged, the algorithm and underlying representation of the shortest paths in the spatial network can be used with different sets of objects.
- J. E. Bresenham. Algorithm for computer control of a digital plotter. IBM Systems Journal, 4(1):25--30, 1965.Google Scholar
Digital Library
- H.-J. Cho and C.-W. Chung. An efficient and scalable approach to CNN queries in a road network. In VLDB'05, pp. 865--876, Trondheim, Norway, Sep. 2005. Google ScholarDigital Library
- K. L. Clarkson. Fast algorithm for the all nearest neighbors problem. In FOCS'83, pp. 226--232, Tucson, AZ, Nov. 1983. Google ScholarDigital Library
- E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.Google ScholarDigital Library
- G. N. Frederickson. Planar graph decomposition and all pairs shortest paths. JACM, 38(1):162--204, Jan. 1991. Google ScholarDigital Library
- K. Fukunaga and P. M. Narendra. A branch and bound algorithm for computing k-nearest neighbors. IEEE Trans. on Comp., 24(7):750--753, July 1975. Google ScholarDigital Library
- I. Gargantini. An effective way to represent quadtrees. CACM, 25(12):905--910, Dec. 1982. Google ScholarDigital Library
- A. V. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. In SODA'05, pp. 156--165, Vancouver, Canada, Jan. 2005. Google ScholarDigital Library
- A. Henrich. A distance-scan algorithm for spatial access structures. In ACM GIS'94, pp. 136--143, Gaithersburg, MD, Dec. 1994.Google Scholar
- G. R. Hjaltason and H. Samet. Distance browsing in spatial databases. TODS, 24(2):265--318, June 1999. Google ScholarDigital Library
- E. G. Hoel and H. Samet. Efficient processing of spatial queries in line segment databases. In SSD'91, LNCS 525, pp. 237--256, Zurich, Switzerland, Aug. 1991. Google ScholarDigital Library
- H. Hu, D. L. Lee, and V. C. S. Lee. Distance indexing on road networks. In VLDB'06, pp. 894--905, Seoul, Korea, Sep. 2006. Google ScholarDigital Library
- G. M. Hunter and K. Steiglitz. Operations on images using quad trees. PAMI, 1(2):145--153, Apr. 1979.Google ScholarDigital Library
- N. Jing, Y.-W. Huang, and E. A. Rundensteiner. Hierarchical encoded path views for path query processing: an optimal model and its performance evaluation. TKDE, 10(3):409--432, May 1998. Google ScholarDigital Library
- M. R. Kolahdouzan and C. Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. In VLDB'04, pp. 840--851, Toronto, Canada, Sep. 2004. Google ScholarDigital Library
- M. R. Kolahdouzan and C. Shahabi. Continuous k-nearest neighbor queries in spatial network databases. In STDBM'04, pp. 33--40, Toronto, Canada, Aug. 2004.Google Scholar
- M. Lindenbaum, H. Samet, and G. R. Hjaltason. A probabilistic analysis of trie-based sorting of large collections of line segments in spatial databases. SIAM J. on Computing, 35(1):22--58, Sep. 2005. Google ScholarDigital Library
- G. M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. Tech. report, IBM Ltd., Ottawa, Canada, 1966.Google Scholar
- R. C. Nelson and H. Samet. A population analysis for hierarchical data structures. In SIGMOD'87, pp. 270--277, San Francisco, May 1987. Google ScholarDigital Library
- J. A. Orenstein. Multidimensional tries used for associative searching. Inf. Proc. Letters, 14(4):150--157, June 1982.Google ScholarCross Ref
- D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases. In VLDB'03, pp. 802--813, Berlin, Germany, Sep. 2003. Google ScholarDigital Library
- N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In SIGMOD'95, pp. 71--79, San Jose, CA, May 1995. Google ScholarDigital Library
- H. Samet. Region representation: quadtrees from binary arrays. CGIP'80, 13(1):88--93, May 1980.Google ScholarCross Ref
- H. Samet. An algorithm for converting rasters to quadtrees. PAMI, 3(1):93--95, Jan. 1981.Google ScholarDigital Library
- H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan-Kaufmann, San Francisco, 2006. Google ScholarDigital Library
- H. Samet and R. E. Webber. Storing a collection of polygons using quadtrees. TOGS, 4(3):182--222, July 1985. Google ScholarDigital Library
- J. Sankaranarayanan, H. Alborzi, and H. Samet. Efficient query processing on spatial networks. In ACM GIS'05, pp. 200--209, Bremen, Germany, Nov. 2005. Google ScholarDigital Library
- C. A. Shaffer and H. Samet. Optimal quadtree construction algorithms. CVGIP'87 , 37(3):402--419, Mar. 1987. Google ScholarDigital Library
- C. A. Shaffer, H. Samet, and R. C. Nelson. QUILT: a geographic information system based on quadtrees. Int. Jour. of Geog. Inf. Sys., 4(2):103--131, Apr.-Jun. 1990.Google ScholarCross Ref
- C. Shahabi, M. R. Kolahdouzan, and M. Sharifzadeh. A road network embedding technique for k-nearest neighbor search in moving object databases. GeoInformatica, 7(3):255--273, Sep. 2003. Google ScholarDigital Library
- D. Wagner and T. Willhalm. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In ESA'03, LNCS 2832, pp. 776--787, Budapest, Hungary, Sep. 2003.Google ScholarCross Ref
- F. Zhan and C. E. Noon. Shortest path algorithms: an evaluation using real road networks. Transportation Science, 32(1):65--73, Feb. 1998. Google ScholarDigital Library
Index Terms
- Scalable network distance browsing in spatial databases
Recommendations
Efficient query processing on spatial networks
GIS '05: Proceedings of the 13th annual ACM international workshop on Geographic information systemsA framework for determining the shortest path and the distance between every pair of vertices on a spatial network is presented. The framework, termed SILC, uses path coherence between the shortest path and the spatial positions of vertices on the ...
Distance browsing in spatial databases
We compare two different techniques for browsing through a collection of spatial objects stored in an R-tree spatial data structure on the basis of their distances from an arbitrary spatial query object. The conventional approach is one that makes use ...
Finding Alternative Shortest Paths in Spatial Networks
Shortest path query is one of the most fundamental queries in spatial network databases. There exist algorithms that can process shortest path queries in real time. However, many complex applications require more than just the calculation of a single ...
Comments