Searching in metric spaces by spatial approximation

By Gonzalo Navarro. 1999

Subfields: Information Retrieval & Search, Algorithms & Complexity

How researchers see this paper

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

In Information Retrieval & Search

In Algorithms & Complexity

Citations in the corpus

On The Marriage of Lp-norms and Edit Distance (2004, methodology): “In our experiments, we pick M-trees and OMNI-sequential as the strawman structures for comparison; MVP-trees and Sa-trees are not compared because they are main memory resident structures.”
Approximate Nearest Neighbor Search Small World Approach (2011, methodology): “Because it is impossible to determine exact Delaunay graph [26] (excluding the variant of the complete graph) we cannot avoid the existence of local minimums.”
Near neighbor searching with K nearest references (2015, background): “On the other hand, for sufficiently large ρ, the number of distance computations, even with the speedup of the SAT structure, becomes dominant and the search becomes slower.”
Effective Proximity Retrieval by Ordering Permutations (2008, background): “[8], [33], a set of centers is cho en and every other point is added to the group of its closest center.”
Searching in metric spaces (2001, methodology): “SAT The algorithm SAT (\Spatial Approximation Tree") [44] does not use pivots to split the set of candidate objects, but rather relies on \spatial" approximation.”
Approximate nearest neighbor algorithm based on navigable small world graphs (2014, methodology): “However, there are major drawbacks associated with the Delaunay graph: it requires some knowledge of metric space internal structure [8] and it suffers from the curse of dimensionality [7].”
Large Scale Nearest Neighbors Search Based on Neighborhood Graph (2013, methodology): “Neighborhood graph method: The neighborhood graph method organizes the data with a graph structure to connect data points, for example, Delaunay graph [20], relative neighborhood graph [21], and KNN graph [22].”
Navigating K-Nearest Neighbor Graphs to Solve Nearest Neighbor Searches (2010, background): “The quest for a proximity graph in a general metric space was deterred when it was proved in [1] that the degree of the graph is unbounded if only the distance information is used.”
Singleton indexes for nearest neighbor search (2016, methodology): “The legacy one by Navarro’s SAT [18] and the Distal SAT [8].”
Rank-Based Similarity Search: Reducing the Dimensional Dependence (2015, methodology): “This has spurred the development of search structures for more general metric spaces, such as the Multi-Vantage-Point Tree [7], the Geometric Near-neighbor Access Tree (GNAT) [9], Spatial Approximation Tree (SAT) [40], the M-tree [13], and (more recently) the Cover Tree (CT) [6].”
Nearest-Neighbor Searching and Metric Space Dimensions (2005, methodology): “In the metric-space setting, Navarro [Nav02] proposed a heuristic data structure with a similar but somewhat more complicated searching method.”
Query-driven iterated neighborhood graph search for large scale indexing (2012, background): “Various modiﬁcations have been done over local search to kick a solution out from a local optimum.”