Searching dynamic point sets in spaces with bounded doubling dimension

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Searching dynamic point sets in spaces with bounded doubling dimension

Full text

Pdf (275 KB)

Source

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

Seattle, WA, USA

SESSION: Session 13B table of contents

Pages: 574 - 583

Year of Publication: 2006

ISBN:1-59593-134-1

Authors

Richard Cole	New York University, New York, NY
Lee-Ad Gottlieb	New York University, New York, NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 56, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/1132516.1132599 What is a DOI?

ABSTRACT

We present a new data structure that facilitates approximate nearest neighbor searches on a dynamic set of points in a metric space that has a bounded doubling dimension. Our data structure has linear size and supports insertions and deletions in O(log n) time, and finds a (1+ε)-approximate nearest neighbor in time O(log n) + (1/ε)^O(1). The search and update times hide multiplicative factors that depend on the doubling dimension; the space does not. These performance times are independent of the aspect ratio (or spread) of the points.

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	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
	2	A. Bagchi, A. L. Buchsbaum and M. T. Goodrich. Biased skip lists. Algorithmica, 42(1):31--48, 2005.
	3	S. W. Bent, D. D. Sleator and R. E. Tarjan. Biased search trees. SIAM J. Comput., 14(3):545--68, 1985.
	4	J. L. Bentley and J. B. Saxe. Decomposable searching problems I: Static-to-dynamic transformation. J. Alg., 1(4):301--358, 1980.
	5	A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. Manuscript.
	6	Paul B. Callahan , S. Rao Kosaraju, A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.546-556, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129766]
	7	Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001 [doi>10.1145/502807.502808]
	8	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]
	9	K. L. Clarkson. Nearest neighbor queries in metric spaces. Discrete Computational Geometry, 22(1):63--93, 1999.
	10	Richard Cole , Ramesh Hariharan, Dynamic LCA Queries on Trees, SIAM Journal on Computing, v.34 n.4, p.894-923, 2005 [doi>10.1137/S0097539700370539]
	11	Greg N. Frederickson, A data structure for dynamically maintaining rooted trees, Journal of Algorithms, v.24 n.1, p.37-65, July 1997 [doi>10.1006/jagm.1996.0835 ]
	12	Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
	13	Sariel Har-Peled , Manor Mendel, Fast construction of nets in low dimensional metrics, and their applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064117]
	14	David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
	15	Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	16	Robert Krauthgamer , James R. Lee, The black-box complexity of nearest-neighbor search, Theoretical Computer Science, v.348 n.2, p.262-276, 8 December 2005 [doi>10.1016/j.tcs.2005.09.017]

CITED BY 5

	Lee-Ad Gottlieb , Liam Roditty, Improved algorithms for fully dynamic geometric spanners and geometric routing, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.591-600, January 20-22, 2008, San Francisco, California
	Liam Roditty, Fully dynamic geometric spanners, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Navin Goyal , Yury Lifshits , Hinrich Schütze, Disorder inequality: a combinatorial approach to nearest neighbor search, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA
	T-H. Hubert Chan , Anupam Gupta, Approximating TSP on metrics with bounded global growth, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.690-699, January 20-22, 2008, San Francisco, California
	T-H. Hubert Chan , Anupam Gupta , Kunal Talwar, Ultra-low-dimensional embeddings for doubling metrics, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.333-342, January 20-22, 2008, San Francisco, California