Lower bounds for high dimensional nearest neighbor search and related problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for high dimensional nearest neighbor search and related problems

Full text

Pdf (858 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 312 - 321

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Allan Borodin	Department of Computer Science, University of Toronto
Rafail Ostrovsky	Bell Communication Research, MCC-1C365B, 445 South Street, Morristown, NJ
Yuval Rabani	Computer Science Department, Technion--IIT, Haifa 32000, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 37, Citation Count: 18

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301330 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.517-526, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129763]
	2	M. Ajtai. A lower bound for finding predecessors in Yao's cell probe model. Combinatorica, 8:235- ~47, 1988.
	3	Sunil Arya , David M. Mount, Approximate nearest neighbor queries in fixed dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.271-280, January 25-27, 1993, Austin, Texas, United States
	4	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
	5	Paul Beame , Michael Saks , Jayram S. Thathachar, Time-Space Tradeoffs for Branching Programs, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.254, November 08-11, 1998
	6	Jeffrey S. Beis , David G. Lowe, Shape Indexing Using Approximate Nearest-Neighbour Search in High-Dimensional Spaces, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.1000, June 17-19, 1997
	7	Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
	8	Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
	9	Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	10	Marshall Bern, Approximate closest-point queries in high dimensions, Information Processing Letters, v.45 n.2, p.95-99, Feb. 26, 1993 [doi>10.1016/0020-0190(93)90222-U]
	11	A. Chakrabaxti, B. Chazelle, B. Gum, A. Lvov. A good neighbor is hard to find. These Proceedings.
	12	Timothy M. Chan, Approximate nearest neighbor queries revisited, Proceedings of the thirteenth annual symposium on Computational geometry, p.352-358, June 04-06, 1997, Nice, France [doi>10.1145/262839.263001]
	13	B. Chazelle. Private communication.
	14	Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
	15	Kenneth L. Clarkson, An algorithm for approximate closest-point queries, Proceedings of the tenth annual symposium on Computational geometry, p.160-164, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177609]
	16	S. Deerwester, S.T. Dumais, G.W. Furnas, T.K. Landauer, and R. tIarshman. Indexing by latent semantic analysis. J. Amer. Soc. lnfo. $ci., 41(6):391-407, 1990.
	17	D. Dobkin and R. Lipton. Multidimensional search problems. SIAM J. Comput., 5:181-186, 1976.
	18	D. Dolev, Y. Harari, and M. Pumas. Finding'the neighborhood of a query in a dictionary. In Proc. of ~nd ISTC$, 1993.
	19	Danny Dolev , Yuval Harari , Nathan Linial , Noam Nisan , Michal Parnas, Neighborhood preserving hashing and approximate queries, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.251-259, January 23-25, 1994, Arlington, Virginia, United States
	20	J. Erickson. New lower bounds for Hopcroft's problem. Discrete Comput. ~eom., 16:389-418, 1996.
	21	Ronald Fagin, Fuzzy queries in multimedia database systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.1-10, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275488]
	22	Myron Flickner , Harpreet Sawhney , Wayne Niblack , Jonathan Ashley , Qian Huang , Byron Dom , Monika Gorkani , Jim Hafner , Denis Lee , Dragutin Petkovic , David Steele , Peter Yanker, Query by Image and Video Content: The QBIC System, Computer, v.28 n.9, p.23-32, September 1995 [doi>10.1109/2.410146]
	23	Michael L. Fredman, A Lower Bound on the Complexity of Orthogonal Range Queries, Journal of the ACM (JACM), v.28 n.4, p.696-705, Oct. 1981 [doi>10.1145/322276.322281]
	24	M.L. Fredman. Lower bounds on the complexity of some optimal data structures. SIAM J. Computing, I0:1-10, 198i
	25	M.L. Fredman and D.J. Volper. The complexity of partial match retrieval in a dynamic setting. Journal of Algorithms, 3:68-78, 1982.
	26	D. Grigoriev, Randomized complexity lower bounds, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.219-223, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276745]
	27	T. H astie and R. Tibshirani. Discriminant adaptive nearest neighbor classification. In Is! International Conf. on Knowledge Discovery and Data Mining, 1995.
	28	Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou, On the analysis of indexing schemes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.249-256, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263688]
	29	P. Indyk, On Approximate Nearest Neighbors in Non-Euclidean Spaces, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.148, November 08-11, 1998
	30	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
	31	Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258653]
	32	Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
	33	Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
	34	Jiří Matoušek, Reporting points in halfspaces, Proceedings of the 32nd annual symposium on Foundations of computer science, p.207-215, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185370]
	35	S. Meiser, Point location in arrangements of hyperplanes, Information and Computation, v.106 n.2, p.286-303, Oct. 1993 [doi>10.1006/inco.1993.1057]
	36	Peter Bro Miltersen, The Bit Probe Complexity Measure Revisited, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.662-671, February 25-27, 1993
	37	Peter Bro Miltersen, Lower bounds for union-split-find related problems on random access machines, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.625-634, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195415]
	38	Peter Bro Miltersen, On the cell probe complexity of polynomial evaluation, Theoretical Computer Science, v.143 n.1, p.167-174, May 29, 1995
	39	Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.103-111, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225093]
	40	A. Pentland, R.W. Picard, and S. Sclaroff. Photobook: tools for content-based manipulation of image databases. In Proc. $PIE Conf. on Storage and Retrieval of Image and Video Databases lI, 1994.
	41	R. Rivest. Partial-match retrieval algorithms. SIAM J. Comput., 5:19-50, 1976.
	42	Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	43	A.W.M. Smeulders and R. Jain (eds). Proc. 1st Workshop on Image Databases and Multi-Media Search, 1996.
	44	Bing Xiao, New bounds in cell probe model, University of California at San Diego, La Jolla, CA, 1992
	45	Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]
	46	A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]

CITED BY 18

	Omer Barkol , Yuval Rabani, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, Journal of Computer and System Sciences, v.64 n.4, p.873-896, June 2002
	Stephen Alstrup , Thore Husfeldt , Theis Rauhe, A cell probe lower bound for dynamic nearest-neighbor searching, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.779-780, January 07-09, 2001, Washington, D.C., United States
	Amit Chakrabarti , Bernard Chazelle , Benjamin Gum , Alexey Lvov, A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.305-311, May 01-04, 1999, Atlanta, Georgia, United States
	Changzhou Wang , X. Sean Wang, Supporting subseries nearest neighbor search via approximation, Proceedings of the ninth international conference on Information and knowledge management, p.314-321, November 06-11, 2000, McLean, Virginia, United States
	Peter N. Yianilos, Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.361-370, January 09-11, 2000, San Francisco, California, United States
	T. S. Jayram , Subhash Khot , Ravi Kumar , Yuval Rabani, Cell-probe lower bounds for the partial match problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Changzhou Wang , Xiaoyang Sean Wang, High-dimensional nearest neighbor search with remote data centers, Knowledge and Information Systems, v.4 n.4, p.440-465, October 2002
	Piotr Indyk, Better algorithms for high-dimensional proximity problems via asymmetric embeddings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Flip Korn , Bernd-Uwe Pagel , Christos Faloutsos, On the 'Dimensionality Curse' and the 'Self-Similarity Blessing', IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.96-111, January 2001
	Paul Beame , Erik Vee, Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Ding Liu, A strong lower bound for approximate nearest neighbor searching, Information Processing Letters, v.92 n.1, p.23-29, 16 October 2004
	Rina Panigrahy, Entropy based nearest neighbor search in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1186-1195, January 22-26, 2006, Miami, Florida
	T. S. Jayram , Subhash Khot , Ravi Kumar , Yuval Rabani, Cell-probe lower bounds for the partial match problem, Journal of Computer and System Sciences, v.69 n.3, p.435-447, November 2004
	A. M. Sokolov, Vector representations for efficient comparison and search for similar strings, Cybernetics and Systems Analysis, v.43 n.4, p.484-498, July 2007
	Nir Ailon , Bernard Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Omer Barkol , Yuval Rabani, Tighter bounds for nearest neighbor search and related problems in the cell probe model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.388-396, May 21-23, 2000, Portland, Oregon, United States
	Hyunjung Shin , Sungzoon Cho, Neighborhood Property--Based Pattern Selection for Support Vector Machines, Neural Computation, v.19 n.3, p.816-855, March 2007
	Moritz G. Maaí , Johannes Nowak, Text indexing with errors, Journal of Discrete Algorithms, v.5 n.4, p.662-681, December, 2007