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

Μαροπάκη, Στέλλα; Maropaki, Stella

dc.contributor.advisor	Δουλκερίδης, Χρήστος
dc.contributor.author	Μαροπάκη, Στέλλα
dc.contributor.author	Maropaki, Stella
dc.date.accessioned	2017-09-04T08:40:46Z
dc.date.available	2017-09-04T08:40:46Z
dc.date.issued	2016-03
dc.identifier.uri	https://dione.lib.unipi.gr/xmlui/handle/unipi/9891
dc.description.abstract	Στις μέρες μας, χρησιμοποιούνται όλο και περισσότερο εφαρμογές που διαχειρίζονται χωρικά αντικείμενα σε συνδυασμό με περιγραφές κειμένου. Ανεπτυγμένοι τύποι ερωτημάτων και ευρετήρια δεδομένων, έχουν γίνει όχι μόνο χρήσιμα, άλλα και σχεδόν απαραίτητα, ώστε να βοηθούν τους χρήστες να χειρίζονται τον μεγάλο όγκο των διαθέσιμων δεδομένων, απαντώντας τους αποτελεσματικά στα ερωτήματά τους. Με αυτά τα δεδομένα, δίνεται στους χρήστες η δυνατότητα να θέσουν spatio-textual ερωτήματα με τις προτιμήσεις τους. Τα αποτελέσματα ενός τέτοιου ερωτήματος, συνιστώνται από spatio-textual αντικείμενα, καταταγμένα ανάλογα την απόστασή τους από μία επιθυμητή τοποθεσία και την λεκτική ομοιότητά τους με το ερώτημα. Ένα πρόβλημα που προκύπτει, είναι το πώς να επιλέξεις το πολύ b λέξεις κλειδιά, ενισχύοντας την περιγραφή ενός χωρικού αντικειμένου, ώστε να εμφανίζεται αυτό στα TOPk αποτελέσματα, σε όσο το δυνατόν περισσότερους χρήστες. Το πρόβλημα αυτό θα αναφέρεται στο εξής ως Best Term, και αποδεικνύεται ότι είναι NP-hard. Σε αυτήν την διπλωματική εργασία, μελετάμε τον σχεδιασμό και την ανάπτυξη ενός αλγορίθμου που λύνει προσεγγιστικά αυτό το πρόβλημα. Ο αλγόριθμος που παρουσιάζεται, εστιάζει στο να χρησιμοποιεί αποτελεσματικά την δομή δεδομένων ενός IR-tree, που δημιουργήθηκε από τα spatio-textual δεδομένα, ώστε να υπολογίζει τις b λέξεις που απαιτούνται. Θα παρουσιαστεί ένας εκτενής αριθμός πειραμάτων, που αποδεικνύουν την αποτελεσματικότητα του αλγόριθμου. Επίσης, θα δοθεί μια συγκριτική ανάλυση απόδοσης μεταξύ αυτού του αλγορίθμου και των ήδη υπαρχόντων. ΄Όπως θα φανεί από την μελέτη των πειραματικών αποτελεσμάτων, ο αλγόριθμος αυτός είναι μια αποδοτική λύση για το Best Term πρόβλημα.	el
dc.format.extent	64	el
dc.language.iso	en	el
dc.publisher	Πανεπιστήμιο Πειραιώς	el
dc.rights	Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/4.0/	*
dc.title	A study on algorithms for maximizing the influence score of spatio-textual objects	el
dc.title.alternative	Μελέτη αλγορίθμων για τη μεγιστοποίηση βαθμού επιρροής σε spatio-textual αντικείμενα	el
dc.type	Master Thesis	el
dc.contributor.department	Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Ψηφιακών Συστημάτων	el
dc.description.abstractEN	Nowadays, more and more applications are used that manage spatial objects annotated with textual descriptions. Advanced query operators and data indexes have become, not just useful, but indispensable, in order to help users handle the huge amount of available data by answering efficiently in their queries. With these data, users are offered the opportunity to pose spatio-textual queries with their preferences. The results of such a query consists of spatio-textual objects ranked according to their distance from a desired location and to their textual relevance to the query. A problem that arises from this context is how to select a set of at most b keywords to enhance the description of a spatial object, in order to make the object appear in the TOPk results of as many users as possible. This problem is referred in later work as Best Term and it is proven that it is NP-hard. In this thesis we study the design and development of an algorithm that approximately solves this problem. The presented algorithm focuses on using efficiently the data structure of an IR-tree index, that is build over the spatio-textual data, in order to compute the b keywords needed. An extended number of experiments will be demonstrated that will show the effectiveness of the proposed algorithm. A comparative performance analysis will be provided for this algorithm and the already introduced algorithms as baselines. As it will be shown by the experimental studies, this algorithm is an efficient solution for the Best Term problem.	el
dc.contributor.master	Ψηφιακά Συστήματα και Υπηρεσίες	el
dc.subject.keyword	Spatio-textual objects	el
dc.subject.keyword	Algorithms	el
dc.subject.keyword	Information systems	el

Files in this item

Name:: Maropaki_Stella.pdf
Size:: 722.8Kb
Format:: PDF
Description:: Μεταπτυχιακή διατριβή

View/Open

This item appears in the following Collection(s)

Τμήμα Ψηφιακών Συστημάτων
Department of Digital Systems

Show simple item record

Except where otherwise noted, this item's license is described as
Attribution-NonCommercial-NoDerivatives 4.0 Διεθνές