PAC nearest neighbor queries: Approximate and controlled search in high-dimensional and metric spaces

171 citations recorded by the source corpus.

How researchers see this paper

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

Maximum inner-product search using cone trees (2012, background): “The hierarchical tree data structure provides a very intuitive extension to solve the problem approximately to gain efficiency [8, 32].”
Effective Proximity Retrieval by Ordering Permutations (2008, methodology): “Finally, there are approaches that combine approximation a nd probabilistic techniques, such as the PAC (probably approximately correct) method [17].”
Fast Exact Max-Kernel Search (2012, background): “These hierarchical indexing schemes lend easily to intuitive branch-and-bound algorithms for efficient solutions (especially approximate solutions [18, 19]).”
Zero-shot Learning with Semantic Output Codes (2009, result): “Much of our nearest-neighbor analysis parallels the work of Ciaccia and Patella (2000).”
Learning Transferable Knowledge Through Embedding Spaces (2019, methodology): “The latter distribution has been computed by Ciaccia and Patella [78] as: Wẑ(t) = 1− ( 1−Rẑ(t) )n , (3.12) where n is the number of points drawn from the distribution P .”
The properties of high-dimensional data spaces: implications for exploring gene and protein expression data (2008, methodology): “In many studies, investigators perform a similarity search of the data space that is effectively a nearest neighbour (distance) query in Euclidean spac”
The Concentration of Fractional Distances (2007, unknown): “NNs [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17],”