Nearest-Neighbor Searching and Metric Space Dimensions
作者： Kenneth L. Clarkson
DOI:
关键词: Theoretical computer science 、 Mathematics 、 Range searching 、 Metric (mathematics) 、 Fisher information metric 、 Nearest neighbor search 、 Discrete mathematics 、 Equilateral dimension 、 Convex metric space 、 Metric space 、 Intrinsic metric
摘要: Given a set S of points in metric space with distance function D, the nearest-neighbor searching problem is to build data structure for so that an input query point q, s 2 minimizes D(s,q) can be found quickly. We survey approaches this problem, and its relation concepts dimension. Several measures dimension estimated using searching, while others used estimate cost searching. In recent years, several structures have been proposed are provably good low-dimensional spaces, some particular These other surveyed.
stanford.edu 参考文章(89)
Ya. B. Pesin, Dimension theory in dynamical systems ,(1997)
Piotr Indyk, Nearest Neighbors in High-Dimensional Spaces Handbook of Discrete and Computational Geometry, Second Edition. pp. 877- 892 ,(2004) , 10.1201/9781420035315.CH39
Patrice Assouad, Plongements lipschitziens dans Rn ,(2003)
Richard E. Ladner, Kevin C. Zatloukal, Mary Holland Johnson, Nearest neighbor search for data compression. Data Structures, Near Neighbor Searches, and Methodology. pp. 69- 86 ,(1999)
Surender Baswana, Sandeep Sen, Randomized Graph Data-Structures for Approximate Shortest Paths Handbook of Data Structures and Applications. pp. 611- 625 ,(2018) , 10.1201/9781315119335-39
Peter Willett, Molecular diversity techniques for chemical databases. Information Research. ,vol. 2, ,(1996)
Kai Hormann, From Scattered Samples to Smooth Surfaces ,(2003)
COLLEEN D. CUTLER, A REVIEW OF THE THEORY AND ESTIMATION OF FRACTAL DIMENSION WORLD SCIENTIFIC. pp. 1- 107 ,(1993) , 10.1142/9789814317382_0001
Yakov B. Pesin, Dimension Theory in Dynamical Systems: Contemporary Views and Applications University of Chicago Press. ,(1997) , 10.7208/9780226662237
Edward Marczewski, Hugo Steinhaus, On a certain distance of sets and the corresponding distance of functions Colloquium Mathematicum. ,vol. 6, pp. 319- 327 ,(1958) , 10.4064/CM-6-1-319-327