In search of better proximity

Kumar, Nirman

Permalink

https://hdl.handle.net/2142/50535 Copy

Description

Title

In search of better proximity

Author(s)

Kumar, Nirman

Issue Date

2014-09-16

Director of Research (if dissertation) or Advisor (if thesis)

Har-Peled, Sariel

Doctoral Committee Chair(s)

Har-Peled, Sariel

Committee Member(s)

• Erickson, Jeff G.
• Viswanathan, Mahesh
• Mount, David M.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Computational Geometry
• Algorithms
• Data-Structures
• Nearest-Neighbor Search
• Approximation algorithms

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.

Graduation Semester

2014-08

Permalink

http://hdl.handle.net/2142/50535

Copyright and License Information

Copyright 2014 by Nirman Kumar

Owning Collections