{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1321210"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1321210","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Low-quality dimension reduction and high-dimensional Approximate Nearest Neighbor","abstract":"Το πρόβλημα του προσεγγιστικού κοντινότερου γείτονα στην Ευκλείδεια μετρική έχει επιλυθεί κυρίως με δύο βασικές μεθόδους: δομές δέντρων που διαμερίζουν τον χώρο, οι οποίες λειτουργούν εξαιρετικά όταν η διάσταση είναι σχετικά μικρή και το locality sensitive hashing το οποίο αποτελεί μια τυχαιοκρατική μέθοδο η οποία λειτουργεί αποδοτικά και όταν η διάσταση είναι υψηλή. Γενικεύουμε το Johnson-Lindenstrauss λήμμα και ορίζουμε εμβαπτίσεις χαμηλής ποιότητας σε έναν ευκλείδειο χώρο αρκετά χαμηλότερης διάστασης. Με τις εμβαπτίσεις αυτές ανάγουμε το αρχικό πρόβλημα στο πρόβλημα του υπολογισμού k προσεγγιστικών κοντινότερων γειτόνων σε πολύ χαμηλή διάσταση. Τελικά συνδυάζοντας τις εμβαπτίσεις αυτές με υπάρχουσα δομή δεδομένων για χαμηλές διαστάσεις, κατασκευάζουμε μια τυχαιοκρατική δομή δεδομένων η οποία λειτουργεί αποδοτικά όταν η διάσταση είναι υψηλή.","abstract_html":"Το πρόβλημα του προσεγγιστικού κοντινότερου γείτονα στην Ευκλείδεια μετρική έχει επιλυθεί κυρίως με δύο βασικές μεθόδους: δομές δέντρων που διαμερίζουν τον χώρο, οι οποίες λειτουργούν εξαιρετικά όταν η διάσταση είναι σχετικά μικρή και το locality sensitive hashing το οποίο αποτελεί μια τυχαιοκρατική μέθοδο η οποία λειτουργεί αποδοτικά και όταν η διάσταση είναι υψηλή. Γενικεύουμε το Johnson-Lindenstrauss λήμμα και ορίζουμε εμβαπτίσεις χαμηλής ποιότητας σε έναν ευκλείδειο χώρο αρκετά χαμηλότερης διάστασης. Με τις εμβαπτίσεις αυτές ανάγουμε το αρχικό πρόβλημα στο πρόβλημα του υπολογισμού k προσεγγιστικών κοντινότερων γειτόνων σε πολύ χαμηλή διάσταση. Τελικά συνδυάζοντας τις εμβαπτίσεις αυτές με υπάρχουσα δομή δεδομένων για χαμηλές διαστάσεις, κατασκευάζουμε μια τυχαιοκρατική δομή δεδομένων η οποία λειτουργεί αποδοτικά όταν η διάσταση είναι υψηλή.","abstract_has_math":false,"creators":["Ψαρρός Ιωάννης"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015","date_published":"2015","updated_at":"2026-11-19T05:26:40Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321210"],"render_values":[{"text":"uoadl:1321210","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321210","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1321210","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1321210","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Ψαρρός Ιωάννης"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1321210","https://pergamos.lib.uoa.gr/uoa/dl/object/1321210"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Το πρόβλημα του προσεγγιστικού κοντινότερου γείτονα στην Ευκλείδεια μετρική έχει επιλυθεί κυρίως με δύο βασικές μεθόδους: δομές δέντρων που διαμερίζουν τον χώρο, οι οποίες λειτουργούν εξαιρετικά όταν η διάσταση είναι σχετικά μικρή και το locality sensitive hashing το οποίο αποτελεί μια τυχαιοκρατική μέθοδο η οποία λειτουργεί αποδοτικά και όταν η διάσταση είναι υψηλή. Γενικεύουμε το Johnson-Lindenstrauss λήμμα και ορίζουμε εμβαπτίσεις χαμηλής ποιότητας σε έναν ευκλείδειο χώρο αρκετά χαμηλότερης διάστασης. Με τις εμβαπτίσεις αυτές ανάγουμε το αρχικό πρόβλημα στο πρόβλημα του υπολογισμού k προσεγγιστικών κοντινότερων γειτόνων σε πολύ χαμηλή διάσταση. Τελικά συνδυάζοντας τις εμβαπτίσεις αυτές με υπάρχουσα δομή δεδομένων για χαμηλές διαστάσεις, κατασκευάζουμε μια τυχαιοκρατική δομή δεδομένων η οποία λειτουργεί αποδοτικά όταν η διάσταση είναι υψηλή.","The approximate nearest neighbor problem (ANN) in Euclidean settings is a fundamental question, which has been addressed by two main approaches: Data-dependent space partitioning techniques perform well when the dimension is relatively low, but are affected by the curse of dimensionality. On the other hand, locality sensitive hashing has polynomial dependence in the dimension and sublinear query time. We generalize the Johnson-Lindenstrauss lemma to define “low-quality” mappings to a Euclidean space of significantly lower dimension, such that they satisfy a requirement weaker than approximately preserving all distances or even preserving the nearest neighbor. This mapping guarantees, with constant probability, that an approximate nearest neighbor lies among the k approximate nearest neighbors in the projected space. This leads to an efficient randomized tree based data structure that avoids the curse of dimensionality."]},{"key":"dc:title","label":"Title","values":["Low-quality dimension reduction and high-dimensional Approximate Nearest Neighbor"]}]}],"canonical_facts":{"dc:creator":["Ψαρρός Ιωάννης"],"dc:date":["2015"],"dc:description":["Το πρόβλημα του προσεγγιστικού κοντινότερου γείτονα στην Ευκλείδεια μετρική έχει επιλυθεί κυρίως με δύο βασικές μεθόδους: δομές δέντρων που διαμερίζουν τον χώρο, οι οποίες λειτουργούν εξαιρετικά όταν η διάσταση είναι σχετικά μικρή και το locality sensitive hashing το οποίο αποτελεί μια τυχαιοκρατική μέθοδο η οποία λειτουργεί αποδοτικά και όταν η διάσταση είναι υψηλή. Γενικεύουμε το Johnson-Lindenstrauss λήμμα και ορίζουμε εμβαπτίσεις χαμηλής ποιότητας σε έναν ευκλείδειο χώρο αρκετά χαμηλότερης διάστασης. Με τις εμβαπτίσεις αυτές ανάγουμε το αρχικό πρόβλημα στο πρόβλημα του υπολογισμού k προσεγγιστικών κοντινότερων γειτόνων σε πολύ χαμηλή διάσταση. Τελικά συνδυάζοντας τις εμβαπτίσεις αυτές με υπάρχουσα δομή δεδομένων για χαμηλές διαστάσεις, κατασκευάζουμε μια τυχαιοκρατική δομή δεδομένων η οποία λειτουργεί αποδοτικά όταν η διάσταση είναι υψηλή.","The approximate nearest neighbor problem (ANN) in Euclidean settings is a fundamental question, which has been addressed by two main approaches: Data-dependent space partitioning techniques perform well when the dimension is relatively low, but are affected by the curse of dimensionality. On the other hand, locality sensitive hashing has polynomial dependence in the dimension and sublinear query time. We generalize the Johnson-Lindenstrauss lemma to define “low-quality” mappings to a Euclidean space of significantly lower dimension, such that they satisfy a requirement weaker than approximately preserving all distances or even preserving the nearest neighbor. This mapping guarantees, with constant probability, that an approximate nearest neighbor lies among the k approximate nearest neighbors in the projected space. This leads to an efficient randomized tree based data structure that avoids the curse of dimensionality."],"dc:identifier":["uoadl:1321210","https://pergamos.lib.uoa.gr/uoa/dl/object/1321210"],"dc:language":["English"],"dc:title":["Low-quality dimension reduction and high-dimensional Approximate Nearest Neighbor"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:26:40Z"}