Article

Better algorithms for high-dimensional proximity problems via asymmetric embeddings

Author:

Piotr IndykAuthors Info & Claims

SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 539 - 545

Published: 12 January 2003 Publication History

Abstract

In this paper we give several results based on randomized embeddings of l₂ into l_∞(or "l_∞-like") spaces. Our first result is a (1 + ε)-distortion asymmetric embedding of n points in l₂ into l_∞ with polylog(n) dimension, for any 1 + ε. This gives the first known O(1)- approximate nearest neighbor algorithm with fast query time and almost polynomial space for a product of Euclidean norms, a common generalization of both l₂ and l_∞ norms. Our embedding also clarifies the relative complexity of approximate nearest neighbor in l₂ and l_∞ spaces.Our second result in a (1 + ε)-approximate algorithm for the diameter of n points in l^d₂, running in time Õ(dn^1+l/(1+ε)²); the algorithm is fully dynamic. This improves several previous algorithms for this problem (see Table 1 for more information).

References

[1]

{AGGM98} P.K. Agarwal, A. Gionis, L. Guibas, and R. Motwani. Rank-based similarity searching. Manuscript, 1998.

[2]

{AMS92} P.K. Agarwal, J. Matoušek, and S. Suri. Farthest neighbors, maximum spanning trees and related problems in higher dimensions. Computational Geometry: Theory and Applications, 1(4):189--201, 1992.

Digital Library

[3]

{AV99} R. I. Arriaga and S. Vempala. An algorithmic theory of learning: Robust concepts and random projection. Proceedings of the Symposium on Foundations of Computer Science, 1999.

Digital Library

[4]

{BOR99a} A. Borodin, R. Ostrovsky, and Y. Rabani. Lower bounds for high dimensional nearest neighbor search and related problems. Proceedings of the Symposium on Theory of Computing, 1999.

Digital Library

[5]

{BOR99b} A. Borodin, R. Ostrovsky, and Y. Rabani. Subquadratic approximation algorithms for clustering problems in high dimensional spaces. Proceedings of the Symposium on Theory of Computing, 1999.

Digital Library

[6]

{Das99} S. Dasgupta. Learning mixtures of gaussians. Proceedings of the Symposium on Foundations of Computer Science, pages 634--644, 1999.

Digital Library

[7]

{EK89} O. Egecioglu and B. Kalantari. Approximating the diameter of a set of points in the euclidean space. Information Processing Letters, 32:205, 1989.

Digital Library

[8]

{Epp95} D. Eppstein. Dynamic euclidean minimum spanning trees and extrema of binary functions. Disc. Comp. Geom., 13:111--122, 1995.

[9]

{Fag96} R. Fagin. Combining fuzzy information from multiple systems. Proceedings of the ACM Symposium on Principles of Database Systems, pages 216--227, 1996.

Digital Library

[10]

{Fag98} R. Fagin. Fuzzy queries in multimedia database systems (invited paper). Proceedings of the ACM Symposium on Principles of Database Systems, 1998.

Digital Library

[11]

{FCI99} M. Farach-Colton and P. Indyk. Approximate nearest neighbor algorithms for hausdorff metrics via embeddings. Proceedings of the Symposium on Foundations of Computer Science, 1999.

Digital Library

[12]

{Fel91} W. Feller. An Introduction to Probability Theory and its Applications. John Wiley & Sons, NY, 1991.

[13]

{FP99} D. Finocchiaro and M. Pellegrini. On computing the diameter of a point set in high dimensional euclidean space. Proceedings of the European Symposium on Algorithms, 1999.

Digital Library

[14]

{GBT84} H. N. Gabow, J. L. Bentley, and R. E. Tarjan. Scaling and related techniques for geometry problems. Proceedings of the Symposium on Theory of Computing, pages 135--143, 1984.

Digital Library

[15]

{GIV01} A. Goel, P. Indyk, and K. Varadarajan. Reductions among high-dimensional geometric problems. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2001.

Digital Library

[16]

{IM98} P. Indyk and R. Motwani. Approximate nearest neighbor: towards removing the curse of dimensionality. Proceedings of the Symposium on Theory of Computing, 1998.

Digital Library

[17]

{Ind98} P. Indyk. On approximate nearest neighbors in l∞ norm. Journal of Computer and System Sciences, to appear. Preliminary version appeared in Proceedings of the Symposium on Foundations of Computer Science, 1998.

Digital Library

[18]

{Ind00a} P. Indyk. Dimensionality reduction techniques for proximity problems. Proceedings of the Ninth ACM-SIAM Symposium on Discrete Algorithms, 2000.

Digital Library

[19]

{Ind00b} P. Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. Proceedings of the Symposium on Foundations of Computer Science, 2000.

Digital Library

[20]

{Ind02} P. Indyk. Approximate nearest neighbor algorithms for frechet metric via product metrics. Symposium on Computational Geometry, 2002.

Digital Library

[21]

{JS82} W.B. Johnson and G. Schechtman. Embedding lmp into ln1. Acta Mathematica, 149:71--85, 1982.

[22]

{Kle97} J. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 1997.

Digital Library

[23]

{KOR98} E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. Proceedings of the Thirtieth ACM Symposium on Theory of Computing, pages 614--623, 1998.

Digital Library

[24]

{LM} J. Lindenstrauss and V.D. Milman. Local theory of normed spaces and convexity. Handbook of convex geometry, B:1149--1220.

[25]

{Mat96} J. Matoušek. On the distortion required for embedding finite metric spaces into normed spaces. Israel Journal of Mathematics, 93:333--344, 1996.

[26]

{MS00} S. Muthukrishnan and C. Sahinalp. Approximate sequence nearest neighbors. Proceedings of the Symposium on Theory of Computing, 2000.

Cited By

Aumüller MChristiani TPagh RSilvestri FVan den Bussche JArenas M(2018)Distance-Sensitive HashingProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3196959.3196976(89-104)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3196959.3196976
Rubinstein ADiakonikolas IKempe DHenzinger M(2018)Hardness of approximate nearest neighbor searchProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188916(1260-1268)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188916
Braverman VFrahling GLang HSohler CYang L(2017)Clustering high dimensional dynamic data streamsProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305381.3305441(576-585)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.5555/3305381.3305441
Show More Cited By

Index Terms

Better algorithms for high-dimensional proximity problems via asymmetric embeddings
1. Applied computing
  1. Physical sciences and engineering
    1. Mathematics and statistics
2. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical analysis
    1. Numerical analysis

Recommendations

Parallel algorithms for proximity problems
Lossless Prioritized Embeddings

Given metric spaces $(X,d)$ and $(Y,\rho)$ and an ordering $x_1,x_2,\ldots,x_n$ of $(X,d)$, an embedding $f: X \rightarrow Y$ is said to have a prioritized distortion $\alpha(\cdot)$, for a function $\alpha(\cdot)$, if for any pair $x_j,x'$ of distinct ...
Ultra-low-dimensional embeddings for doubling metrics
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

We consider the problem of embedding a metric into low-dimensional Euclidean space. The classical theorems of Bourgain and of Johnson and Lindenstrauss imply that any metric on n points embeds into an O(log n)-dimensional Euclidean space with O(log n) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms

January 2003

891 pages

ISBN:0898715385

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 12 January 2003

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
551
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Aumüller MChristiani TPagh RSilvestri FVan den Bussche JArenas M(2018)Distance-Sensitive HashingProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3196959.3196976(89-104)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3196959.3196976
Rubinstein ADiakonikolas IKempe DHenzinger M(2018)Hardness of approximate nearest neighbor searchProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188916(1260-1268)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188916
Braverman VFrahling GLang HSohler CYang L(2017)Clustering high dimensional dynamic data streamsProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305381.3305441(576-585)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.5555/3305381.3305441
Pagh RSilvestri FSivertsen JSkala M(2017)Approximate furthest neighbor with application to annulus queryInformation Systems10.1016/j.is.2016.07.00664:C(152-162)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.is.2016.07.006
Agarwal PSharathkumar R(2015)Streaming Algorithms for Extent Problems in High DimensionsAlgorithmica10.1007/s00453-013-9846-472:1(83-98)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1007/s00453-013-9846-4
Pagh RSilvestri FSivertsen JSkala M(2015)Approximate Furthest Neighbor in High DimensionsProceedings of the 8th International Conference on Similarity Search and Applications - Volume 937110.1007/978-3-319-25087-8_1(3-14)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-25087-8_1
Agarwal PSharathkumar RCharikar M(2010)Streaming algorithms for extent problems in high dimensionsProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873721(1481-1489)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.5555/1873601.1873721
Bagchi AChaudhary AEppstein DGoodrich M(2007)Deterministic sampling and range counting in geometric data streamsACM Transactions on Algorithms10.1145/1240233.12402393:2(16-es)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.1145/1240233.1240239
Chan T(2006)Faster core-set constructions and data-stream algorithms in fixed dimensionsComputational Geometry: Theory and Applications10.5555/1646483.164657835:1-2(20-35)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.5555/1646483.1646578
Regev ORosen RKleinberg J(2006)Lattice problems and norm embeddingsProceedings of the thirty-eighth annual ACM symposium on Theory of Computing10.1145/1132516.1132581(447-456)Online publication date: 21-May-2006
https://dl.acm.org/doi/10.1145/1132516.1132581
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten