2026-09-21T01:42:46Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/50535 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Har-Peled, Sariel Har-Peled, Sariel Erickson, Jeff G. Viswanathan, Mahesh Mount, David M. Kumar, Nirman 2014-09-16T17:23:34Z 2014-09-16T17:23:34Z 2014-08 2014-09-16 2014-08 Given a set of points in a metric space, a fundamental problem is to preprocess these points for answering nearest-neighbor queries on them. Proximity search is the problem of answering more general queries that need the first, second, or further closest neighbors of a query point, possibly in spaces where a separation function is defined which may be more general than a metric. In this thesis, we look at several proximity search problems. Our goal is to better understand, when proximity search is easy, i.e., there is a data-structure requiring near-linear space and allowing logarithmic query time. We study three problems: (i) Answering nearest-neighbor queries in a metric space when the query is restricted to a subspace of low doubling dimension. We show that even though the points lie in a high dimensional ambient space, the problem is inherently low dimensional. (ii) Answering kth nearest-neighbor queries in Euclidean space. We provide a sub-linear space data- structure for this problem. We also extend this to the case when the data points are replaced by disjoint balls (of arbitrary radii), and the distance of a query point to a ball is the distance to the ball as a set. (iii) We consider more general distance functions and proximity search queries on them. This translates to the abstract problem of computing the lower envelope of a set of functions, for a query point. For this abstract problem, we provide a set of sufficient conditions that allow efficient data-structures for computation of the lower envelope. We apply this to several problems of interest. Among new results, we provide approximate weighted Voronoi diagrams in low dimensional Euclidean space. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-07-11T19:05:19Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 28 Kumar_Nirman.pdf: 978285 bytes, checksum: c7feaa43dc036d413daaab761c3d3de6 (MD5) thesis.tex: 6944 bytes, checksum: c7fc296514831852063b21fe7edb9b8c (MD5) meb_expansion.pdf: 19069 bytes, checksum: 119b3f904f2e8dd64b6bf2082484248e (MD5) fconvex.pdf: 46651 bytes, checksum: 161245420d0aa74cf3d451607956a470 (MD5) far.pdf: 20826 bytes, checksum: f04b4764d54ae87150eb4c77fd206c7b (MD5) region.pdf: 46078 bytes, checksum: 61c76b4c5ba784da388f1c6fdf194099 (MD5) region_2.pdf: 45319 bytes, checksum: 932b55fb32f64aebc1a697ed98911ccf (MD5) manifold.pdf: 57698 bytes, checksum: 82c872be128918aa29330fbcce1e0e16 (MD5) grid.pdf: 3332 bytes, checksum: 1a945c55d37a7d4e95a272c098bbb40b (MD5) quorum.pdf: 2794 bytes, checksum: 3c223ba441c41c78fc30d269c3e1e68a (MD5) euclidean.pdf: 99494 bytes, checksum: b176804a981a4a6beea9777f49cacbec (MD5) ellipse.pdf: 20047 bytes, checksum: 067f153cf5a80a68eccc5c56d5cd7b1b (MD5) contain.pdf: 96573 bytes, checksum: 15fcacbef5aa125b09b8e95b4a8e61aa (MD5) b_example.pdf: 94648 bytes, checksum: c6f730fc9c19a30b63dd8c71898d76a7 (MD5) afat.pdf: 61262 bytes, checksum: b4bbd5b566ad906406f2120e64a60d70 (MD5) afat_2.pdf: 36826 bytes, checksum: b2f807b618d155fbf7124a22dad3a0a6 (MD5) prefix.tex: 18367 bytes, checksum: 0f9c700df6c0e0aec019f9a6cf5bfdc7 (MD5) prelims.tex: 22834 bytes, checksum: 14d8a84580e12822d50be6c8c74bf834 (MD5) madgps_apndx.tex: 10159 bytes, checksum: 17e2e184ffa730ef15b9a7df6db8e421 (MD5) madgps.tex: 117418 bytes, checksum: 3fab0208ffeeab4cb5fcca60399046d6 (MD5) lowdim.tex: 80523 bytes, checksum: c80d922e22943948b06623151c7b980d (MD5) bann.tex: 60491 bytes, checksum: 440ed12d93dfa3e034687a0bb7c035dc (MD5) kann.tex: 72839 bytes, checksum: 2f17b10c932456b616e819f19c579960 (MD5) intro.tex: 24677 bytes, checksum: d36aaadef371e4d1837e92b4b12fa64f (MD5) Kumar_Nirman.pdf: 978288 bytes, checksum: 61de99a3f5686822a20f9e9eee41b94a (MD5) thesis.bib: 5298 bytes, checksum: 7e04ddb21fb4ecc74f1c2d837c50e647 (MD5) geometry.bib: 535878 bytes, checksum: 0f4c16e2b7ac51c152ccfc477505bd81 (MD5) shortcuts.bib: 37764 bytes, checksum: bc7025868286023cef88ba3f19a07381 (MD5) Made available in DSpace on 2014-09-16T17:23:34Z (GMT). No. of bitstreams: 28 Nirman_Kumar.pdf: 978288 bytes, checksum: 61de99a3f5686822a20f9e9eee41b94a (MD5) thesis.bib: 5298 bytes, checksum: 7e04ddb21fb4ecc74f1c2d837c50e647 (MD5) geometry.bib: 535878 bytes, checksum: 0f4c16e2b7ac51c152ccfc477505bd81 (MD5) shortcuts.bib: 37764 bytes, checksum: bc7025868286023cef88ba3f19a07381 (MD5) thesis.tex: 6944 bytes, checksum: c7fc296514831852063b21fe7edb9b8c (MD5) meb_expansion.pdf: 19069 bytes, checksum: 119b3f904f2e8dd64b6bf2082484248e (MD5) fconvex.pdf: 46651 bytes, checksum: 161245420d0aa74cf3d451607956a470 (MD5) far.pdf: 20826 bytes, checksum: f04b4764d54ae87150eb4c77fd206c7b (MD5) region.pdf: 46078 bytes, checksum: 61c76b4c5ba784da388f1c6fdf194099 (MD5) region_2.pdf: 45319 bytes, checksum: 932b55fb32f64aebc1a697ed98911ccf (MD5) manifold.pdf: 57698 bytes, checksum: 82c872be128918aa29330fbcce1e0e16 (MD5) grid.pdf: 3332 bytes, checksum: 1a945c55d37a7d4e95a272c098bbb40b (MD5) quorum.pdf: 2794 bytes, checksum: 3c223ba441c41c78fc30d269c3e1e68a (MD5) euclidean.pdf: 99494 bytes, checksum: b176804a981a4a6beea9777f49cacbec (MD5) ellipse.pdf: 20047 bytes, checksum: 067f153cf5a80a68eccc5c56d5cd7b1b (MD5) contain.pdf: 96573 bytes, checksum: 15fcacbef5aa125b09b8e95b4a8e61aa (MD5) b_example.pdf: 94648 bytes, checksum: c6f730fc9c19a30b63dd8c71898d76a7 (MD5) afat.pdf: 61262 bytes, checksum: b4bbd5b566ad906406f2120e64a60d70 (MD5) afat_2.pdf: 36826 bytes, checksum: b2f807b618d155fbf7124a22dad3a0a6 (MD5) prefix.tex: 18367 bytes, checksum: 0f9c700df6c0e0aec019f9a6cf5bfdc7 (MD5) prelims.tex: 22834 bytes, checksum: 14d8a84580e12822d50be6c8c74bf834 (MD5) madgps_apndx.tex: 10159 bytes, checksum: 17e2e184ffa730ef15b9a7df6db8e421 (MD5) madgps.tex: 117418 bytes, checksum: 3fab0208ffeeab4cb5fcca60399046d6 (MD5) lowdim.tex: 80523 bytes, checksum: c80d922e22943948b06623151c7b980d (MD5) bann.tex: 60491 bytes, checksum: 440ed12d93dfa3e034687a0bb7c035dc (MD5) kann.tex: 72839 bytes, checksum: 2f17b10c932456b616e819f19c579960 (MD5) intro.tex: 24677 bytes, checksum: d36aaadef371e4d1837e92b4b12fa64f (MD5) license.txt: 4061 bytes, checksum: f3d54ed2e64219e96d5ec24f4311ee6d (MD5) http://hdl.handle.net/2142/50535 en Copyright 2014 by Nirman Kumar Computational Geometry Algorithms Data-Structures Nearest-Neighbor Search Approximation algorithms In search of better proximity text Computer Science 1434 Computer Science 0112 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Computer Science -UIUC 10KS0112PHD