Nearest Neighbor Query
- PDF / 286,501 Bytes
- 7 Pages / 547.087 x 737.008 pts Page_size
- 108 Downloads / 286 Views
Nearest Neighbor Query
tonically with the path (i. e., a path cannot be cheaper than one of its sub-sets), because, otherwise there is no bound in the expansion process. Dijkstra’s algorithm is also based on the same assumption, which is realistic for all SNDB applications.
Cross References Nearest Neighbor Query R*-tree Trip Planning Queries in Road Network Databases
Recommended Reading Key Applications Geographic Information Systems Spatial (e. g., road, river) networks are common in Geographic Information Systems (GIS). Efficient query mechanisms are important for dealing with the large and ever increasing amount of spatial data in several GIS applications. Navigation Systems Navigation systems are already incorporated in vehicles and mobile devices (e. g., PDAs). Flexible SNDB architectures and advanced algorithms will provide the means for enhanced location-based services (in addition to the common shortest path services currently offered by most systems). Decision Support Nearest neighbor and related queries are sometimes important components for decision support systems. For example, assume a supermarket chain that wants to build a number of warehouses close to existing sale facilities. This task is related to NN search and its solution could invoke SNDB architectures and algorithms. Future Directions Several specialized techniques can be used to speed up evaluation of NN queries on road networks. [8] uses the concept of network Voronoi cells and materialization. [6] presents the island approach for balancing query and materialization costs. In another direction, [5] proposes tree-based structures for capturing shortest paths in a road network and develops techniques for fast processing of NN queries on those structures. [13] addresses continuous nearest neighbor (CNN) queries that retrieve all nearest neighbors along a given route. [9] extends the Voronoi-based solution of [8] for computing CNN queries, while [2] combines network expansion and precomputed NN lists of network nodes for deriving query results. Other directions for future work include maintenance of long running NN queries on moving objects [10] and alternative forms of NN search (such as aggregate NN [14] and reverse NN [15]).
1. Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The R*tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD (1990) 2. Cho, H.J., Chung, C.W.: An Efficient and Scalable Approach to CNN Queries in a Road Network. VLDB (2005) 3. Dijkstra, E.W.: A Note on Two Problems in Connection with Graphs. Numeriche Mathematik, vol. 1, 269–271 (1959) 4. Hjaltason, G., Samet, H.: Distance Browsing in Spatial Databases. TODS 24(2), 265–318 (1999) 5. Hu, H., Lee, D.L., Xu, J. Fast Nearest Neighbor Search on Road Networks. EDBT (2006) 6. Huang, X., Jensen, C. S., Saltenis, S.: The Islands Approach to Nearest Neighbor Querying in Spatial Networks. SSTD (2005) 7. Jing, N., Huang, Y.W., Rundensteiner, E.A.: Hierarchical Encoded Path Views for Path Query Processing: an Optimal Model and its Performa
Data Loading...
