{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:3229374"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:3229374","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Indexing N-Gram Graphs with Metric Access Methods","abstract":"Η αναζήτηση των πλησιέστερων γειτόνων εξακολουθεί να αποτελεί σημαντικό πρόβλημα σε πολλούς τομείς της επιστήμης και της μηχανικής. Η αναζήτηση της πιο όμοιας ακολουθίας μίας συλλογής δεδομένων σε με μια δεδομένη ακολουθία δεν είναι τετριμμένη, καθώς η σύγκριση ακολουθιών με ουσιαστικό τρόπο είναι συχνά δαπανηρή. Ειδικοί στην αναζήτηση ομοιότητας έχουν αναπτύξει μετρικές μεθόδους πρόσβασης για την αναζήτηση πλησιέστερου γείτονα που εκμεταλλεύονται τις μετρικές ιδιότητες των συναρτήσεων απόστασης προκειμένου να κλαδέψουν το χώρο αναζήτησης. Ωστόσο, δεν προσφέρουν όλες οι αναπαραστάσεις ακολουθιών συναρτήσεις έυκολα αξιοποιήσιμες από αντίστοιχες μεθόδους. Μια ενδιαφέρουσα τέτοια περίπτωση είναι η αναπαράσταση γράφων ν-γραμμάτων, η οποία απεικονίζει ακολουθίες μέσω ειδικών γραφημάτων που φαίνεται να ενσωματώνουν τη σημασιολογική πληροφορία των ακολουθιών. Οι γράφοι ν-γραμμάτων είναι εξοπλισμένοι με συναρτήσεις ομοιότητας που έχουν χρησιμοποιηθεί αποτελεσματικά σε διάφορα σύνολα εκμάθησης όπως η ταξινόμηση κειμένων ή η ομαδοποίηση σε καταστάσεις θορύβου. Ωστόσο, έχει υπάρξει λίγη έρευνα σχετικά με την ανάκτηση γράφων ν-γραμμάτων, αλλά και σχετικά τις μετρικές ιδιότητες και τις δυνατότητες ευρετηρίασης που προσφέρουν. Η παρούσα διατριβή έχει ως στόχο να καλύψει αυτό το κενό ενσωματώνοντας μετρικές μεθόδους πρόσβασης και αξιολογώντας τις δυνατότητες ευρετηρίασής τους σε γράφους ν-γραμμάτων τόσο θεωρητικά όσο και πειραματικα. Η ικανοποίηση των μετρικών ιδιοτήτων από τις ομοιότητες γράφων ν-γραμμάτων εξετάζεται διεξοδικά, και διερευνώνται μέθοδοι για τη μετατροπή των εν λόγω ομοιοτήτων σε πιο χρήσιμες μορφές. Μια ενδεικτική υλοποίηση αναπτύχθηκε για την εκτέλεση αναζήτησης πλησιέστερου γείτονα με ομοιότητες γράφων ν-γραμμάτων και οι προκλήσεις της υλοποίησης και οι τεχνικές λεπτομέρειες περιγράφονται λεπτομερώς. Οι επιδόσεις, η ταχύτητα και η ευρωστία κάθε αναζήτησης ομοιότητας αξιολογείται σε μια σειρά πειραμάτων ανάκτησης. Αυτή η μελέτη ρίχνει φως στην αναζήτηση ομοιότητας γράφων ν-γραμμάτων και ανοίγει την πόρτα σε μελλοντικές εξετάσεις σε πειράματα που διαφορετικά θα ήταν χρονοβόρα ή σχεδόν ατελέσφορα.","abstract_html":"Η αναζήτηση των πλησιέστερων γειτόνων εξακολουθεί να αποτελεί σημαντικό πρόβλημα σε πολλούς τομείς της επιστήμης και της μηχανικής. Η αναζήτηση της πιο όμοιας ακολουθίας μίας συλλογής δεδομένων σε με μια δεδομένη ακολουθία δεν είναι τετριμμένη, καθώς η σύγκριση ακολουθιών με ουσιαστικό τρόπο είναι συχνά δαπανηρή. Ειδικοί στην αναζήτηση ομοιότητας έχουν αναπτύξει μετρικές μεθόδους πρόσβασης για την αναζήτηση πλησιέστερου γείτονα που εκμεταλλεύονται τις μετρικές ιδιότητες των συναρτήσεων απόστασης προκειμένου να κλαδέψουν το χώρο αναζήτησης. Ωστόσο, δεν προσφέρουν όλες οι αναπαραστάσεις ακολουθιών συναρτήσεις έυκολα αξιοποιήσιμες από αντίστοιχες μεθόδους. Μια ενδιαφέρουσα τέτοια περίπτωση είναι η αναπαράσταση γράφων ν-γραμμάτων, η οποία απεικονίζει ακολουθίες μέσω ειδικών γραφημάτων που φαίνεται να ενσωματώνουν τη σημασιολογική πληροφορία των ακολουθιών. Οι γράφοι ν-γραμμάτων είναι εξοπλισμένοι με συναρτήσεις ομοιότητας που έχουν χρησιμοποιηθεί αποτελεσματικά σε διάφορα σύνολα εκμάθησης όπως η ταξινόμηση κειμένων ή η ομαδοποίηση σε καταστάσεις θορύβου. Ωστόσο, έχει υπάρξει λίγη έρευνα σχετικά με την ανάκτηση γράφων ν-γραμμάτων, αλλά και σχετικά τις μετρικές ιδιότητες και τις δυνατότητες ευρετηρίασης που προσφέρουν. Η παρούσα διατριβή έχει ως στόχο να καλύψει αυτό το κενό ενσωματώνοντας μετρικές μεθόδους πρόσβασης και αξιολογώντας τις δυνατότητες ευρετηρίασής τους σε γράφους ν-γραμμάτων τόσο θεωρητικά όσο και πειραματικα. Η ικανοποίηση των μετρικών ιδιοτήτων από τις ομοιότητες γράφων ν-γραμμάτων εξετάζεται διεξοδικά, και διερευνώνται μέθοδοι για τη μετατροπή των εν λόγω ομοιοτήτων σε πιο χρήσιμες μορφές. Μια ενδεικτική υλοποίηση αναπτύχθηκε για την εκτέλεση αναζήτησης πλησιέστερου γείτονα με ομοιότητες γράφων ν-γραμμάτων και οι προκλήσεις της υλοποίησης και οι τεχνικές λεπτομέρειες περιγράφονται λεπτομερώς. Οι επιδόσεις, η ταχύτητα και η ευρωστία κάθε αναζήτησης ομοιότητας αξιολογείται σε μια σειρά πειραμάτων ανάκτησης. Αυτή η μελέτη ρίχνει φως στην αναζήτηση ομοιότητας γράφων ν-γραμμάτων και ανοίγει την πόρτα σε μελλοντικές εξετάσεις σε πειράματα που διαφορετικά θα ήταν χρονοβόρα ή σχεδόν ατελέσφορα.","abstract_has_math":false,"creators":["Γιαλίτσης Νικόλαος","Nikolaos Gialitsis"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022","date_published":"2022","updated_at":"2026-11-19T05:47:28Z","subjects":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:3229374"],"render_values":[{"text":"uoadl:3229374","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3229374","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/3229374","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%3A3229374","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Γιαλίτσης Νικόλαος","Nikolaos Gialitsis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Τεχνολογία – Πληροφορική","Technology - Computer science"]}]},{"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:3229374","https://pergamos.lib.uoa.gr/uoa/dl/object/3229374"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η αναζήτηση των πλησιέστερων γειτόνων εξακολουθεί να αποτελεί σημαντικό πρόβλημα σε πολλούς τομείς της επιστήμης και της μηχανικής. Η αναζήτηση της πιο όμοιας ακολουθίας μίας συλλογής δεδομένων σε με μια δεδομένη ακολουθία δεν είναι τετριμμένη, καθώς η σύγκριση ακολουθιών με ουσιαστικό τρόπο είναι συχνά δαπανηρή. Ειδικοί στην αναζήτηση ομοιότητας έχουν αναπτύξει μετρικές μεθόδους πρόσβασης για την αναζήτηση πλησιέστερου γείτονα που εκμεταλλεύονται τις μετρικές ιδιότητες των συναρτήσεων απόστασης προκειμένου να κλαδέψουν το χώρο αναζήτησης. Ωστόσο, δεν προσφέρουν όλες οι αναπαραστάσεις ακολουθιών συναρτήσεις έυκολα αξιοποιήσιμες από αντίστοιχες μεθόδους. Μια ενδιαφέρουσα τέτοια περίπτωση είναι η αναπαράσταση γράφων ν-γραμμάτων, η οποία απεικονίζει ακολουθίες μέσω ειδικών γραφημάτων που φαίνεται να ενσωματώνουν τη σημασιολογική πληροφορία των ακολουθιών. Οι γράφοι ν-γραμμάτων είναι εξοπλισμένοι με συναρτήσεις ομοιότητας που έχουν χρησιμοποιηθεί αποτελεσματικά σε διάφορα σύνολα εκμάθησης όπως η ταξινόμηση κειμένων ή η ομαδοποίηση σε καταστάσεις θορύβου. Ωστόσο, έχει υπάρξει λίγη έρευνα σχετικά με την ανάκτηση γράφων ν-γραμμάτων, αλλά και σχετικά τις μετρικές ιδιότητες και τις δυνατότητες ευρετηρίασης που προσφέρουν. Η παρούσα διατριβή έχει ως στόχο να καλύψει αυτό το κενό ενσωματώνοντας μετρικές μεθόδους πρόσβασης και αξιολογώντας τις δυνατότητες ευρετηρίασής τους σε γράφους ν-γραμμάτων τόσο θεωρητικά όσο και πειραματικα. Η ικανοποίηση των μετρικών ιδιοτήτων από τις ομοιότητες γράφων ν-γραμμάτων εξετάζεται διεξοδικά, και διερευνώνται μέθοδοι για τη μετατροπή των εν λόγω ομοιοτήτων σε πιο χρήσιμες μορφές. Μια ενδεικτική υλοποίηση αναπτύχθηκε για την εκτέλεση αναζήτησης πλησιέστερου γείτονα με ομοιότητες γράφων ν-γραμμάτων και οι προκλήσεις της υλοποίησης και οι τεχνικές λεπτομέρειες περιγράφονται λεπτομερώς. Οι επιδόσεις, η ταχύτητα και η ευρωστία κάθε αναζήτησης ομοιότητας αξιολογείται σε μια σειρά πειραμάτων ανάκτησης. Αυτή η μελέτη ρίχνει φως στην αναζήτηση ομοιότητας γράφων ν-γραμμάτων και ανοίγει την πόρτα σε μελλοντικές εξετάσεις σε πειράματα που διαφορετικά θα ήταν χρονοβόρα ή σχεδόν ατελέσφορα.","Searching for nearest neighbors continues to constitute an important problem in many fields of science and engineering. Finding the most similar database sequence to a given sequence is non-trivial, as comparing sequences in a meaningful way is often a costly process in terms of time and computational resources. Similarity search experts have developed metric access methods for nearest neighbor search that take advantage of the metric properties of distance functions in order to prune the search space. However, not all representations of sequences offer metrics as distances. An interesting case is the n-gram graph representation, which reflects a sequence through special types of graphs that appear to encapsulate the semantic information of sequences. N-gram graphs are equipped with similarity functions that have been efficiently used in diverse learning settings, such as text classification or clustering in noisy settings. Nevertheless, there has been little research on the evaluation of the retrieval of n-gram graphs, as well as on the related metric properties and indexing capabilities. This thesis aims to fill this gap by incorporating n-gram graph similarities to metric access methods and evaluating their indexing potential both theoretically and experimentally. The satisfaction of metric properties by the n-gram graph similarities is thoroughly examined along with methods for converting said similarities into more useful forms indexable by metric access methods. A reference implementation is developed to perform approximate efficient nearest neighbor search with n-gram graph similarities and the implementation challenges and technical details are described in detail. The performance, speed, and robustness of each similarity search configuration are evaluated on multiple retrieval experiments of increasing complexity. This study sheds light on the n-gram graph similarity search and opens up the door to future experiments that would otherwise be time-consuming or nearly infeasible."]},{"key":"dc:title","label":"Title","values":["Indexing N-Gram Graphs with Metric Access Methods"]}]}],"canonical_facts":{"dc:creator":["Γιαλίτσης Νικόλαος","Nikolaos Gialitsis"],"dc:date":["2022"],"dc:description":["Η αναζήτηση των πλησιέστερων γειτόνων εξακολουθεί να αποτελεί σημαντικό πρόβλημα σε πολλούς τομείς της επιστήμης και της μηχανικής. Η αναζήτηση της πιο όμοιας ακολουθίας μίας συλλογής δεδομένων σε με μια δεδομένη ακολουθία δεν είναι τετριμμένη, καθώς η σύγκριση ακολουθιών με ουσιαστικό τρόπο είναι συχνά δαπανηρή. Ειδικοί στην αναζήτηση ομοιότητας έχουν αναπτύξει μετρικές μεθόδους πρόσβασης για την αναζήτηση πλησιέστερου γείτονα που εκμεταλλεύονται τις μετρικές ιδιότητες των συναρτήσεων απόστασης προκειμένου να κλαδέψουν το χώρο αναζήτησης. Ωστόσο, δεν προσφέρουν όλες οι αναπαραστάσεις ακολουθιών συναρτήσεις έυκολα αξιοποιήσιμες από αντίστοιχες μεθόδους. Μια ενδιαφέρουσα τέτοια περίπτωση είναι η αναπαράσταση γράφων ν-γραμμάτων, η οποία απεικονίζει ακολουθίες μέσω ειδικών γραφημάτων που φαίνεται να ενσωματώνουν τη σημασιολογική πληροφορία των ακολουθιών. Οι γράφοι ν-γραμμάτων είναι εξοπλισμένοι με συναρτήσεις ομοιότητας που έχουν χρησιμοποιηθεί αποτελεσματικά σε διάφορα σύνολα εκμάθησης όπως η ταξινόμηση κειμένων ή η ομαδοποίηση σε καταστάσεις θορύβου. Ωστόσο, έχει υπάρξει λίγη έρευνα σχετικά με την ανάκτηση γράφων ν-γραμμάτων, αλλά και σχετικά τις μετρικές ιδιότητες και τις δυνατότητες ευρετηρίασης που προσφέρουν. Η παρούσα διατριβή έχει ως στόχο να καλύψει αυτό το κενό ενσωματώνοντας μετρικές μεθόδους πρόσβασης και αξιολογώντας τις δυνατότητες ευρετηρίασής τους σε γράφους ν-γραμμάτων τόσο θεωρητικά όσο και πειραματικα. Η ικανοποίηση των μετρικών ιδιοτήτων από τις ομοιότητες γράφων ν-γραμμάτων εξετάζεται διεξοδικά, και διερευνώνται μέθοδοι για τη μετατροπή των εν λόγω ομοιοτήτων σε πιο χρήσιμες μορφές. Μια ενδεικτική υλοποίηση αναπτύχθηκε για την εκτέλεση αναζήτησης πλησιέστερου γείτονα με ομοιότητες γράφων ν-γραμμάτων και οι προκλήσεις της υλοποίησης και οι τεχνικές λεπτομέρειες περιγράφονται λεπτομερώς. Οι επιδόσεις, η ταχύτητα και η ευρωστία κάθε αναζήτησης ομοιότητας αξιολογείται σε μια σειρά πειραμάτων ανάκτησης. Αυτή η μελέτη ρίχνει φως στην αναζήτηση ομοιότητας γράφων ν-γραμμάτων και ανοίγει την πόρτα σε μελλοντικές εξετάσεις σε πειράματα που διαφορετικά θα ήταν χρονοβόρα ή σχεδόν ατελέσφορα.","Searching for nearest neighbors continues to constitute an important problem in many fields of science and engineering. Finding the most similar database sequence to a given sequence is non-trivial, as comparing sequences in a meaningful way is often a costly process in terms of time and computational resources. Similarity search experts have developed metric access methods for nearest neighbor search that take advantage of the metric properties of distance functions in order to prune the search space. However, not all representations of sequences offer metrics as distances. An interesting case is the n-gram graph representation, which reflects a sequence through special types of graphs that appear to encapsulate the semantic information of sequences. N-gram graphs are equipped with similarity functions that have been efficiently used in diverse learning settings, such as text classification or clustering in noisy settings. Nevertheless, there has been little research on the evaluation of the retrieval of n-gram graphs, as well as on the related metric properties and indexing capabilities. This thesis aims to fill this gap by incorporating n-gram graph similarities to metric access methods and evaluating their indexing potential both theoretically and experimentally. The satisfaction of metric properties by the n-gram graph similarities is thoroughly examined along with methods for converting said similarities into more useful forms indexable by metric access methods. A reference implementation is developed to perform approximate efficient nearest neighbor search with n-gram graph similarities and the implementation challenges and technical details are described in detail. The performance, speed, and robustness of each similarity search configuration are evaluated on multiple retrieval experiments of increasing complexity. This study sheds light on the n-gram graph similarity search and opens up the door to future experiments that would otherwise be time-consuming or nearly infeasible."],"dc:identifier":["uoadl:3229374","https://pergamos.lib.uoa.gr/uoa/dl/object/3229374"],"dc:language":["English"],"dc:subject":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"dc:title":["Indexing N-Gram Graphs with Metric Access Methods"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:47:28Z"}