Nearest-Neighbor Searching and Metric Space Dimensions

By Kenneth L. Clarkson. 2005

246 citations recorded by the source corpus.

Subfields: Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition, Evaluation & Benchmarks, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

In Evaluation & Benchmarks

In Signal Processing

Citations in the corpus

Maximum inner-product search using cone trees (2012, methodology): “MAXIMUM INNER-PRODUCT SEARCH Numerous techniques exists for nearest-neighbor search in Euclidean metric space (see surveys like [9]).”
Fast Exact Max-Kernel Search (2012, methodology): “Extensions for approximate max-kernel search are also presented.”
Bisimulation Metrics for Continuous Markov Decision Processes (2011, background): “The particular performance will depend on the structure of a given space—and this in turn can be represented by a number of proposed measures of metric space dimension [10].”
Efficient retrieval of recommendations in a matrix factorization framework (2012, unknown): “Finding the best match with respect to the Euclidean (or more generally Lp) distance is the widely studied problem of nearest-neighbor search in metric spaces [4].”
Locality-sensitive binary codes from shift-invariant kernels (2009, unknown): “For example, if X is an lp ball in R, thendX = O(D); if X is a d-dimensional hyperplane inR, then dX = O(d) [2].”
Randomized Partition Trees for Nearest Neighbor Search (2015, background): “For the convenience of the reader, and to resolve minor discrepancies between our notation and Clarkson's, the brief proof of this fact is reproduced in the appendix (Lemma 7).”
Maximally Persistent Cycles in Random Geometric Complexes (2015, background): “"-nets are a standard construction in computational geometry and exist for any metric space [25].”
Fast, smooth and adaptive regression in metric spaces (2009, unknown): “1 of [9]) will come in handy: consider r1 and r2 such that r1/r2 is a power of 2, and let B ⊂ X be a ball of radius r1; since X has Assouad dimension d, the smallest r2-cover of B is of size at most (r1/r2), and the largest r2-packing of B is of size at most (r1/r2).”
A learning framework for nearest neighbor search (2007, background): “Nevertheless, we can examine the generalization properties of a data structure learned from one of these classes.”
Active Constraints/Virtual Fixtures: A Survey (2014, background): “the reader is guided to [67]–[70] if more detail is required.”
The Five Factor Model of personality and evaluation of drug consumption risk (2015, background): “The basic concept of KNN is: the class of an object is the class of the majority of its k-nearest neighbours [7].”
Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection (2009, unknown): “Keywords: Nearest Neighbors Graph, High Dimensional Data, Divide and Conquer, Lanczos Algorithm, Spectral Method”