This item is provided by the institution :
University of Crete
Repository :
E-Locus Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*
share




2009 (EN)
Ομαδοποίηση αποτελεσμάτων στις μηχανές αναζήτησης του ιστού
Results clustering in web searching

Κοπιδάκη, Στυλιανή Εμμανουήλ
Kopidaki, Styliani E.

Τζίτζικας, Ιωάννης

Η συγκεκριμένη εργασία ασχολείται διεξοδικά με το πρόβλημα εύρεσης αποτελεσματικών και αποδοτικών μεθόδων για την ομαδοποίηση αποτελεσμάτων στις μηχανές αναζήτησης του Ιστού. Εν συντομία, η ομαδοποίηση αποτελεσμάτων παρέχει στους χρήστες μια γενική επισκόπηση των αποτελεσμάτων αναζήτησης, επιτρέποντας τους να εστιάσουν την προσοχή τους σε εκείνα τα τμήματα της απάντησης που ανταποκρίνονται στις πληροφοριακές τους ανάγκες. Επιπλέον, η ομαδοποίηση αποτελεσμάτων μετριάζει το πρόβλημα της αμφισημίας των λέξεων της φυσικής γλώσσας. Εντούτοις, η σύνταξη (μονολεκτικών ή περιφραστικών) ονομάτων παρουσίασης για τις παραγόμενες ομάδες είναι ένα δύσκολο πρόβλημα αφού τα ονόματα πρέπει αφενός να είναι συντακτικά ορθά και αφετέρου να επιτρέπουν στο χρήστη να προβλέψει τα περιεχόμενα των ομάδων. Συνάμα, η ομαδοποίηση αποτελεσμάτων αποτελεί τμήμα της διαδικασίας απάντησης επερωτήσεων επομένως η αποδοτικότητα είναι μια σημαντική απαίτηση. Η εργασία αυτή κάνει μια επισκόπηση των μεθόδων που έχουν προταθεί και έχουν χρησιμοποιηθεί για την ομαδοποίηση αποτελεσμάτων και εστιάζει στον αλγόριθμο Suffix Tree Clustering (STC). Ο STC είναι μια τεχνική στην οποία τα αποτελέσματα αναζήτησης (κυρίως τμήματα των κειμένων) ομαδοποιούνται γρήγορα (σε γραμμικό χρόνο), αυξητικά, και η κάθε ομάδα έχει μια φράση σαν όνομα. Η εργασία αυτή προτείνει δύο νέες μέθοδους: (α) μια παραλλαγή του STC, που λέγεται STC+, η οποία χρησιμοποιεί μια συνάρτηση βαθμολόγησης που ευνοεί τις φράσεις που εμφανίζονται στους τίτλους των εγγράφων και διαφέρει στον τρόπο με τον οποίο συγχωνεύονται οι υποψήφιες ομάδες, και (β) ενα νέο αλγόριθμο, που λέγεται HSTC, ο οποίος καταλήγει σε μια ιεραρχική δομή από ομάδες. Η συγκριτική αξιολόγηση με χρήστες έδειξε ότι οι χρήστες προτιμούν περισσότερο τους STC+ και HSTC από τον STC, και ότι ο HSTC είναι δύο φορές πιο γρήγορος από τους STC και STC+. Οι μέθοδοι αυτοί εφαρμόστηκαν πάνω στη μηχανή αναζήτησης Μίτος και το Google. Επιπλέον, τα αποτελέσματα του HSTC ενσωματώθηκαν στο μοντέλο αλληλεπίδρασης των Δυναμικών Πολυδιάστατων Ταξινομιών που υποστηρίζει η μηχανή Μίτος, ως μια επιπλέον διάσταση που συμπληρώνει τι ;ς υπόλοιπες διαστάσεις (που είναι ανεξάρτητες περιεχομένου). Η ζεύξη αυτή έχει σαν αποτέλεσμα μια αποτελεσματική, ευέλικτη και αποδοτική πλοηγητική εμπειρία. Τέλος, περιγράφονται και αναλύονται τα πειραματικά και εμπειρικά αποτελέσματα από την εφαρμογή αυτών των μεθόδων πάνω στη μηχανή Μίτος και στο Google. (EL)
This thesis elaborates on the problem of providing efficient and effective methods for results clustering in Web searching. In brief, results clustering is useful for providing users with overviews of the search results and thus allowing them to restrict their focus to the desired parts of the returned answer. In addition, results clustering alleviates the problem of ambiguity of natural language words. However, the task of deriving (single-word or multiple-word) names for the clusters (usually referred as cluster labeling) is a difficult task, because they have to be syntactically correct and predictive (should allow users to predict the contents of each cluster). Furthermore, results clustering is an online task therefore efficiency is an important requirement. This thesis surveys the methods that have been proposed and used for results clustering and focuses on the Suffix Tree Clustering (STC) approach. STC is a clustering technique where search results (mainly snippets) can be clustered fast (in linear time), incrementally, and each cluster is labeled with a phrase. This thesis proposes two novel results clustering methods: (a) a variation of the STC, called STC+, with a scoring formula that favors phrases that occur in document titles and differs in the way base clusters are merged, and (b) a novel algorithm, called HSTC, that results in hierarchically organized clusters. The comparative user evaluation showed that both STC+ and HSTC are significantly more preferred than STC, and that HSTC is about two times faster than STC and STC+. These methods where applied over Mitos Web search engine and over Google. Moreover, HSTC was integrated with the Dynamic Faceted Taxonomies interaction scheme of Mitos. The dynamic coupling of results clustering with dynamic faceted taxonomies results to an effective, flexible and efficient exploration experience. Finally, the thesis reports experimental and empirical results from applying these methods over Mitos and over Google. (EN)

text
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης

Ομαδοποίηση αποτελεσμάτων
Δέντρα καταλήξεων
Dynamically Mined Metadata
Results Clustering
Suffix trees
Web Searching
Clustering
Μηχανές αναζήτησης

Πανεπιστήμιο Κρήτης (EL)
University of Crete (EN)

English

2009-06-23


Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)