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