| Περίληψη |
Η συνεχής αύξηση των διαθέσιμων πληροφοριών στον παγκόσμιο ιστό έχει ως αποτέλεσμα την
ολοένα και περισσότερη χρησιμοποίησητεχνολογιών δημοσιεύσεως περιεχομένου, για την
έγκαιρη διάθεση παραγόμενης πληροφορίας.
Οι τεχνολογίες δημοσιεύσεως περιεχομένου, στην ουσία ενισχύουν το παραδοσιακό μοντέλο
έλξης (pull) που εφαρμόζεται κατά την αναζήτηση και περιήγηση των ιστοσελίδων με
πρωτόκολλα του διαδικτύουγια δημοσιεύσεις και συνδρομές βασιζόμενες στο μοντέλο ώθησης.
Σήμερα, τεχνολογίες για την δημοσίευση περιεχομένου, όπως για παράδειγμα RSS και
Atom,χρησιμοποιούνται σε μια ευρείας ποικιλίας από εφαρμογές που κυμαίνονται από μεγάλης
κλίμακας μετάδοση ειδησεογραφίας μέχρι μικρής κλίμακας ανταλλαγής πληροφοριών μελών των
κοινωνικών δικτύων. Ωστόσο, οι υπάρχοντες τεχνολογίες δημοσίευσης περιεχομένου RSSή Atom
παρουσιάζουν σοβαρούς περιορισμούς για την αντιμετώπιση της υπερφόρτωσης της πληροφορίας
στο σημερινό περιβάλλον του Web 2.0 , ενώ παράλληλα συνεπάγονται μια δυνατή αλληλεξάρτηση
μεταξύ των δυο συμβαλλομένων πλευρών (συνδρομητές και εκδότες).
Στην εργασία αυτή, μας ενδιαφέρει να επεκτείνουμε υπάρχοντα συστήματα
Δημοσιεύσεων/Συνδρομών προτεινόμενα για το διαδίκτυο με λειτουργίες όπως φιλτράρισμα με
βάση το περιεχόμενο και συνάθροισης. Συγκεκριμένα θα θέλαμε να επιτρέψουμε στους χρήστες
να εκφράζουν τις προτιμήσεις τους σε περιεχόμενο με λέξεις κλειδιά (σε αντίθεση με την
συνδρομή σε ένα κανάλι RSS) οι οποίες θα ικανοποιούνται σε πραγματικό χρόνο πάνω από ροές
αντικειμένων RSS (RSSitems)που προέρχονται από μεγάλο πλήθος διαφορετικώνκαναλιών
(RSSfeeds).
Πολλές δομές έχουν προταθεί στην βιβλιογραφία για την ευρετηρίαση συνδρομών πάνω από ροές
δομημένης πληροφορίας με την μορφή συνόλου πεδίο-τιμή ζευγών (attribute-valuepairs).
Δυστυχώς, λόγω της υψηλής διαστατικότητας (highdimensionality) της αδόμητης πληροφορίας,
οι συγκεκριμένες δομές δεν μπορούν να εφαρμοστούν αποτελεσματικά για την ευρετηρίαση
συνδρομών που σχηματίζονται από σύνολα λέξεων-κλειδιών. Σε αυτή την συγκεκριμένη δουλεία
προτείνουμε μια καινοτόμα δομή βασισμένη στο Trie η οποία εκμεταλλεύεται τις σχέσεις
επαλληλίας μεταξύ των συνδρομών για να αντιμετωπίσει θέματα κλιμακωσιμότητας κατά την
ευρετηρίαση και αναζήτηση συνόλων από λέξεις κλειδιά.
Για να ανταπεξέλθει στους μεγάλους ρυθμούς δημοσίευσης περιεχομένου των RSSfeeds(για
παράδειγμα την εκρηκτική δημοσίευση αντικειμένων ειδησεογραφίας RSS)και τις μεγάλες
κοινότητες συνδρομητών (για παράδειγμα εκατομμύρια συνδρομών), ο χώρος αναζήτησης που
κατασκευάζει η προτεινόμενη δομή μας είναι σημαντικά πιολεπτομερείς από την περίπτωση του
ευρετηρίου βασισμένου στους μετρητές (Count-based), ιδιαίτερα όταν πρόκειται για πολύ
δημοφιλής όρους, ενώ ταυτόχρονου δεν χρειάζονται περεταίρω δομές δεδομένων (για
παράδειγμα Counter) για να ανακαλύψει το σύνολο των συνδρομών που καλύπτει το εισερχόμενο
αντικείμενο ειδησεογραφίας. Πιο συγκεκριμένα, το βάθος του Trie οριοθετείτε από το
μέγεθος των συνδρομών που έχουν ευρετηριασθεί (κάτω από ρεαλιστικές προϋποθέσεις είναι
μικρές από 2 έως 6 όρους), ενώ το πλάτος του οριοθετείτε από το μέγεθος του λεξιλογίου
των ευρετηριασμένων όρων (κάτω από ρεαλιστικές προϋποθέσεις είναι μεγάλο και φθάνει έως
και τους 1,500,000 όρους).
Επιπρόσθετα, ο συνολικός αριθμός των όρων και γενικότερα η μορφολογία τουTrie ,
επηρεάζεται από την κατανομή των όρων του λεξιλογίου και της κατάταξης που υποθέτει το
ευρετήριο για την ευρετηρίαση συνδρομών (κάτω από ρεαλιστικές προϋποθέσεις η κατανομή των
όρων ακολουθεί κατανομές ισχύος (powerlaw) ): όταν η διαβάθμιση των όρων στην συνδρομές
δεν παραβιάζει την αρχική κατανομή που θεωρεί το Trie τότε ένα μεγάλο πλήθος από ψιλά
διαβαθμισμένους όρους θα υπάρχουν ως ένα αριστερά βαθύ (leftdeep) Trie, ενώ στην αντίθετη
περίπτωση, ένας μεγάλος αριθμός από χαμηλά διαβαθμιζόμενους όρους θα εμφανιστεί ως ένα
δεξιά βαθύ (rightdeep) Trie. Πέραν της μορφολογίας, ο χρόνος ταιριάσματος εξαρτάται
κυρίως από το μέγεθος του εισερχόμενου αντικειμένου ειδησεογραφίας (κάτω από ρεαλιστικές
προϋποθέσεις κυμαίνεται μεταξύ 5 και 50 όρων). Σε αυτό το πλαίσιο, έχουμε εφαρμόσει ένα
πλήθος από βελτιστοποιήσεις που αφορούν τις απαιτήσεις μνήμης τόσο sτο Trie όσο και σε
(Count-based) ευρετήριο ενώ αποτιμήσαμε πειραματικά τις επιδόσεις τους σε μνήμη και
χρόνο. Έχουμε δείξει, ότι το Trie, υπερτερεί του Count-based ευρετηρίου από 1 έως και 3
τάξης μεγέθους, με 2 φορές μεγαλύτερες απαιτήσεις χώρου. Παρόλο το μεγάλο μέγεθος του
λεξιλογίου και του πλήθος των συνδρομών, οι απαιτήσεις χρόνου για το Trie αυξάνονται
υπό-γραμμικά (sub-linear) σε σχέση με τον αριθμό των συνδρομών που έχουν ευρετηριάσει,
ενώ για το Count-based ευρετήριο η αύξηση είναι γραμμική. Η απόδοση που επιτυγχάνει το
Trie, όταν το πλήθος των ευρετηριασμένων συνδρομών είναι 10,000,000, είναι ~500
αντικείμενα ειδησεογραφίας ανά δευτερόλεπτο.
|
Subscription Indexes for Web Syndication Systems
