Navigating nets: simple algorithms for proximity search

By Robert Krauthgamer, James R. Lee. ACM-SIAM Symposium on Discrete Algorithms, 2004

405 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/09703995833819dbd3eb3905b3f7f632b956e23a

How researchers see this paper

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

Citations in the corpus

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].”
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 construction of nets in low dimensional metrics, and their applications (2004, background): “The doubling constant of metric space M is the maximum, over all balls b in the metric space M, of the minimum number of balls needed to cover b, using balls with half the radius of b.”
Learning Multi-View Neighborhood Preserving Projections (2011, methodology): “Approximate nearest neighbor techniques are applied instead, and these are available mainly for queries with respect to the Euclidean distance, e.g. randomized neighborhood graphs (Arya et al., 1998), navigating nets (Krauthgamer & Lee, 2004) and cover trees (Beygelzimer et al., 2006).”
Fast, smooth and adaptive regression in metric spaces (2009, methodology): “The navigating-nets of [17] implement the same basic idea.”
Randomized Partition Trees for Nearest Neighbor Search (2015, background): “The navigating net [15], given data from a metric space of doubling dimension do, has size O(2O(do)n) and gives a (1 + )-approximate answer to queries in time O(2O(do) log n + (1/ )O(do)); the crucial advantage here is that doubling dimension, defined in Sect.”
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions (2006, background): “In fact, for large enough d, in theory or in practice , they often provide little improvement over a linear time algorithm that compares a query to each point from the database.”
Random projection trees and low dimensional manifolds (2008, unknown): “3. ez and ez′ both lie within distance 3Δ/√D of ex0.”
Rank-Based Similarity Search: Reducing the Dimensional Dependence (2015, methodology): “Subsequently, Krauthgamer and Lee [34] proposed a structure called a Navigating Net , consisting of a hierarchy of progressively ﬁner " -nets of S , with pointers that allow navigation from one level of the hierarchy to the next.”
Fast k-Nearest Neighbour Search via Prioritized DCI (2017, methodology): “Due to the difﬁculties of devising efﬁcient algorithms for the exact version of the problem, there has been extensive work on approximate algorithms.”
Online Action Recognition via Nonparametric Incremental Learning (2014, methodology): “For example, [26] embeds S in a tree where nearest neighbour queries and updates can be performed in time O(ln |S|) —see also [25].”
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.”
Nearest-Neighbor Searching and Metric Space Dimensions (2005, methodology): “This is roughly the approach taken by Krauthgamer and Lee[KL04], with additional refinements; they obtain also dynamic data structures that support insertion and deletion of sites.”
Linear-time Algorithms for Pairwise Statistical Problems (2009, methodology): “In this paper, we extend the existing wo rk [6, 1, 18, 19] to provide algorithms for two important instances of the all-query problem (namel y al -nearest-neighbor and all-kernelsummation) and obtain for the first time a linear runtime boun d for dual-tree algorithms for the more general bichromatic”
DBSCAN Revisited, Revisited (2017, background): “In most applications, Δ = poly( |S |), hence log Δ = O (logn)” [28].”
Randomized partition trees for exact nearest neighbor search (2013, unknown): “The navigating net (Krauthgamer and Lee, 2004), given data from a metric space of doubling dimension d o , has size O (2 O ( d o ) n ) and gives a Figure 1: Left: A k -d tree, with axis-parallel splits.”