Recommender systems over distributed architectures

Abstract

The widespread adoption of social networks, where the logs to apply a frequent-pattern mining algorithm are scattered in many servers has driven the need for distributed techniques for FPM. Frequent-pattern mining algorithms belong to two major categories: either collaborative filtering, where the posts are clustered according to the interests of each user, in order to present content preferred by the group he/she belongs to, or content-based filtering, where the clickstreams of the surfers are monitored so as to discover frequently visited sets of posts. Given a frequently visited set of pages F containing k pages, a page PF can be proposed to a user, provided that the rest k-1 pages belonging to F have been requested. Nevertheless, since the current implementations are usually designed to work in systems consisting of a single server which reads the involved posts and implements one of the aforementioned kinds of FPM algorithms, they exhibit limited scalability when the number of users or the volume of data substantially increases, requiring us to move to a distributed architecture. Furthermore, taking into account that there is an increasing number of applications (e.g. in data stream mining), where new information arrives constantly, there is a need to process it quickly, without the need to reprocess or reaccess the transaction database prior to the arrival of the update portion. Moreover, in order to augment the quality of recommendations offered, the taxonomy information inherent in data considered by FPM applications (e.g. news sites, digital libraries) could be exploited by adding information about the categories the web pages belong to. Taking the aforementioned unified framework into account, this thesis presents algorithms in the fields of centralized, distributed, as well as incremental frequent-pattern mining, focusing on our contributions in the final two fields (FGP and FGP+, our implementation in centralized, taxonomy-aware FPM, have already been presented in our previous work; nevertheless, they will be also outlined in brief). The incorporation of the taxonomy information is given special attention, given its wide applicability in social media. We simply note that, despite the fact that we have conducted extensive experiments with our algorithms in web log files, they can be applied in a number of contemporary scenarios, such as digital libraries, social media, server farms, as well as content distribution networks.

Η καθολική υιοθέτηση των κοινωνικών δικτύων, όπου τα αρχεία καταγραφής που χρησιμοποιούνται για την εφαρμογή αλγορίθμων εξόρυξης συχνών προτύπων (frequent-pattern mining algorithms) είναι διασκορπισμένα σε πολλούς εξυπηρετητές δημιούργησε την ανάγκη για κατανεμημένες (distributed) τεχνικές. Οι αλγόριθμοι εξόρυξης συχνών προτύπων εντάσσονται σε δύο μείζονες κατηγορίες: (α) την κατηγορία του συνεργατικού φιλτραρίσματος (collaborative filtering), όπου οι αλγόριθμοι κατατάσσουν τις δημοσιεύσεις σε κατηγορίες, ανάλογα με τα ενδιαφέροντα του εκάστοτε χρήστη, προκειμένου να είναι δυνατή η παρουσίαση περιεχομένου, ανάλογα με την κατηγορία εκείνη, στην οποία ανήκει και (β) την κατηγορία του φιλτραρίσματος βασισμένο στο περιεχόμενο (content-based filtering), όπου οι αλγόριθμοι παρακολουθούν τη ροή αιτήσεων σελίδων (clickstream) των χρηστών του διαδικτύου, έτσι ώστε να ανακαλύφθούν συχνά συν-επισκεπτόμενα σύνολα δημοσιεύσεων. Έχοντας ένα συχνά συν-επισκεπτόμενο σύνολο ιστοσελίδων F μεγέθους k, μπορούμε να προτείνουμε σε έναν χρήστη μία σελίδα pF, υπό την προϋπόθεση ότι ο χρήστης έχει επισκεφθεί τις υπόλοιπες k-1 ιστοσελίδες που ανήκουν στο F. Παρόλα αυτά, αφού οι τρέχουσες υλοποιήσεις έχουν συνήθως σχεδιαστεί να δουλεύουν σε συστήματα που αποτελούνται από ένα μόνο εξυπηρετητή, ο οποίος διαβάζει τις εκάστοτε δημοσιεύσεις και εφαρμόζει μία από τις παραπάνω δύο κατηγορίες αλγορίθμων, εμφανίζουν περιορισμένη δυνατότητα κλιμάκωσης (limited scalability) όταν ο αριθμός των χρηστών ή ο όγκος της πληροφορίας αυξάνει σημαντικά, κάτι που καθιστά αναγκαία την υιοθέτηση κατανεμημένων (distributed) αρχιτεκτονικών. Επιπλέον, λαμβάντοντας υπόψη ότι υπάρχει αυξανόμενος αριθμός εφαρμογών [για παράδειγμα, στην εξόρυξη γνώσης από ρεύματα δεδομένων (data stream mining)], όπου νέες πληροφορίες καταφθάνουν συνέχεια, θα ήταν προτιμητέα η επεξεργασία τους όσο πιο γρήγορα γίνεται, χωρίς να απαιτείται η προσπέλαση ή εκ νέου επεξεργασία της αρχικής βάσης συναλλαγών (δηλαδή, εκείνης που υπήρχε πριν την άφιξη του νέου τμήματος). Επίσης, προκειμένου να αυξηθεί η ποιότητα των παρεχόμενων συστάσεων, η ταξονομική πληροφορία, η οποία είναι εγγενής σε αρκετά μοντέλα δεδομένων όπου εφαρμόζεται εξόρυξη συχνών προτύπων (π.χ. ειδησιογραφικοί ιστοχώροι, περιεχόμενα ψηφιακών βιβλιοθηκών κ.λπ.), μπορεί να αξιοποιηθεί προσθέτοντας πληροφορίες σχετικά με τις κατηγορίες εκείνες, στις οποίες ανήκουν οι ιστοσελίδες. Λαμβάνοντας το παραπάνω ενοποιημένο πλαίσιο υπ' όψη μας, αυτή η διατριβή παρουσιάζει αλγορίθμους στο χώρο της κεντρικοποιημένης (centralized), κατανεμημένης (distributed), καθώς και επαυξητικής (incremental) εξόρυξης συχνά εμφανιζόμενων προτύπων (frequent-pattern mining), εστιάζοντας το ενδιαφέρον μας στη συνεισφορά μας στα δύο τελευταία επιστημονικά πεδία (ο FGP, καθώς και ο FGP+, η συνεισφορά μας στον τομέα της κεντρικοποιημένης εξόρυξης γνώσης από πρότυπα, χρησιμοποιώντας και ταξονομική πληροφορία, έχουν ήδη παρουσιαστεί σε προηγούμενή μας εργασία. παρ' όλα αυτά, και αυτοί οι αλγόριθμοι παρουσιάζονται συνοπτικά). Δίνεται ιδιαίτερη προσοχή στη χρησιμοποίηση της ταξονομικής πληροφορίας, εξαιτίας της μεγάλης της εφαρμοσιμότητας στα κοινωνικά δίκτυα. Σημειώνεται ότι η συνεισφορά μας έχει δοκιμαστεί σε αρχεία καταγραφής δικτυακών τόπων (web log files). παρ' όλα αυτά, είναι δυνατή η εφαρμογή των αλγορίθμων μας και σε άλλους τομείς, όπως ψηφιακές βιβλιοθήκες (digital libraries), κοινωνικά δίκτυα (social media), φάρμες εξυπηρετητών (server farms), καθώς και δίκτυα διανομής περιεχομένου (content distribution networks).