A study on algorithms for maximizing the influence score of spatio-textual objects

Abstract

Στις μέρες μας, χρησιμοποιούνται όλο και περισσότερο εφαρμογές που διαχειρίζονται χωρικά αντικείμενα σε συνδυασμό με περιγραφές κειμένου. Ανεπτυγμένοι τύποι ερωτημάτων και ευρετήρια δεδομένων, έχουν γίνει όχι μόνο χρήσιμα, άλλα και σχεδόν απαραίτητα, ώστε να βοηθούν τους χρήστες να χειρίζονται τον μεγάλο όγκο των διαθέσιμων δεδομένων, απαντώντας τους αποτελεσματικά στα ερωτήματά τους. Με αυτά τα δεδομένα, δίνεται στους χρήστες η δυνατότητα να θέσουν spatio-textual ερωτήματα με τις προτιμήσεις τους. Τα αποτελέσματα ενός τέτοιου ερωτήματος, συνιστώνται από spatio-textual αντικείμενα, καταταγμένα ανάλογα την απόστασή τους από μία επιθυμητή τοποθεσία και την λεκτική ομοιότητά τους με το ερώτημα. Ένα πρόβλημα που προκύπτει, είναι το πώς να επιλέξεις το πολύ b λέξεις κλειδιά, ενισχύοντας την περιγραφή ενός χωρικού αντικειμένου, ώστε να εμφανίζεται αυτό στα TOPk αποτελέσματα, σε όσο το δυνατόν περισσότερους χρήστες. Το πρόβλημα αυτό θα αναφέρεται στο εξής ως Best Term, και αποδεικνύεται ότι είναι NP-hard. Σε αυτήν την διπλωματική εργασία, μελετάμε τον σχεδιασμό και την ανάπτυξη ενός αλγορίθμου που λύνει προσεγγιστικά αυτό το πρόβλημα. Ο αλγόριθμος που παρουσιάζεται, εστιάζει στο να χρησιμοποιεί αποτελεσματικά την δομή δεδομένων ενός IR-tree, που δημιουργήθηκε από τα spatio-textual δεδομένα, ώστε να υπολογίζει τις b λέξεις που απαιτούνται. Θα παρουσιαστεί ένας εκτενής αριθμός πειραμάτων, που αποδεικνύουν την αποτελεσματικότητα του αλγόριθμου. Επίσης, θα δοθεί μια συγκριτική ανάλυση απόδοσης μεταξύ αυτού του αλγορίθμου και των ήδη υπαρχόντων. ΄Όπως θα φανεί από την μελέτη των πειραματικών αποτελεσμάτων, ο αλγόριθμος αυτός είναι μια αποδοτική λύση για το Best Term πρόβλημα.