Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A. An optimal algorithm for approximate nearest neighbor searching, Proc. 5th Annu. ACM- SIAM Symp. Disc. AIg. (1994), 573-582.

Digital Library

Google Scholar

[5]

Beame, P., Fich, F. Optimal bounds for the predecessor problem, manuscript, }998.

Google Scholar

[6]

Bern, M. Approximate closest-point queries in high dimensions, Inform. Process. Lett., 45 (1993), 95-99.

Digital Library

Google Scholar

[7]

Borodin, A., Ostrovsky, R., Rabani, Y. Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems, Proc. 31st Annu. ACM Symp. Theory Comput. (i999).

Digital Library

Google Scholar

[8]

C~zaJs, F. Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering, Proc. 14th Annu. ACM Syrup. Comput. Geom. (1998), 222-230.

Digital Library

Google Scholar

[9]

Chan, T. Approximate nearest neighbor queries revisited, Proc. 13th Annu. ACM Symp. Comput. Geom. (1997), 352-358.

Digital Library

Google Scholar

[10]

Cha~etle, B. The Discrepancy Method: Randomness and Complexity, manuscript, to appear.

Google Scholar

[11]

Clarkson, K.L. A probabiIistic algorithm for the post o~ce problem, Proc. 17th Annu. ACM Symp. Theory Comput. (1985), 175-t84.9

Digital Library

Google Scholar

[12]

Clarkson, K.L. A randomized algorithm for closestpoint queries, SIAM J. Comput., 17 (1988), 830-847.

Digital Library

Google Scholar

[13]

Clarkson, K.L. An algorithm for approximate closest-point queries, Proc. 10th Annu. ACM Symp. Comput. Geom. l0 (1994), I60-164.

Digital Library

Google Scholar

[14]

Graham, R.L., Knuth, D.E., Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2rid ed., Addison-Wesley, 1994.

Digital Library

Google Scholar

[15]

Hoeffding, W. Probability inequalities for sums oj~ bounded random variables, J. Amer. Stat. Assoc., 58 (~a), ~a-ao.

Google Scholar

[16]

Indyk, P., Motwani, R. Approximate nearest neighbors: towards removing the curse of dimensionality, Proc. 30{h ACM Symp. Theory Comput. (1998), 604-613.

Digital Library

Google Scholar

[17]

Karchmer, M., Wigderson, A. Monotone circuits for connectivity require super-logarithmic depth, SIAM J. Disc. Math., 2 (t990).

Google Scholar

[18]

Kteinberg, J.M. Two algorithms for nearest neighbor search in high dimensions, Proc. 29th Annu. ACM Syrup. Theory Comput. (1997), 599-608.

Digital Library

Google Scholar

[19]

Kushilevit~z, E., Nisan, N. Communication Complexity, Cambridge University Press, 1997

Digital Library

Google Scholar

[20]

Kushitevitz, E., Ostrovsky, R., Rabani, Y. Efficient search for appro~mate nearest neighbor in highdimensional spaces, Proc. 30th Annu. AGM Symp. Theory Compu~. (1998), 614-623.

Digital Library

Google Scholar

[21]

Liniat, N., London, E., Rabinovitch, Y. The geometry of graphs and some of its algorithmic applications, Proc. 35th Annu. IEEE Symp. Found. Corn~ put. Sci. (1994), 577-591.

Google Scholar

[22]

Miltersen, P.B. Lower bounds for union-split-find related problems on random access machines, Proc. 26th Annu. ACM Symp. Theory Comput. (1994), 625-634.

Digital Library

Google Scholar

[23]

Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A. On data structures and asymmetric communication complexity, Proc. 27th Annu. A CM Symp. Theory Comput. (t995), 103-111.

Digital Library

Google Scholar

[24]

Motwani, R., Raghawn, P. Randomized Algorithms, Cambridge University Press, 1995.

Digital Library

Google Scholar

[25]

Xiao, B. New Bounds in Cell Probe Model, PhD Thesis, UC San Diego, 1992.

Digital Library

Google Scholar

[26]

Ygnilos, P.N. Data structures and algorithms for nearest neighbor search in general metric spaces, Proc. 2nd Annual ACM-SIAM Symp. Disc. Alg. (~s), s~-a:~.

Digital Library

Google Scholar

[27]

Yao, A.C. Should tables be sorted?, J. ACM, 28 (~gs~), 6~$-6~s.

Digital Library

Google Scholar

Cited By

View all

Andoni ALaarhoven TRazenshteyn IWaingarten EKlein P(2017)Optimal hashing-based time-space trade-offs for approximate near neighborsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039690(47-66)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039690
Alman JWilliams R(2015)Probabilistic Polynomials and Hamming Nearest NeighborsProceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2015.18(136-150)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1109/FOCS.2015.18
Sun YWang WQin JZhang YLin X(2014)SRSProceedings of the VLDB Endowment10.14778/2735461.27354628:1(1-12)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.14778/2735461.2735462
Show More Cited By

Index Terms

A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation

Recommendations

A Fast Approximate Nearest Neighbor Search Algorithm in the Hamming Space

A fast approximate nearest neighbor search algorithm for the (binary) Hamming space is proposed. The proposed Error Weighted Hashing (EWH) algorithm is up to 20 times faster than the popular locality sensitive hashing (LSH) algorithm and works well even ...
Fast k-Nearest Neighbor Searching in Static Objects

The k-nearest neighbor searching is a classical problem that has been seriously studied, due to its many important applications. The paper proposes an efficient algorithm to search the k-nearest neighbors for static objects. Since locations of static ...
A strong lower bound for approximate nearest neighbor searching

We prove a lower bound of <i>d</i><sup>1-o(1)</sup> on the query time for any deterministic algorithms that solve approximate nearest neighbor searching in Yao's cell probe model. Our result greatly improves the best previous lower bound for this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

May 1999

790 pages

ISBN:1581130678

DOI:10.1145/301250

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC99

Sponsor:

SIGACT

STOC99: ACM Symposium on Theory of Computing

May 1 - 4, 1999

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
353
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)4

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Andoni ALaarhoven TRazenshteyn IWaingarten EKlein P(2017)Optimal hashing-based time-space trade-offs for approximate near neighborsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039690(47-66)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039690
Alman JWilliams R(2015)Probabilistic Polynomials and Hamming Nearest NeighborsProceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2015.18(136-150)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1109/FOCS.2015.18
Sun YWang WQin JZhang YLin X(2014)SRSProceedings of the VLDB Endowment10.14778/2735461.27354628:1(1-12)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.14778/2735461.2735462
Borodin A(2013)Computing (and Life) Is All about TradeoffsSpace-Efficient Data Structures, Streams, and Algorithms10.1007/978-3-642-40273-9_9(112-132)Online publication date: 2013
https://doi.org/10.1007/978-3-642-40273-9_9
Lemire DKaser OGutarra E(2012)Reordering rows for better compressionACM Transactions on Database Systems10.1145/2338626.233863337:3(1-29)Online publication date: 6-Sep-2012
https://dl.acm.org/doi/10.1145/2338626.2338633
Kapralov MPanigrahy R(2012)NNS lower bounds via metric expansion for lProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part I10.1007/978-3-642-31594-7_46(545-556)Online publication date: 9-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31594-7_46
Pintus PPetrou M(2011)Relational space classification for malaria diagnosisPattern Analysis & Applications10.1007/s10044-011-0224-z14:3(261-272)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1007/s10044-011-0224-z
Panigrahy RTalwar KWieder U(2010)Lower Bounds on Near Neighbor Search via Metric ExpansionProceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science10.1109/FOCS.2010.82(805-814)Online publication date: 23-Oct-2010
https://dl.acm.org/doi/10.1109/FOCS.2010.82
Patrascu M(2008)(Data) STRUCTURESProceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science10.1109/FOCS.2008.69(434-443)Online publication date: 25-Oct-2008
https://dl.acm.org/doi/10.1109/FOCS.2008.69
Panigrahy RTalwar KWieder U(2008)A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial MatchProceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science10.1109/FOCS.2008.68(414-423)Online publication date: 25-Oct-2008
https://dl.acm.org/doi/10.1109/FOCS.2008.68
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Index Terms

Recommendations

A Fast Approximate Nearest Neighbor Search Algorithm in the Hamming Space

Fast k-Nearest Neighbor Searching in Static Objects

A strong lower bound for approximate nearest neighbor searching