Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Dimitrios Nikolopoulos Anonymously browsing from at 21:23:55, 23-09-2017. login

MSc thesis of Dimitrios Nikolopoulos

Randomly-oriented RKD-trees

Supervisor: Ioannis Emiris

Consider a set S of points in a real D-dimensional space RD, where distances are defined using function ∆ : RD × RD → R (the Euclidean metric). Nearest neighbor search is an optimization problem for finding the closest points in S to a given query point q ∈ RD. Given a positive real ε > 0 then a point p ∈ S is a (1+ε)-approximate nearest neighbor of the query point q ∈ RD if dist(q, p) ≤ (1 + ε)dist(q, pnn) where pnn ∈ S is the true nearest neighbor to q. If the data that is expressed in high- dimensional space RD lies closer to an embedded manifold M of dimension d, where d ≪ D, then, we show the data may be preprocessed into the Randomly-oriented RKD-trees structure and we provide a near optimal bound on the number of levels required to reduce the size of its cells by a factor s ≥ 2. We show the data may be preprocessed into the structure in O􏰀D · N · log N 􏰁 time and O􏰀D · N 􏰁 space, so that given a query point q ∈ RD and ε > 0, a (1+ε)-approximate nearest neighbor of q may ε high-dimensional data with an underlying low-intrinsic dimensional subspace.

Defended: March 19, 2014.

Scientific committee


Download thesis.


Page updates

No recent updates.

Feeds RSS and Atom feeds

all posts RSS
news RSS
announcements RSS
website news RSS
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2017 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.