Locality-preserving hashing in multidimensional spaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Locality-preserving hashing in multidimensional spaces

Full text

Pdf (1.20 MB)

Source

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

El Paso, Texas, United States

Pages: 618 - 625

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Piotr Indyk	Department of Computer Science, Stanford University
Rajeev Motwani	Department of Computer Science, Stanford University
Prabhakar Raghavan	IBM Almaden Research Center
Santosh Vempala	School of Computer Science, Carnegie-Mellon University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 56, Citation Count: 25

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/258533.258656 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	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
	3	C. Buckley, A. Singhal, M. Mitra, and G. Salton, New Retrieval Approaches Using SMART: TREC 4. Proc. Fourth Text Retrieval Conference, National Institute of Standards and Technology, 1995.
	4	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]
	5	Scott Cost , Steven Salzberg, A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features, Machine Learning, v.10 n.1, p.57-78, Jan. 1993 [doi>10.1023/A:1022664626993]
	6	T.M. (:over and P.E. Hart, "Nearest neighbor pattern classification," iEEE Transactions on information Theory, 13 (1967), pp. 21-27.
	7	S. Deerwester, S. T. Dumais, T.K. Landauer, G.W. Furnas, and R.A. Harshman, "Indexing by latent semantic analysis," Journal of the Society for Information Science, 41 (1990), pp. 391-407.
	8	L. Devroye and T.J. Wagner, "Nearest neighbor methods in discrimination," Handbook of Statistics, vol. 2, P.R. Krishnaiah, L.N. Kanal, eds., North-Holland, 1982.
	9	D. Dobkin and R. Lipton, "Multidimensional search problems," SiAM J. Computing, 5 (1976), pp. 181-186.
	10	Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
	11	C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
	12	Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
	13	T. Hastie and R. Tibshirani, "Discriminant adaptive nearest neighbor classification," First International Conference on Knowledge Discovery and Data Mining, 1995.
	14	H. Hotelling, "Analysis of a complex of statistical variables into principal components", Journal of educational psychology, 27 (1933), pp. 417-441.
	15	IEEE Computer Special Issue on Content. based Image Retrieval Systems, 28 (1995).
	16	K. Karhunen. Ober lineare Methoden in der Wahrscheinlichkeitsredmung. Ann. Acad. Sci. Fennicae, Ser. A137, 1947.
	17	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]
	18	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	19	E. Kreyszig, Introductory Functional Analysis with Applications, Wiley, 1989.
	20	V. Koivune and S. Kassam, "Nearest neighbor filters for multivariate data," IEEE Workshop on Nonlinear Signal and Image Processing, 1995.
	21	Nathan Linial , Ori Sasson, Non-expansive hashing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.509-518, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237999]
	22	M. Lo~ve. Fonctions aleastoires de second ordere. Processus Stochastiques et mouvement Brownian. Hermann, Paris, 1948.
	23	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]
	24	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]
	25	Ketan Mulmuley, Randomized multidimensional search trees: further results in dynamic sampling (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.216-227, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185371]
	26	Panel on Discriminant Analysis and Clustering, National Research Council, Discriminant Analysis and Clustering, National Academy Press, 1988.
	27	A. Pentland, R.W. Picard, and S. Sclaroff, "Photobook: tools for content-based manipulation of image databases", In Proc. SPIE Conference on Storage and Retrieval of Image and Video Databases II, 2185, 1994.
	28	Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	29	Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	30	A.W.M. Smeulders and R. Jain, editors, Image Databases and Multi-media Search, Proceedings of the First International Workshop, IDB-MMS '96, Amsterdam. Amsterdam University Press, 1996.
	31	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 25

	Ashish Goel , Piotr Indyk , Kasturi Varadarajan, Reductions among high dimensional proximity problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.769-778, January 07-09, 2001, Washington, D.C., United States
	Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.538-547, January 09-11, 2000, San Francisco, California, United States
	Vijayshankar Raman, Locality preserving dictionaries: theory & application to clustering in databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.337-345, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Andrew B. Kahng , Darko Kirovski , Stefanus Mantik , Miodrag Potkonjak , Jennifer L. Wong, Copy detection for intellectual property protection of VLSI designs, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.600-605, November 07-11, 1999, San Jose, California, United States
	Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001
	Pankaj K. Agarwal , Cecilia M. Procopiuc , Kasturi R. Varadarajan, A (1 + ɛ)-approximation algorithm for 2-line-center, Computational Geometry: Theory and Applications, v.26 n.2, p.119-128, October 2003
	Anna Ostlin , Rasmus Pagh, Uniform hashing in constant time and linear space, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Journal of Algorithms, v.46 n.2, p.115-139, February 2003
	Bill Chiu , Eamonn Keogh , Stefano Lonardi, Probabilistic discovery of time series motifs, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Piotr Indyk, Dimensionality reduction techniques for proximity problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.371-378, January 09-11, 2000, San Francisco, California, United States
	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
	Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA
	Joshua Steinhurst , Greg Coombe , Anselmo Lastra, Reordering for cache conscious photon mapping, Proceedings of the 2005 conference on Graphics interface, May 09-11, 2005, Victoria, British Columbia
	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
	Vincent C. H. Ma , Michael D. McCool, Low latency photon mapping using block hashing, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
	Sreenivas Gollapudi , Rina Panigrahy, Exploiting asymmetry in hierarchical topic extraction, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Dragomir Yankov , Eamonn Keogh , Jose Medina , Bill Chiu , Victor Zordan, Detecting time series motifs under uniform scaling, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Jeffrey Scott Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, v.2 n.4, p.305-474, January 2008
	Li Wei , Eamonn Keogh , Xiaopeng Xi , Melissa Yoder, Efficiently finding unusual shapes in large image databases, Data Mining and Knowledge Discovery, v.17 n.3, p.343-376, December 2008
	Jon Oberheide , Evan Cooke , Farnam Jahanian, CloudAV: N-version antivirus in the network cloud, Proceedings of the 17th conference on Security symposium, p.91-106, July 28-August 01, 2008, San Jose, CA
	Niloy J. Mitra , Leonidas Guibas , Joachim Giesen , Mark Pauly, Probabilistic fingerprints for shapes, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
	Joshua Steinhurst , Greg Coombe , Anselmo Lastra, Reducing Photon-Mapping Bandwidth by Query Reordering, IEEE Transactions on Visualization and Computer Graphics, v.14 n.1, p.13-24, January 2008
	Simon Heinzle , Gaël Guennebaud , Mario Botsch , Markus Gross, A hardware processing unit for point sets, Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, June 20-21, 2008, Sarajevo, Bosnia and Herzegovina
	Jong Wook Kim , K. Selçuk Candan , Junichi Tatemura, Efficient overlap and content reuse detection in blogs and online news articles, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain