Αποδοτική αναζήτηση με χρήση λέξεων - κλειδιών σε ημιδομημένα δεδομένα

Abstract

Keyword search is the most popular querying technique on large semistructured datasets, often of unknown structure, in the web. Keyword queries are simple and convenient. However, as a consequence of their imprecision, there is usually a huge number of candidate results of which only very few match the user's intent. Unfortunately, the existing semantics for keyword queries are ad-hoc and they generally fail to ``guess'' the user intent. Therefore, the quality of their answers is poor and the existing algorithms do not scale satisfactorily.In this context, three challenging problems are (a) to avoid missing useful results in the answer set, (b) to rank the results with respect to some relevance criterion and (c) to design algorithms that can efficiently compute the results on large datasets. A major challenge of a ranking approach is the efficiency of its algorithms as the number of keywords and the size and complexity of the data increase. To face this challenge most of the known approaches restrict their ranking to a subset of the LCAs (e.g., SLCAs, ELCAs), missing relevant results.In this thesis, we present a novel ranking semantics for keyword queries which is based on the concept of LCA size. Similarly to metric selection in Information Retrieval, LCA size reflects the proximity of keyword matches in the data tree. This semantics does not rank a predefined subset of LCAs and through a layered presentation of results, it demonstrates improved effectiveness compared to previous relevant approaches. To address performance challenges, we design novel stack-based algorithms, which exploit a lattice of the partitions of the keyword set to return, as an answer to a keyword query, all the results ranked on their size. This feature empowers a linear time performance on the size of the input data for a given number of query keywords. As a result, our algorithm can run efficiently on large input data for several keywords. We extend our approach to efficiently support top-k keyword query answering, with new top-k-size semantics. An extensive experimental study on various and large datasets confirms the theoretical analysis. The results show that, in contrast to other approaches, our algorithms scale smoothly when the size of the dataset and the number of keywords increase.Furthermore, we present a multi-level clustering methodology which groups together results with similar structural and semantic features, and allows the user to focus on a small subset of the results. In order to define our cluster hierarchy, we exploit homomorphisms between label paths which allow the detection of commonalities between patterns of results. An originality of our approach is that the clusters are ranked at different levels of granularity to quickly guide the user to the relevant result patterns. We design an efficient stack-based algorithm for generating result patterns and constructing the clustering hierarchy. Our extensive experimentation with multiple real datasets shows that our algorithm is fast and scalable. It is also shown that our clustering methodology allows the users to effectively retrieve their intended results, and outperforms a recent state-of-the-art clustering approach. Although keyword queries are simple and convenient, the existing semantics for keyword queries are prone to failure on ``guessing'' the user intent. Therefore, the quality of the answers is often poor. To address this issue, we introduce the novel concept of cohesive keyword queries for tree data. Intuitively, a cohesiveness relationship on keywords indicates that they should form a cohesive whole in a query result. Cohesive keyword queries allow term nesting and keyword repetition. They bridge the gap between flat keyword queries and structured queries. Although more expressive, they are as simple as flat keyword queries and they do not require any schema knowledge. We provide formal semantics for cohesive keyword queries and rank query results on the proximity of the keyword instances. We design a stack based algorithm which efficiently evaluates cohesive keyword queries. Our experiments demonstrate that our approach outperforms in quality previous filtering semantics and our algorithm scales smoothly on queries of even 20 keywords on large datasets.

Η αναζήτηση με χρήση λέξεων-κλειδιών είναι ο πλέον διαδεδομένος τρόπος αναζήτησης σε ημιδομημένα δεδομένα, συχνά άγνωστης συχνά δομής. Οι σύγχρονες μηχανές αναζήτησης δίνουν πρόσβαση σε μεγάλου όγκου δεδομένα που είναι ετερογενούς μορφής και διασκορπισμένα στο διαδίκτυο. Σε αντίθεση με τις δομημένες βάσεις δεδομένων και τις δομημένες γλώσσες ερωτήσεων που τις συνοδεύουν, σ' αυτήν την περίπτωση α) ο χρήστης δεν έχει την ανάγκη γνώσης της δομής της πληροφορίας και β) δε χρειάζεται να κατέχει εξειδίκευση σε μια γλώσσα ερωτήσεων. Τα πλεονεκτήματα αυτά συνοδεύονται από το μειονέκτημα της ασάφειας των ερωτήσεων. Το σύστημα αποτίμησης ερωτήσεων λέξεων-κλειδιών καλείται να αντιμετωπίσει αυτό το πρόβλημα, "μαντεύοντας" το νόημα της ερώτησης του χρήστη με βάση α) τις λέξεις-κλειδιά που περιέχονται στην ερώτησή του και β) τα δεδομένα πάνω στα οποία αποτιμάται η ερώτηση. Για το λόγο αυτό, η ποιότητα των αποτελεσμάτων διαφόρων προσεγγίσεων αναζήτησης είναι χαμηλή, όπως και η επίδοσή τους. Σε αυτό το πλαίσιο, υπάρχουν τρία βασικά προβλήματα: α) η αποφυγή απώλειας χρήσιμων αποτελεσμάτων στην απάντηση της αναζήτησης, β) η ταξινόμηση των αποτελεσμάτων με βάση κάποιο αξιόπιστο κριτήριο και γ) η αποδοτική αποτίμηση ερωτήσεων λέξεων-κλειδιών. Το σχήμα της πληροφορίας που ακολουθεί τη μορφή δένδρου ή γράφου ορίζει σχέσεις μεταξύ των οντοτήτων πληροφορίας, οι οποίες πρέπει να λαμβάνονται υπόψιν αλλά με τρόπο που δε θα μειώνει την ποιότητα των αποτελεσμάτων αναζήτησης. Η επίδοση των αλγορίθμων που αποτιμούν ερωτήσεις με λέξεις-κλειδιά και έχουν τη δυνατότητα να ταξινομούν τα αποτελέσματα που προκύπτουν από μεγάλες συλλογές δεδομένων είναι καίριο ζήτημα. Για την αντιμετώπιση αυτού του προβλήματος, οι περισσότερες γνωστές προσεγγίσεις περιορίζουν εκ των πρωτέρων το σύνολο των αποτελεσμάτων σε ένα υποσύνολο αυτών, πληρώνοντας το τίμημα της απώλειας σωστών αποτελεσμάτων από την απάντηση που επιστρέφουν.Στην παρούσα διατριβή, εισάγονται νέες μέθοδοι αναζήτησης σε ημιδομημένα δεδομένα. Παρουσιάζεται μια νέα σημασιολογία ταξινόμησης που βασίζεται στην έννοια του μεγέθους χαμηλότερου κοινού προγόνου. Σε αναλογία με την αναζήτηση με κριτήρια εγγύτητας στο πεδίο της Ανάκτησης Πληροφορίας (IR), το μέγεθος χαμηλότερου κοινού προγόνου αντικατοπτρίζει την εγγύτητα εμφάνισης των λέξεων-κλειδιών σε ένα δένδρο δεδομένων. Αυτή η προσέγγιση δεν απορρίπτει εκ προοιμίου κανένα αποτέλεσμα, αλλά μέσω μιας κλιμακωτής ταξινόμησης επιδεικνύει βελτιωμένη αποτελεσμάτικότητα στην αποτίμηση ερωτήσεων με λέξεις-κλειδιά, σε σύγκριση με τις έως τώρα προσεγγίσεις. Για την αντιμετώπιση του προβλήματος επίδοσης, σχεδιάσαμε μια οικογένεια αλγορίθμων που χρησιμοποιούν στοίβες. Οι αλγόριθμοι αξιοποιούν το δικτυωτό των διαμερίσεων των λέξεων-κλειδιών μιας ερώτησης, για να επιστρέψουν τα αποτελέσματα υπολογίζοντας ταυτόχρονα τα μεγέθη χαμηλότερων κοινών προγόνων. Το δικτυωτό αυτό εξασφαλίζει γραμμική απόκριση των αλγορίθμων σε σχέση με το μέγεθος εισόδου, για δεδομένο αριθμό από λέξεις-κλειδιά. Ως αποτέλεσμα, οι αλγόριθμοί μας εκτελούνται αποδοτικά σε μεγάλα σύνολα δεδομένων και για ερωτήσεις με πολλές λέξεις-κλειδιά. Επεκτείνοντας τη λογική αυτή, προχωρήσαμε στο σχεδιασμό νέων top-k αλγορίθμων, που υλoποιούν μια διαφορετική λογική επιλογής κορυφαίων k αποτελεσμάτων. Η εκτεταμένη πειραματική μας ανάλυση επιβεβαιώνει τα θεωρητικώς προδοκόμενα. Σε αντίθεση με ανάλογες προσεγγίσεις οι αλγόριθμοί μας κλιμακώνονται ομαλά καθώς ο αριθμός των λέξεων-κλειδιών και των εμφανίσεών τους σε διάφορα σύνολα δεδομένων αυξάνονται. Παρουσιάζεται, επίσης, μια πολυεπίπεδη μεθοδολογία συσταδοποίησης, που ομαδοποιεί αποτελέσματα παρόμοιας δομής και σημασιολογίας, επιτρέποντας στο χρήστη να επικεντρώνεται σε μικρό αριθμό αποτελεσμάτων. Η συσταδοποίηση αποφασίζεται από ένα σύνολο ομομορφιδμών που ορίζονται μεταξύ δενδρικών προτύπων. Οι συστάδες ορίζονται σε διαφορετικό επίπεδο λεπτεμέρειας και παρουσιάζονται εμφωλευμένες από τις γενικότερες στις ειδικότερες, καθοδηγώντας το χρήστη γρήγορα στα επιθυμητά αποτελέσματα. Για τη μέθοδο αυτή, επίσης σχεδιάστηκε ένας αποδοτικός αλγόριθμος που αποκρίνεται σε πρακτικό χρόνο, όπως επιβεβαιώνεται από την πειραματική μας μελέτη. Τα πειράματα, επίσης, κατέδειξαν ότι η μεθοδολογία συσταδοποίησης ουσιαστικά βοηθά τους χρήστες να εντοπίσουν τα επιθυμητά αποτελέσματα ξεπερνώντας σε αποτελεσματικότητα ανάλογες προσεγγίσεις.Παρόλο που οι ερωτήσεις με λέξεις-κλειδιά είναι απλές και διευκολύνουν το χρήστη, οι υπάρχουσες σημασιολογίες όσο καλά αποτελέσματα και να επιδεικνύουν κατά περίπτωση, δεν μπορούν επ ουδενί να "μαντέψουν" την πρόθεση αναζήτησης του χρήστη. Το αποτέλεσμα είναι χαμηλής ποιότητας αποτελέσματα αναζήτησης. Προς αυτήν την κατεύθυνση, εισαγάγμε μια νέα γλώσσα ερωτήσεων με συνεκτικές λέξεις-κλειδιά. Διαισθητικά, μια σχέση συνεκτικότητας ανάμεσα σε λέξεις-κλειδιά υποδεικνύει πως σε ένα αποτέλεσμα οι συγκεκριμένες λέξεις-κλειδιά θα πρέπει να σχηματίζουν ένα συνεκτικό, αδιαίρετο σύνολο. Στη γλώσσα αυτή επιτρέπεται η επανάληψη λέξεων-κλειδιών και η εμφώλευση των συνεκτικών όρων. Η μορφή αυτή ερωτήσεων γεφυρώνει το χάσμα ανάμεσα στις απλές ερωτήσεις με λέξεις-κλειδιά και τις εξελιγμένες, αυτστηρές δομημένες γλώσσες. Παρόλο που είναι πιο εκφραστικές οι ερωτήσεις με συνεκτικές σχέσεις, είναι όσο απλές στη διατύπωση είναι κι οι ερωτήσεις χωρίς συνεκτικές σχέσεις, ενώ επίσης δεν απαιτούν γνώση της δομής του συνόλου δεδομένων. Για την αποτίμηση των ερωτήσεων, σχεδιάσαμε κατάλληλο αλγόριθμο στη λογική των αλγορίθμων που αξιοποιούν το δικτυωτό των διαμερίσεων των λέξεων-κλειδιών. Η πειραματική μας μελέτη αποδεικνύει την υπεροχή της μεθόδου μας σε σχέση με παλαιότερες σημασιολογίες φιλτραρίσματος και προβάλλει την επίδοση του αλγορίθμου μας, δείχνοντας ότι έχει τη δυνατότητα αποτίμησης ακόμα και ερωτήσεων με πολύ μεγάλο αριθμό λέξεων-κλειδιών.