{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/50535"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/50535","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"In search of better proximity","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Kumar, Nirman"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Har-Peled, Sariel","Erickson, Jeff G.","Viswanathan, Mahesh","Mount, David M."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-09-16T17:23:34Z","date_published":"2014-09-16T17:23:34Z","updated_at":"2026-07-22T22:25:40Z","subjects":["Computational Geometry","Algorithms","Data-Structures","Nearest-Neighbor Search","Approximation algorithms"],"languages":["en"],"rights":["Copyright 2014 by Nirman Kumar"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/50535","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Har-Peled, Sariel","Erickson, Jeff G.","Viswanathan, Mahesh","Mount, David M."]},{"key":"dc:creator","label":"Author","values":["Kumar, Nirman"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-09-16T17:23:34Z","2014-08","2014-09-16"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computational Geometry","Algorithms","Data-Structures","Nearest-Neighbor Search","Approximation algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 by Nirman Kumar"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/50535"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)"]},{"key":"dc:title","label":"Title","values":["In search of better proximity"]}]}],"canonical_facts":{"dc:contributor":["Har-Peled, Sariel","Erickson, Jeff G.","Viswanathan, Mahesh","Mount, David M."],"dc:creator":["Kumar, Nirman"],"dc:date":["2014-09-16T17:23:34Z","2014-08","2014-09-16"],"dc:description":["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)"],"dc:identifier":["http://hdl.handle.net/2142/50535"],"dc:language":["en"],"dc:rights":["Copyright 2014 by Nirman Kumar"],"dc:subject":["Computational Geometry","Algorithms","Data-Structures","Nearest-Neighbor Search","Approximation algorithms"],"dc:title":["In search of better proximity"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:40Z"}