High dimensional Approximate r-nets with emphasis on vectors on a unit hypercube

Postgraduate Thesis uoadl:1325624 618 Read counter

Unit:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Library of the School of Science
Deposit date:
2016-11-29
Year:
2016
Author:
Kavouras Loukas
Supervisors info:
Ιωάννης Ζ. Εμίρης , Καθηγητής , Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Δημήτριος Φωτάκης , Επίκουρος Καθηγητής, Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ
Άρης Παγουρτζής , Αναπληρωτής Καθηγητής, Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ
Original Title:
High dimensional Approximate r-nets with emphasis on vectors on a unit hypercube
Languages:
English
Greek
Translated title:
High dimensional Approximate r-nets with emphasis on vectors on a unit hypercube
Summary:
The construction of $r$-nets offers a powerful tool in computational and metric geometry.
We focus on high-dimensional spaces and
present a new randomized algorithm which efficiently computes approximate $r$-nets with respect to Euclidean distance.
For any fixed $\epsilon>0$,
the approximation factor is $1+\epsilon$ and the complexity is polynomial in the dimension and subquadratic in the number of points. The algorithm succeeds with high probability. More specifically,
the best previously known LSH-based construction of Eppstein et al.\ \cite{EHS15} is improved in terms of complexity by reducing the dependence on $\epsilon$,
provided that $\epsilon$ is sufficiently small.
Our method does not require LSH but, instead, follows Valiant's \cite{Val15} approach in designing a sequence of reductions of our problem to other problems in different spaces, under Euclidean distance or inner product, for which $r$-nets are computed efficiently and the error can be controlled.
Our result immediately implies efficient solutions to a number of geometric problems in high dimension, such as finding the $(1+\epsilon)$-approximate $k$th nearest neighbor distance in time subquadratic in the size of the input.
Main subject category:
Science
Keywords:
approximation, r-nets, high dimension
Index:
Yes
Number of index pages:
1
Contains images:
No
Number of references:
14
Number of pages:
42
high-dimensional-approximate (1).pdf (393 KB) Open in new window