Back to search

National and Kapodistrian University of Athens

Low-quality dimension reduction and high-dimensional Approximate Nearest Neighbor

Abstract

dc:description

Το πρόβλημα του προσεγγιστικού κοντινότερου γείτονα στην Ευκλείδεια μετρική έχει επιλυθεί κυρίως με δύο βασικές μεθόδους: δομές δέντρων που διαμερίζουν τον χώρο, οι οποίες λειτουργούν εξαιρετικά όταν η διάσταση είναι σχετικά μικρή και το locality sensitive hashing το οποίο αποτελεί μια τυχαιοκρατική μέθοδο η οποία λειτουργεί αποδοτικά και όταν η διάσταση είναι υψηλή. Γενικεύουμε το Johnson-Lindenstrauss λήμμα και ορίζουμε εμβαπτίσεις χαμηλής ποιότητας σε έναν ευκλείδειο χώρο αρκετά χαμηλότερης διάστασης. Με τις εμβαπτίσεις αυτές ανάγουμε το αρχικό πρόβλημα στο πρόβλημα του υπολογισμού k προσεγγιστικών κοντινότερων γειτόνων σε πολύ χαμηλή διάσταση. Τελικά συνδυάζοντας τις εμβαπτίσεις αυτές με υπάρχουσα δομή δεδομένων για χαμηλές διαστάσεις, κατασκευάζουμε μια τυχαιοκρατική δομή δεδομένων η οποία λειτουργεί αποδοτικά όταν η διάσταση είναι υψηλή.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ψαρρός Ιωάννης

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:1321210

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ψαρρός Ιωάννης. Low-quality dimension reduction and high-dimensional Approximate Nearest Neighbor. 2015. https://pergamos.lib.uoa.gr/uoa/dl/object/1321210