AUEB Library - Digital Repository

PYXIDA Institutional Repository
and Digital Library

Username
Password

Collections :	Ιδρυματικό Αποθετήριο ΟΠΑ / AUEB Institutional Repository Σχολή Επιστημών και Τεχνολογίας της Πληροφορίας / School of Informatics Τμήμα Πληροφορικής / Department of Informatics Μεταπτυχιακές Εργασίες / Postgraduate dissertations

Title :	Optimizing two-stage nearest neighbor search for scalable multi-table vector retrieval

Alternative Title :	Βελτιστοποίηση αναζήτησης δύο σταδίων του πλησιέστερου γείτονα για κλιμακούμενη ανάκτηση διανυσμάτων από πολλαπλούς πίνακες

Creator :	Δημόπουλος, Βασίλειος Dimopoulos, Vasileios

Contributor :	Kotidis, Yannis (Επιβλέπων καθηγητής) Androutsopoulos, Ion (Εξεταστής) Vassalos, Vasilios (Εξεταστής) Athens University of Economics and Business, Department of Informatics (Degree granting institution)

Type :	Text

Extent :	85p.

Language :	en

Identifier :	http://www.pyxida.aueb.gr/index.php?op=view_object&object_id=11761

Abstract :	Η παρούσα διπλωματική εργασία εξετάζει το πρόβλημα που της Ανάκτησης Διανυσμάτων Δύο Σταδίων (Two Stage Vector Retrieval Problem − T SV RP), που περιγράφει την αποδοτική προσέγγιση πλησιέστερων γειτόνων (ΑΝΝ) σε συστήματα ανάκτησης δύο σταδίων. Η διαδικασία περιλαμβάνει την εύρεση πλησιέστερων γειτόνων σε δύο ξεχωριστά σύνολα δεδομένων, όπου τα αποτελέσματα του πρώτου σταδίου χρησιμοποιούνται ως ερωτήματα στο δεύτερο στάδιο. Οι παραδοσιακές μέθοδοι, αν και αποτελεσματικές, μπορεί να είναι υπολογιστικά απαιτητικές λόγω ανεξάρτητων αναζητήσεων σε κάθε στάδιο. Προτείνουμε δύο νέες μεθόδους για τη βελτίωση της αποδοτικότητας και της ταχύτητας αυτής της διαδικασίας. Η πρώτη μέθοδος βελτιστοποιεί το δεύτερο στάδιο, αξιοποιώντας τα αποτελέσματα προηγούμενων αναζητήσεων για τη μείωση περιττών υπολογισμών και την αξιοποίηση της τοπικότητας των δεδομένων. Η δεύτερη μέθοδος χρησιμοποιεί μια στρατηγική κατακερματισμού, διαιρώντας τα δεδομένα σε μικρότερα, διαχειρίσιμα υποσύνολα και εστιάζοντας την αναζήτηση σε συγκεκριμένες περιοχές, μειώνοντας το συνολικό υπολογιστικό κόστος. Τα αποτελέσματά μας δείχνουν ότι η πρώτη μέθοδος προσφέρει σημαντική βελτίωση της αποδοτικότητας διατηρώντας υψηλή ακρίβεια, καθιστώντας την κατάλληλη για εφαρμογές που απαιτούν ακρίβεια. Η δεύτερη μέθοδος αποτελεί ταχύτερη εναλλακτική για περιπτώσεις όπου η ταχύτητα έχει μεγαλύτερη σημασία από την απόλυτη ακρίβεια. Οι μέθοδοι αυτές παρέχουν ευέλικτες λύσεις για τη βελτιστοποίηση της αναζήτησης ΑΝΝ σε συστήματα πολλαπλών σταδίων. This thesis explores the problem of Two Stage Vector Retrieval (TSVRP), that describes the efficient approximate nearest neighbor (ANN) search in two-stage retrieval systems. The process involves finding nearest neighbors in two separate datasets, where the results of the first stage are used as queries in the second stage. Traditional approaches, while effective, can be computationally expensive due to independent searches at each stage. We propose two novel methods to improve the efficiency and speed of this process. The first method optimizes the second stage by leveraging the results of prior searches to reduce redundant computations and take advantage of data locality. The second method employs a partitioning strategy to divide the data into smaller, manageable subsets, focusing searches within specific partitions to reduce the overall computational cost. Our results demonstrate that the first method achieves significant efficiency improvements while maintaining high accuracy, making it suitable for applications where precision is critical. The second method offers a faster alternative for scenarios where speed is prioritized over exact accuracy. These approaches provide flexible solutions for optimizing ANN search in multi-stage systems.

Abstract :

Η παρούσα διπλωματική εργασία εξετάζει το πρόβλημα που της Ανάκτησης Διανυσμάτων Δύο Σταδίων (Two Stage Vector Retrieval Problem − T SV RP), που περιγράφει την αποδοτική προσέγγιση πλησιέστερων γειτόνων (ΑΝΝ) σε συστήματα ανάκτησης δύο σταδίων. Η διαδικασία περιλαμβάνει την εύρεση πλησιέστερων γειτόνων σε δύο ξεχωριστά σύνολα δεδομένων, όπου τα αποτελέσματα του πρώτου σταδίου χρησιμοποιούνται ως ερωτήματα στο δεύτερο στάδιο. Οι παραδοσιακές μέθοδοι, αν και αποτελεσματικές, μπορεί να είναι υπολογιστικά απαιτητικές λόγω ανεξάρτητων αναζητήσεων σε κάθε στάδιο. Προτείνουμε δύο νέες μεθόδους για τη βελτίωση της αποδοτικότητας και της ταχύτητας αυτής της διαδικασίας. Η πρώτη μέθοδος βελτιστοποιεί το δεύτερο στάδιο, αξιοποιώντας τα αποτελέσματα προηγούμενων αναζητήσεων για τη μείωση περιττών υπολογισμών και την αξιοποίηση της τοπικότητας των δεδομένων. Η δεύτερη μέθοδος χρησιμοποιεί μια στρατηγική κατακερματισμού, διαιρώντας τα δεδομένα σε μικρότερα, διαχειρίσιμα υποσύνολα και εστιάζοντας την αναζήτηση σε συγκεκριμένες περιοχές, μειώνοντας το συνολικό υπολογιστικό κόστος. Τα αποτελέσματά μας δείχνουν ότι η πρώτη μέθοδος προσφέρει σημαντική βελτίωση της αποδοτικότητας διατηρώντας υψηλή ακρίβεια, καθιστώντας την κατάλληλη για εφαρμογές που απαιτούν ακρίβεια. Η δεύτερη μέθοδος αποτελεί ταχύτερη εναλλακτική για περιπτώσεις όπου η ταχύτητα έχει μεγαλύτερη σημασία από την απόλυτη ακρίβεια. Οι μέθοδοι αυτές παρέχουν ευέλικτες λύσεις για τη βελτιστοποίηση της αναζήτησης ΑΝΝ σε συστήματα πολλαπλών σταδίων.
This thesis explores the problem of Two Stage Vector Retrieval (TSVRP), that describes the efficient approximate nearest neighbor (ANN) search in two-stage retrieval systems. The process involves finding nearest neighbors in two separate datasets, where the results of the first stage are used as queries in the second stage. Traditional approaches, while effective, can be computationally expensive due to independent searches at each stage. We propose two novel methods to improve the efficiency and speed of this process. The first method optimizes the second stage by leveraging the results of prior searches to reduce redundant computations and take advantage of data locality. The second method employs a partitioning strategy to divide the data into smaller, manageable subsets, focusing searches within specific partitions to reduce the overall computational cost. Our results demonstrate that the first method achieves significant efficiency improvements while maintaining high accuracy, making it suitable for applications where precision is critical. The second method offers a faster alternative for scenarios where speed is prioritized over exact accuracy. These approaches provide flexible solutions for optimizing ANN search in multi-stage systems.

Subject :	Ανάκτηση διανυσμάτων Αναζήτηση πλησιέστερου γείτονα Προσεγγιστική αναζήτηση Ανάκτηση δύο σταδίων Κλιμακωσιμότητα Vector retrieval Nearest neighbor search Approximate search Two-stage retrieval Scalability

Date Available :	2024-12-05 13:45:55

Date Issued :	26-11-2024

Date Submitted :	2024-12-05 13:45:55

Access Rights :	Free access

Licence :

File: Dimopoulos_2024.pdf

Type: application/pdf

Login