Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering

Full text

Pdf (1.19 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the fourteenth annual symposium on Computational geometry table of contents

Minneapolis, Minnesota, United States

Pages: 222 - 230

Year of Publication: 1998

ISBN:0-89791-973-4

Author

F. Cazals

Algorithms project, INRIA Rocquencourt, F-78153 Le Chesnay and Prisme project, INRIA Sophia, F-06902 Sophia-Antipolis

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 15, Citation Count: 2

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/276884.276910 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.

	A+94	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
	AM93	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
	BYF92	William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	Caz98	F. Cazals. Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustl:ring. Technical Report To appear, INKIA, 1998.
	Cla94	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]
	CP97	F. Cazals , C. Puech, Bucket-like space partitioning data structures with applications to ray-tracing, Proceedings of the thirteenth annual symposium on Computational geometry, p.11-20, June 04-06, 1997, Nice, France [doi>10.1145/262839.262851]
	Dev86	Luc Devroye, Lecture Notes on Bucket Algorithms, Birkhauser Boston, 1986
	Eng97	Konrad Engel, Sperner theory, Cambridge University Press, New York, NY, 1997
	EW82	C. Eastman and S. Weiss. Tree structures for high dimensionality nearest neighbour searching. Information Systems, 7(2), 1982.
	FBF77	Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
	G+93	Mordecai Golin , Rajeev Raman , Christian Schwarz , Michiel Smid, Randomized data structures for the dynamic closest-pair problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.301-310, January 25-27, 1993, Austin, Texas, United States
	IM98	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]
	Kle97	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]
	Kle98	Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
	Mil98	Peter Bro Miltersen, Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.556-563, January 25-27, 1998, San Francisco, California, United States
	Pug90	William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
	Riv74	R. Rive.st. On the optimality of elias's algorithm for performing best matches searches. Information Processing, No rth-Holland Pub. Co.:678-681, 1974.
	Spr91	B.. Sproull. Refinements to nearest-neighbour searching in k-dimensional trees. Algorithmica, 6, 1991.
	vLW92	J.H. van Lint and R.M. Wilson. A course in Combinaret ies. Cambridge University Press, 1992.
	Yao82	A. Yao. On constructing minimum spanning trees in kdimensional spaces and related problems. SIAM J. on Computing, 11(4), 1982.
	Yia93	Peter N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.311-321, January 25-27, 1993, Austin, Texas, United States

CITED BY 2

	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
	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