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 × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:3229374