| Περίληψη: | Ο σκοπός αυτής της διατριβής είναι η ανεύρεση μεθόδων αποδοτικής οργάνωσης και διαχείρισης πολυδιάστατων αντικειμένων (multi-dimensional objects) προκειμένου να ανακαλυφθεί χρήσιμη γνώση. Αρχική αφορμή για αυτή τη μελέτη αποτέλεσαν οι ανάγκες μιας απαιτητικής εφαρμογής με σκοπό τη χαρτογράφηση του ανθρώπινου εγκεφάλου προκειμένου να εντοπιστούν επιληπτικές εστίες. Οι απαιτήσεις Αναπαράστασης και Διαχείρισης των Δεδομένων του Εγκεφάλου, έφεραν στην επιφάνεια δύο κεντρικά ερευνητικά προβλήματα:
- Τις ιδιαιτερότητες των πολύπλοκων, μη-ομοιογενών, δικτυακών μερικές φορές, τρισδιάστατων αντικειμένων (τμημάτων του εγκεφάλου – brain objects).
- Την ανάγκη για αποτελεσματική διαχείριση-χρήση γνωστών αλλά και παραγόμενων εξαρτήσεων δεδομένων και γνώσης (data and knowledge dependencies), η οποία μπορεί να αναβαθμίσει την απόδοση και τη δυναμική της εφαρμογής. Το μεγαλύτερο μέρος της μελέτης που αφορούσε αυτό το πρόβλημα, οδήγησε σε :
- Διερεύνηση θεμάτων ανεύρεσης ομοιοτήτων (similarity search). Καθώς η συγκεκριμένη περιοχή διαθέτει μεγάλο εύρος εφαρμογών αλλά και ανοικτών προβλημάτων, αποτέλεσε τελικά μεγάλο μέρος της παρούσας διατριβής.
Δεδομένου ότι πολλά από τα γεωμετρικά χαρακτηριστικά των δεδομένων αλλά και από τις εξαρτήσεις γνώσης που αφορούν τον ανθρώπινο εγκέφαλο, συναντώνται – καθ’ολοκληρία ή τμηματικά – σε πλήθος σύγχρονων πολυμεσικών (multimedia) εφαρμογών, τα παραπάνω προβλήματα εντάσσονται στα βασικά προβλήματα της έρευνας του τομέα των Βάσεων Δεδομένων.
Επικεντρώνοντας την έρευνά στα παραπάνω προβλήματα, καταλήξαμε:
• στον ορισμό νέων ευέλικτων τύπων δεδομένων, εννοιών και μοντέλων καθώς και εργαλείων και μεθόδων ταξινόμησης δεδομένων και γνώσης (βάση δεδομένων BDB και μοντέλα 3D-IFO και MITOS) οι οποίες οργανώνουν πιο ευέλικτα και αποδοτικά τα δεδομένα μας, με τρόπους που όχι μόνο κάνουν την πρόσβασή τους ευκολότερη αλλά αξιοποιούν παράλληλα τις ‘κρυμμένες’ μεταξύ τους σχέσεις για την άντληση επιπλέον γνώσης.
• στον ορισμό νέων μεθόδων και δέντρων αναζήτησης, για :
o τον αποδοτικό εντοπισμό τμηματικών ομοιοτήτων (partial similarity) ανάμεσα σε πολυδιάστατα αντικείμενα (Lui k-n-match και INTESIS)
o την εξάλειψη της μεγάλης πτώσης της απόδοσης των δέντρων με την αύξηση των διαστάσεων των αντικειμένων (‘dimensionality curse’) (δομή Digenis).
o την ανεύρεση χαρακτηριστικών/διαστάσεων με παρόμοια εξέλιξη στην πορεία του χρόνου – για πολυδιάστατα κυρίως αντικείμενα – με σκοπό τη μελέτη πιθανής αλληλεπίδρασής τους.
Γενικά, η παρούσα μελέτη αποτελείται από δύο βασικά μέρη, τα οποία αναφέρονται σε δύο περιοχές με μεγάλη αλληλεπίδραση:
Τη Μοντελοποίηση σε Πολυμεσικές Βάσεις Δεδομένων
Την Αναζήτηση Ομοιοτήτων ανάμεσα σε Πολυδιάστατα Αντικείμενα
Στο πρώτο κεφάλαιο αρχικά παρουσιάζεται το πρόβλημα της χαρτογράφησης του ανθρώπινου εγκεφάλου για τον εντοπισμό επιληπτικών εστιών, απ’όπου εγείρονται τα πρώτα προβλήματα αναπαράστασης και οργάνωσης τριδιάστατων αντικειμένων πολύπλοκης δομής και λειτουργικών σχέσεων και εξαρτήσεων μεταξύ τους. Σε μια πρώτη προσέγγιση προτείνεται το λογικό μοντέλο BDB (Brain Data Base) όπου εισάγονται νέοι τύποι οντοτήτων. Εδώ, ιδιαίτερο ενδιαφέρον παρουσιάζει η προσθήκη της ιεραρχικής διάταξης στο Σχεσιακό Μοντέλο, προκειμένου οι περιοχές του εγκεφάλου να οργανωθούν με βάση την πιθανότητα εμφάνισης επιληπτικής εστίας έτσι ώστε να βελτιώνονται στατιστικά οι χρόνοι ανάκτησής τους. Στη συνέχεια, η μελέτη επεκτείνεται σε άλλα – επόμενης γενιάς - είδη μοντέλων. Πιο συγκεκριμένα, οι ανάγκες της εφαρμογής μελετώνται με βάση ένα Σημαντικό (semantic model) - το μοντέλο IFO - και ένα Αντικειμενοστραφές Μοντέλο (object oriented model), με αποτέλεσμα τη δημιουργία των μοντέλων 3D-IFO και MITOS αντίστοιχα. Στο 3D-IFO εισήχθησαν νέοι τύποι δεδομένων προκειμένου να υποστηριχθούν αποδοτικά τα ιδιαίτερα δεδομένα μας καθώς και νέοι τελεστές για την καλύτερη διαχείριση των σύνθετων δεδομένων. Επιπλέον, εισήχθη ένας νέος constructor και ένα κατάλληλο πεδίο για την υποστήριξή του, προκειμένου να υποστηριχτεί η αναπαράσταση της διάταξης των μερών του εγκεφάλου με βάση κάποιο κριτήριο έτσι ώστε να διευκολυνθεί η μελλοντική απλή και συνδυαστική ανάκτηση πληροφορίας. Τέλος το αντικειμενοστραφές μοντέλο MITOS, εισάγει πάλι ένα νέο μοντέλο δεδομένων (MITOS Data Model - MDM) το οποίο συνεργάζεται με μία νέα γλώσσα ερωτημάτων (MITOS Query Language - MQL). Το μοντέλο MITOS εισάγει διάφορες καινοτομίες οι οποίες εξυπηρετούν μια περισσότερο εκφραστική και έξυπνη αναπαράσταση και διαχείριση πολυδιάστατων δεδομένων και γνώσης. Η μία από αυτές τις καινοτομίες είναι ο ορισμός ενός ακόμη βασικού χαρακτηριστικού των αντικειμένων (object characteristic), της σχέσης τους με το περιβάλλον, απεγκλωβίζοντάς την από την κατάσταση ή τη συμπεριφορά, όπου αποδυναμώνεται σαν έννοια. Η δεύτερη καινοτομία του MITOS η οποία αφορά την MQL σχετίζεται με την εισαγωγή ‘κλειδιού’ στους κανόνες (rules). Η διερεύνηση αυτής της δυνατότητας – η ιδέα προέρχεται από το χώρο των Βάσεων Δεδομένων – οδηγεί πράγματι σε ένα είδος κλειδιού, κατά την έννοια που θα μπορούσε να έχει στις Βάσεις Γνώσης και η οποία δεν μπορεί να είναι ακριβώς ίδια με την αντίστοιχη των Βάσεων Δεδομένων, λόγω των ειδοποιών διαφορών των δύο Βάσεων.
Στο δεύτερο κεφάλαιο μελετάται η αναζήτηση ενός ελάχιστα διερευνημένου είδους ομοιότητας ανάμεσα σε πολυδιάστατα κυρίως αντικείμενα, της τμηματικής ομοιότητας (partial similarity). Η τμηματική ομοιότητα σε αντίθεση με τον ιδιαίτερα διερευνημένο τύπο της πλήρους ομοιότητας (full similarity), αναφέρεται σε πραγματικές ομοιότητες οι οποίες δεν είναι πλήρεις. Κι αυτό συμβαίνει γιατί ένα πολύ συνηθισμένο σενάριο κατά τη διερεύνηση ομοιοτήτων είναι το ακόλουθο: Συνήθως η ανεύρεση πλήρους ομοιότητας βασίζεται σε υπολογισμό αποστάσεων, όπως η Ευκλείδεια απόσταση, οι οποίες είναι συνάρτηση όλων των διαστάσεων των εμπλεκομένων αντικειμένων. Όταν λοιπόν υπάρχουν διαστάσεις με μεγάλες διαφορές, ακόμη κι αν είναι λίγες, αυξάνουν αρκετά την υπολογιζόμενη απόσταση έτσι ώστε οι αποστάσεις τέτοιων αντικειμένων που στην πραγματικότητα μπορεί να είναι όμοια, να καταλήγουν να έχουν μεγάλες τιμές και συνεπώς να μην ανιχνεύεται η ομοιότητά τους (π.χ. όμοια αντικείμενα με πολύ διαφορετικό χρώμα). Από την άλλη πλευρά, για αντικείμενα τα οποία διαφέρουν λίγο σε κάθε διάσταση (π.χ. λίγο διαφορετικό χρώμα, σχήμα, προσανατολισμό κ.λ.π.) και καταλήγουν να είναι στην πραγματικότητα συνολικά πολύ διαφορετικά, η υπολογιζόμενη μεταξύ τους απόσταση έχει μικρή τιμή, οπότε ανιχνεύονται σαν όμοια, χωρίς να είναι.
Οι περισσότερες εργασίες οι οποίες έχουν μελετήσει την τμηματική ομοιότητα, έχουν εστιάσει σε γεωμετρικά δεδομένα. Η εργασία που επεκτείνεται σε πολυδιάστατα αντικείμενα γενικά, είναι η εργασία των Koudas et al., (VLDB 2006) και έχει οδηγήσει σε αξιόλογα αποτελέσματα στο θέμα της τμηματικής ομοιότητας. Εισάγει τις αποδοτικές μεθόδους k-n-match και frequent k-n-match, οι οποίες επιστρέφουν k αντικείμενα, όμοια με τα δοθέντα όχι σε όλες αλλά σε n διαστάσεις, αποφεύγοντας έτσι εκείνες τις λίγες διαστάσεις με τις μεγάλες διαφορές, οι οποίες οδηγούν σε παραπλανητικά αποτελέσματα. Παρόλ’αυτά αυτές οι μέθοδοι κρύβουν κάποιες αδυναμίες οι οποίες τελικά οδηγούν είτε σε ανεύρεση πλήρους ομοιότητας (όταν τελικά ληφθούν υπ’όψιν όλα τα n), είτε σε μία κατά περίπτωση μόνο (και σχεδόν τυχαία) ανίχνευση τμηματικής ομοιότητας (με τα κατάλληλα n’s τα οποία δεν πρέπει να είναι ούτε πολύ μεγάλα ούτε πολύ μικρά, αλλά δεν ορίζονται από κάποιο τύπο ή μέθοδο). Βασιζόμενοι σ’ αυτές τις μεθόδους, προτείνουμε δύο νέες τεχνικές οι οποίες όπως αποδεικνύεται μπορούν να εντοπίσουν πραγματικές τμηματικές ομοιότητες. Η πρώτη, η Lui k-n-match, επιτυγχάνει τον κατά προσέγγιση εντοπισμό των κατάλληλων n’s για τα k-n-matches, με τη βοήθεια της αλληλεπίδρασης με το χρήστη και του ελέγχου των αποδεκτών προτάσεων των k-n-matches. Πιο συγκεκριμένα, μέσω της μεθόδου k-n-match, προτείνεται για κάθε n ένα σύνολο αντικειμένων πιθανά όμοιων με το δεδομένο αντικείμενο του ερωτήματος (query object) . Ο χρήστης φιλτράρει αυτό το σύνολο, επιλέγοντας εκείνα τα αντικείμενα που θεωρεί πραγματικά όμοια με το δεδομένο. Αυτή η διαδικασία συνεχίζεται μέχρι αφού το n γίνει μεγαλύτερο από το ήμισυ των διαστάσεων των αντικειμένων, υπάρξει σύνολο προτεινόμενων αντικειμένων από το οποίο ο χρήστης δεν επιλέγει κανένα ως όμοιο . Μ’αυτόν τον τρόπο επιτυγχάνεται μεγαλύτερη εγκυρότητα των αποτελεσμάτων (λόγω της εμπλοκής του χρήστη) με περιορισμένο ταυτόχρονα αριθμό εκτελούμενων k-n-matches.
Η δεύτερη μέθοδος (INTESIS) βασίζεται στην εξής παρατήρηση: στην ουσία όταν δύο αντικείμενα μοιάζουν αυτό συνήθως σημαίνει ότι μοιάζουν στα περισσότερα χαρακτηριστικά τους, καθένα από τα οποία αναπαριστάται και αντιπροσωπεύεται από ένα σύνολο (μικρό συνήθως) διαστάσεων-πεδίων του αντικειμένου. Εάν λοιπόν οριστεί από τους ειδικούς κάθε εφαρμογής αυτή η αντιστοιχία χαρακτηριστικών και διαστάσεων - δημιουργώντας υποσύνολα διαστάσεων - τότε μπορούν να συμβούν διαδοχικά τα παρακάτω:
α) Να γίνει έλεγχος πλήρους ομοιότητας σε κάθε τέτοιο υποσύνολο διαστάσεων
β) Να οργανωθούν αυτά τα υποσύνολα σε ισάριθμα ιεραρχικά δέντρα για την εύκολη και αποδοτική διαχείρισή τους. Η επιπλέον απλούστευση αυτής της επιλογής έγκειται στο ότι δεδομένου ότι τα εν λόγω υποσύνολα διαστάσεων θα είναι μικρά, είναι πολύ εύκολη η επιλογή δέντρου γι’ αυτά, αφού σχεδόν όλα τα ιεραρχικά δέντρα έχουν μεγάλη απόδοση όταν πρόκειται για μικρό αριθμό διαστάσεων. Συνεπώς ο αναλυτής της κάθε εφαρμογής μπορεί να χρησιμοποιήσει όποιο τέτοιο δέντρο κρίνει εκείνος σαν καλύτερο ( Το R*-tree είναι η δική μας πρόταση).
Τελικά, για να ολοκληρωθεί η διαδικασία πρέπει να έχει οριστεί ένας ελάχιστος αριθμός απαιτούμενων όμοιων χαρακτηριστικών προκειμένου να θεωρηθούν δύο αντικείμενα όμοια.
Για την αξιολόγηση αυτής της μεθόδου, πρέπει αρχικά να σημειωθεί ότι αναφέρεται σε συνολικό αριθμό διαστάσεων μικρότερο του 100 και συνεπώς σε σχετικά μικρό αριθμό δέντρων. Όπως είναι φανερό, σε μονο-επεξεργαστικό σύστημα οι τελικοί χρόνοι απόκρισης είναι το άθροισμα των χρόνων κάθε δέντρου. Λαμβάνοντας υπ’όψιν το ότι τα δέντρα λόγω του μικρού αριθμού διαστάσεων που αντιστοιχούν στο καθένα έχουν πολύ καλές αποδόσεις, βγαίνει εύκολα το συμπέρασμα ότι ο εκάστοτε τελικός χρόνος απόκρισης της μεθόδου - όντας ένα μικρό πολλαπλάσιο των πολύ μικρών χρόνων προσπέλασης των δέντρων - είναι αρκετά χαμηλός. Με δεδομένο ότι η χρήση κάθε δέντρου δεν προϋποθέτει την χρήση κάποιου άλλου πριν ή μετά, οι αναζητήσεις σε κάθε δέντρο μπορούν να γίνονται παράλληλα. Συνεπώς σε πολυεπεξεργαστικό σύστημα, ο συνολικός χρόνος απόδοσης μπορεί να μειωθεί σημαντικά, φτάνοντας μέχρι και το χρόνο που απαιτείται μόνο για αναζήτηση σε ένα δέντρο (όταν υπάρχουν τόσοι επεξεργαστές όσα και δέντρα). Φυσικά, εάν λάβει κανείς υπ’όψιν του ότι η τμηματική ομοιότητα αποτελεί ένα ιδιαίτερα απαιτητικό είδος τότε όχι μόνο οι χρόνοι απόκρισης σε πολυεπεξεργαστικό σύστημα αλλά και εκείνοι του συστήματος ενός επεξεργαστή, αποτελούν ικανοποιητικές αποδόσεις.
Το τρίτο κεφάλαιο μελετά τη δυνατότητα δημιουργίας μιας νέας δομής η οποία δε θα ‘υποφέρει’ από τη μεγάλη πτώση της απόδοσης των δέντρων με την αύξηση των διαστάσεων των αντικειμένων (‘dimensionality curse’) ενώ ταυτόχρονα θα εξασφαλίζει καλή απόδοση και σε μικρό αριθμό διαστάσεων. Οι μέχρι τώρα μελέτες έχουν καταλήξει στο εξής συμπέρασμα: Τα γνωστά διαδεδομένα δέντρα αναζήτησης (είτε πρόκειται για δέντρα οργανωμένα βάση κατανομής χώρου (space partitioning) είτε για δέντρα βάση κατανομής δεδομένων (data partitioning)) αποδίδουν πολύ καλύτερα σε μικρό αριθμό διαστάσεων ενώ όσο αυτός ο αριθμός αυξάνει - ειδικά από 10 και πάνω – η απόδοση χειροτερεύει δραματικά. Το VA-File (σχήμα προσέγγισης διανύσματος) από την άλλη πλευρά - το οποίο είναι ένας απλός πίνακας-αρχείο γεωμετρικών προσεγγίσεων των αντικειμένων - με την αύξηση των διαστάσεων αποδίδει καλύτερα στην αναζήτηση ομοιοτήτων αλλά παρουσιάζει χαμηλή απόδοση σε μικρό αριθμό διαστάσεων.
Προκειμένου να ξεπεραστεί αυτή η καθοριστική εξάρτηση της απόδοσης από το πλήθος των διαστάσεων των προς διαχείριση αντικειμένων, προτείνουμε τη νέα υβριδική δομή Digenis, η οποία παντρεύει τη λογική των δέντρων αναζήτησης με κείνη των VA αρχείων. Πιο συγκεκριμένα, ορίζεται και χρησιμοποιείται ένα στατικό παραμετροποιημένο δέντρο (δέντρο Digenis) σε εννοιολογικό επίπεδο ενώ σε φυσικό επίπεδο χρησιμοποιείται το αρχείο Digenis το οποίο κατασκευάζεται με βάση το δέντρο. Με αυτή τη συσχέτιση επιτυγχάνεται αναζήτηση σε μικρό μόνο μέρος του αρχείου κατά τη διαδικασία ανεύρεσης ομοιοτήτων ανάμεσα σε αντικείμενα πολλών αλλά και λίγων διαστάσεων, γεγονός που δίνει γενικότητα και ευελιξία στη μέθοδο.
Πιο συγκεκριμένα, για το σχηματισμό του δέντρου, αρχικά ορίζονται οι οικογένειες αντικειμένων, οι οποίες αποτελούνται από αντικείμενα με μικρή απόσταση (βάση ενός προκαθορισμένου από τον εκάστοτε αναλυτή ορίου fl) και αντιπροσωπεύονται από το ‘μέσο’ αντικείμενο της οικογένειας (εάν δεν υπάρχει δημιουργείται για αυτό το ρόλο και μόνο). Κάθε κόμβος του δέντρου αντιπροσωπεύει-φιλοξενεί μία τέτοια οικογένεια. Το είδος των αποστάσεων που χρησιμοποιείται είναι η πλέον διαδεδομένη απόσταση, η Ευκλείδεια απόσταση, για την οποία ισχύει και η τριγωνική ανισότητα στην οποία θα βασιστεί μεγάλο μέρος της μεθόδου. Επίσης ένα δεύτερο όριο απόστασης (Lt) ορίζεται – από τον αναλυτή πάλι - σαν όριο με βάση το οποίο δύο αντικείμενα μπορούν να θεωρηθούν όμοια. Το δέντρο Digenis τελικά χτίζεται έχοντας ρίζα την πιο ‘κεντρική’ οικογένεια της περιοχής των αντικειμένων και κόμβους-παιδιά της τις ch πιο γειτονικές της οικογένειες, κάθε μία από αυτές έχει παιδιά της τις ch πιο γειτονικές της οικογένειες κ.ο.κ. Η δεδομένη ισχύ της τριγωνικής ανισότητας ανάμεσα στις Ευκλείδειες αποστάσεις των αντικειμένων-οικογενειών, αποδεικνύεται ένα χρήσιμο θεώρημα βάση του οποίου καθιστάται εφικτή η ασφαλής εξαίρεση μεγάλου μέρους του δέντρου από τους ελέγχους ομοιότητας, κατευθύνοντας τον τελικό έλεγχο σε μία μικρή περιοχή του. Αυτή η ανάλυση της αναζήτησης μέσα στο δέντρο είναι πολύ χρήσιμη σε ό,τι αφορά τη χρήση του αρχείου Digenis, όπου εκεί πραγματοποιείται η πραγματική αναζήτηση (φυσικό επίπεδο).
Το αντίστοιχο αρχείο Digenis στο φυσικό επίπεδο σχηματίζεται εάν αντιστοιχίσουμε σε κάθε του εγγραφή έναν κόμβο του δέντρου, ξεκινώντας από τη ρίζα του δέντρου και περνώντας από κάθε επίπεδο, από αριστερά προς τα δεξιά. Με αυτή την αντιστοίχηση, μπορούν πολύ εύκολα να χρησιμοποιηθούν οι τεκμηριωμένες τεχνικές εύκολου, ασφαλούς και γρήγορου αποκλεισμού περιοχών.
Ο απολογισμός της μεθόδου (θεωρητικά αλλά και πειραματικά) περιλαμβάνει θετικές και αρνητικές όψεις.
Θετικές όψεις:
• Το αρχείο έχει πολύ καλή απόδοση όταν διαχειριζόμαστε αντικείμενα πολλών διαστάσεων. Αυτό ήταν αναμενόμενο αφού το αρχείο λειτούργησε σαν ένα είδος VA αρχείου, όπου το ζητούμενο ήταν η δημιουργία συμπαγών γεωμετρικών προσεγγίσεων. Κι αυτό γιατί και η χρήση των οικογενειών επέφερε μία πρώτη ‘συμπίεση’ των δεδομένων αλλά και η προ-τακτοποίηση των αντικειμένων μέσω της εννοιολογικής χρήσης του δέντρου οδήγησε σε ένα είδος ομαδοποίησης γειτονικών αντικειμένων σε γειτονικές περιοχές.
• Το αρχείο έχει επίσης καλές επιδόσεις και όταν διαχειριζόμαστε αντικείμενα λίγων διαστάσεων. Αυτό συμβαίνει γιατί σε σχέση με το αρχείο VA είναι αναμενόμενα καλύτερο αφού βασίζεται σε δενδρική διάταξη, ενώ για τον ίδιο λόγο είναι ανταγωνιστικό και των παραδοσιακών ιεραρχικών δέντρων.
Αρνητικές όψεις:
• Η στατικότητα στον ορισμό του αριθμού(ch) των παιδιών ανά κόμβο του δέντρου, δημιουργεί προβλήματα στην κατασκευή του, γιατί συνήθως οι πραγματικά όμοιες οικογένειες μπορεί είναι περισσότερες ή λιγότερες από ch.
Αντιμετώπιση: Αν είναι περισσότερες, τοποθετούνται στο σύνολο των παιδιών οι ch κοντινότερες (με μικρότερες αποστάσεις από τον γονέα). Αν είναι λιγότερες, τότε ορίζεται ένα σχετικό όριο παιδιών και γεμάτων κόμβων στο δέντρο, πάνω από το οποίο τα παιδιά τοποθετούνται κανονικά στο δέντρο και οι υπόλοιποι κόμβοι μέχρι να συμπληρωθεί ο αριθμός παιδιών ch, συμπληρώνεται με κενούς κόμβους. Όταν όμως ο αριθμός των παιδιών μιας οικογένειας και οι υπόλοιποι γεμάτοι κόμβοι στο δέντρο είναι κάτω από αυτό το όριο, το αντίστοιχο προς δημιουργία δέντρο αποκόπτεται και δημιουργείται νέο μικρότερο δέντρο - με μικρότερο ch – ενώ το αρχικό δέντρο αναδιατάσσεται. Συνεπώς η τελική εφαρμογή μπορεί να περιλαμβάνει περισσότερα του ενός αρχεία Digenis, τα οποία κατά την αναζήτηση προσπελαύνονται από το μεγαλύτερο προς το μικρότερο, μέχρι να βρεθεί ομοιότητα (εάν υπάρχει).
• Μπορεί να υπάρχουν απομακρυσμένες οικογένειες – να μη συνδέονται με καμία άλλη – οι οποίες δεν μπορούν να ενταχθούν σε κανένα δέντρο.
Αντιμετώπιση: Δημιουργείται ένα Αρχείο Απομακρυσμένων (‘remote’ αρχείο) στο οποίο τοποθετούνται σειριακά οι απομακρυσμένες οικογένειες. Κατά την αναζήτηση αυτό το αρχείο προσπελαύνεται πρώτο, γιατί εφόσον εν γένει θα φιλοξενεί λίγες οικογένειες, η αναζήτηση σ’ αυτό θα είναι γρήγορη. Εάν υπάρχει ομοιότητα μεταξύ του αντικειμένου του ερωτήματος (query) και κάποιας οικογένειας του αρχείου, τότε έχει αποφευχθεί όλη η αναζήτηση στα δέντρα ενώ εάν πάλι δεν υπάρχει τέτοια ομοιότητα, λόγω του μικρού μεγέθους του αρχείου, η χρονική επιβάρυνση είναι σχεδόν αμελητέα.
Στο τελευταίο κεφάλαιο εξετάζεται ένα είδος δυναμικής αναζήτησης ομοιότητας, το οποίο ασχολείται με τις χρονικές ακολουθίες όχι των ίδιων των αντικειμένων αλλά των πεδίων (χαρακτηριστικών) τους. Δηλαδή αυτό που ανιχνεύεται είναι το κατά πόσο μοιάζει η εξέλιξη δύο χαρακτηριστικών στο χρόνο, πληροφορία που μπορεί να σταθεί πολύ χρήσιμη σε πολλά είδη εφαρμογών (ιατρικές, οικονομικές, επιστημονικές γενικά, κλπ). Χρησιμοποιώντας ένα παράδειγμα ιατρικών δεδομένων που αφορούν ορμόνες, με τη βοήθεια της προτεινόμενης μεθόδου (Chiron) εντοπίζονται με αποδοτικό τρόπο όμοια εξελισσόμενες τιμές ορμονών. Πιο συγκεκριμένα, ορίζονται νέα αντικείμενα (property course objects ή Chiron objects) τα οποία κωδικοποιούν τις μεταβολές κάθε χαρακτηριστικού, σε συγκεκριμένα χρονικά διαστήματα και στη συνέχεια αυτά τα αντικείμενα οργανώνονται σε ένα δέντρο (Chiron tree). Ο τρόπος που ορίζονται αυτά τα αντικείμενα, οι διαφορές τους καθώς και το δέντρο Chiron, καθιστούν την πλοήγηση στο δέντρο και τον εντοπισμό όμοιων Chiron αντικειμένων - και συνεπώς όμοια εξελισσόμενων χαρακτηριστικών - μια γρήγορη και εύκολη διαδικασία. Αυτό επιτυγχάνεται μέσω της κατανομής των Chiron αντικειμένων στο δέντρο Chiron με βάση τον αριθμό των διαφορετικών μεταξύ τους ψηφίων . Μ’ αυτόν τον τρόπο, δεδομένου ενός Chiron αντικειμένου, κατά την αναζήτηση όμοιών του στο δέντρο, μπορεί να ακολουθηθεί ένας απλός και συμπαγής αλγόριθμος μέσω του οποίου αποφεύγεται ο έλεγχος σε κείνα τα επίπεδα του δέντρου τα οποία φιλοξενούν Chiron αντικείμενα που σίγουρα είναι ανόμοια προς το δεδομένο αντικείμενο Chiron. Γενικά η μέθοδος κρίνεται πολλά υποσχόμενη, γιατί εκτός των άλλων θέτει νέα ανοικτά θέματα προς διερεύνηση, όπως η στατιστική ανάλυση των αποτελεσμάτων, η αναζήτηση αντίθετα εξελισσόμενων χαρακτηριστικών, η διαχείριση των μετατοπίσεων χρόνου (time shifts) ανάμεσα στα αντικείμενα πορείας χαρακτηριστικών καθώς και η βελτιστοποίηση του δέντρου Chiron.
|
|---|
