Nearest Neighbor Query, Definition
- PDF / 92,491 Bytes
- 2 Pages / 547.087 x 737.008 pts Page_size
- 89 Downloads / 212 Views
Nearest Neighbor Query, Definition
Future Directions With the development of spatial location detection techniques, there are more and more applications for NN queries. Recently, there have been two interesting and emergent directions: one is NN queries in road networks and the other is NN queries over moving objects. Most of traditional NN algorithms are designed based on the Euclidean distance. In some real-world applications, however, data objects are constrained by spatial networks. In such cases, the actual distance between two objects corresponds to the road network distance. It is an interesting topic to efficiently compute NN queries in this distinct metric space. In recent years, the prevalence of inexpensive mobile devices (e. g., PDA and mobile phones), together with the advances in sensor networks and location techniques, enables a location aware environment, where all objects of interest can determine their locations. Under such environments, the objects and query points are continuous changing their locations, and updates are periodically sent to the databases. It is a challenging task to design efficient and scalable algorithms to compute the NN queries over continuously moving objects. Cross References Indexing, Hilbert R-tree, Spatial Indexing, Multimedia
Indexing References 1. Arya, S. Mount, D.M., Netanyahu, N.S., Silverman, R., and Wu, A.Y.: An optimal algorithm for approximate nearest neighbor in fixed dimensions. J. ACM 45(6), 891–923 (1994) 2. Hu, H., and Lee, D.L.: Range nearest-neighbor query. IEEE Trans. on Knowl. Data Eng. 18(1), 78–91 (2006) 3. Roussopoulos, N., Kelley, S., Vincent, F.: Nearest neighbor queries. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 71–79 (1995) 4. Fix E., Hodges, J.L.: Discriminatory analysis: non-parametric discrimination: consistency properties, Report No. 4. USAF School of Aviation Medicine, Randoph Field (1951) 5. Fix E., Hodges, J.L.: Discriminatory analysis: non-parametric discrimination: small sample performance, Report No. 11. USAF School of Aviation Medicine, Randolph Field (1952) 6. Lawler, E.L., Lenstra, J. K., Rinnooy Khan, A.H.G., Shmoys, D. B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons, Chichester (1985) 7. Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6, 563–581 (1977) 8. Sproull, R.: Refinements to nearest neighbor searching in Kdimensional trees. Algorithmica 6, 579–589 (1991) 9. Arya, S., Mount, D., Netanyahu, N., Silverman, R., Wu, A.: An optimal algorithm for approximate nearest neighbor searching. J. ACM 45(6), 891–923 (1998)
10. Samet, H.: The Design & Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA (1989) 11. Samet, H.: Applications of Spatial Data Structures, Computer Graphics, Image Processing and GIS, Addison-Wesley, Reading, MA (1990) 12. Hjaltason, G.R., Samet, H.: Distance browsing in spatial databases. ACM Transaction on Database.
Data Loading...
