Back to search

National and Kapodistrian University of Athens

Indexing N-Gram Graphs with Metric Access Methods

Abstract

dc:description

Η αναζήτηση των πλησιέστερων γειτόνων εξακολουθεί να αποτελεί σημαντικό πρόβλημα σε πολλούς τομείς της επιστήμης και της μηχανικής. Η αναζήτηση της πιο όμοιας ακολουθίας μίας συλλογής δεδομένων σε με μια δεδομένη ακολουθία δεν είναι τετριμμένη, καθώς η σύγκριση ακολουθιών με ουσιαστικό τρόπο είναι συχνά δαπανηρή. Ειδικοί στην αναζήτηση ομοιότητας έχουν αναπτύξει μετρικές μεθόδους πρόσβασης για την αναζήτηση πλησιέστερου γείτονα που εκμεταλλεύονται τις μετρικές ιδιότητες των συναρτήσεων απόστασης προκειμένου να κλαδέψουν το χώρο αναζήτησης. Ωστόσο, δεν προσφέρουν όλες οι αναπαραστάσεις ακολουθιών συναρτήσεις έυκολα αξιοποιήσιμες από αντίστοιχες μεθόδους. Μια ενδιαφέρουσα τέτοια περίπτωση είναι η αναπαράσταση γράφων ν-γραμμάτων, η οποία απεικονίζει ακολουθίες μέσω ειδικών γραφημάτων που φαίνεται να ενσωματώνουν τη σημασιολογική πληροφορία των ακολουθιών. Οι γράφοι ν-γραμμάτων είναι εξοπλισμένοι με συναρτήσεις ομοιότητας που έχουν χρησιμοποιηθεί αποτελεσματικά σε διάφορα σύνολα εκμάθησης όπως η ταξινόμηση κειμένων ή η ομαδοποίηση σε καταστάσεις θορύβου. Ωστόσο, έχει υπάρξει λίγη έρευνα σχετικά με την ανάκτηση γράφων ν-γραμμάτων, αλλά και σχετικά τις μετρικές ιδιότητες και τις δυνατότητες ευρετηρίασης που προσφέρουν. Η παρούσα διατριβή έχει ως στόχο να καλύψει αυτό το κενό ενσωματώνοντας μετρικές μεθόδους πρόσβασης και αξιολογώντας τις δυνατότητες ευρετηρίασής τους σε γράφους ν-γραμμάτων τόσο θεωρητικά όσο και πειραματικα. Η ικανοποίηση των μετρικών ιδιοτήτων από τις ομοιότητες γράφων ν-γραμμάτων εξετάζεται διεξοδικά, και διερευνώνται μέθοδοι για τη μετατροπή των εν λόγω ομοιοτήτων σε πιο χρήσιμες μορφές. Μια ενδεικτική υλοποίηση αναπτύχθηκε για την εκτέλεση αναζήτησης πλησιέστερου γείτονα με ομοιότητες γράφων ν-γραμμάτων και οι προκλήσεις της υλοποίησης και οι τεχνικές λεπτομέρειες περιγράφονται λεπτομερώς. Οι επιδόσεις, η ταχύτητα και η ευρωστία κάθε αναζήτησης ομοιότητας αξιολογείται σε μια σειρά πειραμάτων ανάκτησης. Αυτή η μελέτη ρίχνει φως στην αναζήτηση ομοιότητας γράφων ν-γραμμάτων και ανοίγει την πόρτα σε μελλοντικές εξετάσεις σε πειράματα που διαφορετικά θα ήταν χρονοβόρα ή σχεδόν ατελέσφορα.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Γιαλίτσης Νικόλαος
  • Nikolaos Gialitsis

Subjects

dc:subject × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:3229374

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
citation

Γιαλίτσης Νικόλαος; Nikolaos Gialitsis. Indexing N-Gram Graphs with Metric Access Methods. 2022. https://pergamos.lib.uoa.gr/uoa/dl/object/3229374