Closest pair problems in very high dimensions

DOI10.1007/978-3-540-27836-8_66MaRDI QIDQ5466513zbMATH OpenOpenAlexFDO

Authors Ohad Lipsky, Ely Porat, Piotr Indyk, Moshe Lewenstein

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Dominance product and high-dimensional closest pair under \(L_\infty\)
• scientific article; zbMATH DE number 794264
• Approximate closest-point queries in high dimensions
• Exact \(L_{\infty}\) nearest neighbor search in high dimensions
• scientific article; zbMATH DE number 1559575

Cited in

(26)

• Approximate closest-point queries in high dimensions
• Two-dimensional closest pair problem: a closer look
• On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
• Approximate matching in the \(L_{\infty }\) metric
• \(L_{1}\) pattern matching lower bound
• Reductions among high dimensional proximity problems
• Reporting neighbors in high-dimensional Euclidean space
• Closest periodic vectors in L_p spaces
• On the complexity of closest pair via polar-pair of point-sets
• On Approximating the Average Distance Between Points
• Approximate k-closest-pairs with space filling curves
• On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
• scientific article; zbMATH DE number 794264 (Why is no real title available?)
• Brief announcement: Hamming distance completeness and sparse matrix multiplication
• Dynamic closest pairs — A probabilistic approach
• Hamming Distance Completeness
• On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
• On the complexity of closest pair via polar-pair of point-sets
• Dominance product and high-dimensional closest pair under \(L_\infty\)
• The Closest Pair Problem under the Hamming Metric
• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Exact \(L_{\infty}\) nearest neighbor search in high dimensions
• scientific article; zbMATH DE number 7053290 (Why is no real title available?)
• Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances
• Non-Boolean OMv: one more reason to believe lower bounds for dynamic problems
• Approximate k-closest-pairs in large high-dimensional data sets

This page was built for publication: Closest pair problems in very high dimensions

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