Finding nearest neighbors in growth-restricted metrics

By David R Karger, M. Ruhl. Symposium on the Theory of Computing, 2002

403 citations recorded by the source corpus.

Subfields: Computer Graphics and Computer-Aided Design, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/9fe773cedca17748a2552623d11ee74486c9fe5e

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 Networks and Communications

In Signal Processing

Citations in the corpus

Sparse multidimensional scaling using land-mark points (2004, positive): “Ttandard methods have complexity P(N2), but there are more sophisticated techniques [25, 26] which give an expected bound of cO(1)(pN + N logN log logN) for data sets with an expansion coefficient of c.”
Randomized Partition Trees for Nearest Neighbor Search (2015, methodology): “Under this condition, there is a scheme [13] that gives exact answers to nearest neighbor queries in time O(23do log n), using a data structure of size O(23do n).”
DBSCAN Revisited, Revisited (2017, methodology): “For example, Beygelzimer et al. [10] introduce the cover tree and claimO (logn) query and O (n · logn) construction time, and attribute the same to Karger and Ruhl [27], Hildrum et al. [23], and navigating nets [28] with different constant factors.”
Randomized partition trees for exact nearest neighbor search (2013, neutral): “Under this condition, Karger and Ruhl (2002) have a scheme that gives exact answers to nearest neighbor queries in time O (2 3 d o log n ), using a data structure of size O (2 3 d o n ).”
Linear-time Algorithms for Pairwise Statistical Problems (2009, methodology): “Under their definition of intrinsic dimension, Karger & Ruhl [6] describe a randomized algorithm withO(logN) time per query for nearest neighbor search for lowintrinsic-dimensional data.”
Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifold (2003, background): “Recent work by Karger and Ruhl (2002) specifically addresses the problem of computing nearest neighbors for data on low dimensional manifolds.”
Nearest-Neighbor Searching and Metric Space Dimensions (2005, methodology): “However, the -net scheme roughly follows the ideas of Krauthgamer and Lee[KL04], while the empirical doubling measure (growth-restricted) scheme follows ideas of an earlier paper by Karger and Ruehl[KR02].”
Rank-Based Similarity Search: Reducing the Dimensional Dependence (2015, background): “In [31], Karger and Ruhl introduced a measure of intrinsic dimensionality as a means of analyzing the performance of a local search strategy for handling nearest neighbor queries.”
Fast approximate similarity search based on degree-reduced neighborhood graphs (2011, methodology): “Fast Approximate Similarity Search Based on Degree-Reduced Neighborhood Graphs Kazuo Aoyama NTT Communication Science Kazumi Saito University of Shizuoka Hiroshi Sawada NTT Communication Science Laboratories, NTT Corporation 52-1, Yada, Suruga-ku, Laboratories, NTT Corporation 2-4, Hikaridai, Seik”
Fast k-Nearest Neighbour Search via Prioritized DCI (2017, background): “Examples include navigating nets (Krauthgamer & Lee, 2004), cover trees (Beygelzimer et al., 2006) and rank cover trees (Houle & Nett, 2015), which maintain sets of subsampled data points at different levels of granularity and descend through the hierarchy of neighbourhoods of decreasing radii…”
Graph cluster randomization: network exposure to multiple universes (2013, background): “…space, one can use the locations of vertices in the embedding to carve up the space into clusters directly; the point, as in work on the nearest-neighbor problem [10], is to control this carving-up at a graph-theoretic level rather than a geometric one, and this is what our technique does.”
Locality-sensitive hashing scheme based on p-stable distributions (2004, background): “Efficient nearest neighbor algorithms for data sets with polynomial growth properties in general metr ics have been recently a focus of several papers [9, 21, 23].”
PIC: practical Internet coordinates for distance estimation (2004, methodology): “This can be done in several ways, e.g., using expanding ring multicast or the algorithms described in [15] [28] [2] [3] [12].”
Fast construction of nets in low dimensional metrics, and their applications (2004, background): “…F.2.2 [Analysis of algorithms and problem complexity]: Geometrical problems and computations General Terms Algorithms, Theory Keywords Doubling metrics, approximate nearest neighbor search, compact representation scheme, approximate distance oracle, well separated pair decomposition, spanners”
From Small-World Networks to Comparison-Based Search (2011, methodology): “Our work can be seen as an extension of earlier work [10], [11], [8] considering the NNS problem for objects embedded in a metric space with a small intrinsic dimension.”
Meridian: a lightweight network location service without virtual coordinates (2005, background): “The time and space complexity of two techniques are discussed in [27] and [30], but these techniques focus exclusively on finding the nearest neighbor, apply only to Internet latencies modeled by growthconstrained metrics, and have not been evaluated with a large scale”