Nearest neighbor queries in metric spaces

DOI10.1007/PL00009449zbMATH Open0994.54501MaRDI QIDQ1293352FDOQ1293352

Authors: Kenneth L. Clarkson 

Publication date: 13 October 2002

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 1559576
• scientific article; zbMATH DE number 437556
• scientific article; zbMATH DE number 437552

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Metric spaces, metrizability (54E35)

Cited In (68)

• The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs
• Labeled nearest neighbor search and metric spanners via locality sensitive orderings
• Nearest-neighbor-preserving embeddings
• Online capacity maximization in wireless networks
• Determining Cosine Similarity Neighborhoods by Means of the Euclidean Distance
• On the angle restricted nearest neighbor problem
• Linear-size approximations to the Vietoris-Rips filtration
• Self-organizing flows in social networks
• A Modern View on Stability of Approximation
• On reporting the \(L_1\) metric closest pair in a query rectangle
• Simultaneous nearest neighbor search
• An O(n log n) algorithm for the all-nearest-neighbors problem
• Small hop-diameter sparse spanners for doubling metrics
• Approximate similarity search: a multi-faceted problem
• Chromatic nearest neighbor searching: A query sensitive approach
• Automata, Languages and Programming
• Self-organizing flows in social networks
• Approximating nearest neighbor distances
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Least Cost for Proximity Searching in Metric Spaces
• Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces
• Metric spaces with expensive distances
• Stochastic closest-pair problem and most-likely nearest-neighbor search in tree spaces
• Nearest neighbor classification with excluding assumption.
• Title not available (Why is that?)
• Randomized approaches for nearest neighbor search in metric space when computing the pairwise distance is extremely expensive
• Probabilistic proximity searching algorithms based on compact partitions
• A reverse nearest neighbor search algorithm in metric space
• Space exploration via proximity search
• Space exploration via proximity search
• Simple and fast nearest neighbor search
• New upper bounds for neighbor searching
• Title not available (Why is that?)
• Satisfying general proximity/similarity queries with metric trees
• Title not available (Why is that?)
• Nearest Neighbor Search
• A note on the nearest neighbor in growth-restricted metrics
• New Doubling Spanners: Better and Simpler
• Title not available (Why is that?)
• Packing and covering with balls on Busemann surfaces
• Iterative denoising
• Making doubling metrics geodesic
• Probabilistic proximity search: Fighting the curse of dimensionality in metric spaces.
• Efficient distance computation in configuration space
• Space-Time Tradeoffs for Proximity Searching in Doubling Spaces
• Randomized partition trees for nearest neighbor search
• Smoothed analysis of probabilistic roadmaps
• Flip distance to some plane configurations
• A family of pairwise multi-marginal optimal transports that define a generalized metric
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• Title not available (Why is that?)
• The Metric Nearness Problem
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• Reducing non-determinism of \(k\)-NN searching in non-ordered discrete data spaces
• SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS
• A unified PTAS for prize collecting TSP and Steiner tree problem in doubling metrics
• Approximate nearest neighbor search in metrics of planar graphs
• Dual‐tree fast exact max‐kernel search
• Flip distance to some plane configurations
• A simple framework for the generalized nearest neighbor problem
• The black-box complexity of nearest-neighbor search
• Can nearest neighbor searching be simple and always fast?
• Nearest-neighbor searching under uncertainty. II
• Extending range queries and nearest neighbors
• Partially specified nearest neighbor search
• On efficient \( k\)-optimal-location-selection query processing in metric spaces

This page was built for publication: Nearest neighbor queries in metric spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1293352)