Επεξεργασία ερωτημάτων ομοιότητας και κυριαρχίας σε πολυδιάστατους χώρους

Abstract

This thesis studies the processing of similarity and dominating queries between objects in spatial databases, in spatial networks and generally in multidimensional spaces. It presents the design, the analysis and the study of: (i) new similarity measures between trajectories of moving objects in space-time, with efficient processing algorithms and efficient indexing schemes, (ii) new selectivity estimation methods in spatial and general networks, (iii) a new efficient and progressive algorithm for graph node clustering via transitive node similarity, (iv) new efficient and progressive algorithms for processing of subspace top-k dominating queries in multidimensional datasets, which can be applied also in distributed environments, (v) new efficient and progressive algorithms of top-k dominating queries in metric spaces, and (vi) new estimation methods for the maximum domination value and the skyline cardinality in multidimensional datasets. The proposed algorithms and methods, for the processing of similarity and dominating queries, were designed for demanding applications with the following criteria: (i) to minimize the overall processing cost (CPU and I/O cost), (ii) to minimize the total required space in main memory for the query processing, (iii) to maximize the accuracy and the efficiency of the returned results, (iv) to minimize their complexity, (v) to provide the results in a progressive manner (as soon as the first results are available they can be returned to the user, while more answers are being prepared). The study for the processing of similarity and dominating queries has been completed with the extensive experimental evaluation and comparison of all new proposed methods and algorithms. Moreover, all the proposed methods and algorithms have been implemented in C++, and exhaustive experiments were performed for their comparison using real and synthetic datasets. The experimental results show that the proposed methods can be used efficiently in similarity and dominance applications as well as in demanding environments that manage these applications. In addition, the proposed methods have significant applications in different domains like: spatial databases, general databases, information retrieval, knowledge discovery, data mining, geographical information systems, road network applications, prediction systems, web applications, search engines, distributed and parallel environments, social networks, web communities discovery.

Η διατριβή αυτή πραγματεύεται τα ζητήματα της ομοιότητας και της κυριαρχίας μεταξύ αντικειμένων σε χωρικές βάσεις δεδομένων, σε χωρικά δίκτυα και γενικά σε πολυδιάστατους χώρους. Στο περιεχόμενό της σχεδιάζονται, αναλύονται, μελετούνται και προτείνονται: (α) νέα μέτρα ομοιότητας τροχιών κινούμενων αντικειμένων στο χώρο και στο χρόνο, αποδοτικοί αλγόριθμοι επεξεργασίας ερωτημάτων ομοιότητας των τροχιών αυτών και αποδοτικές μέθοδοι δεικτοδότησής τους, (β) νέες μέθοδοι εκτίμησης της επιλεξιμότητας ερωτημάτων σε περιοχές χωρικών και γενικών δικτύων, (γ) ένας νέος προοδευτικός και αποδοτικός αλγόριθμος για την ομαδοποίηση των κόμβων ενός γράφου με μέτρα μεταβατικής ομοιότητας μεταξύ των κόμβων του, (δ) νέοι προοδευτικοί και αποδοτικοί αλγόριθμοι επεξεργασίας top-k ερωτημάτων κυριαρχίας σε δυναμικά πολυδιάστατα σύνολα δεδομένων με δυνατότητα εκτέλεσής τους σε υποχώρους και σε κατανεμημένα περιβάλλοντα, (ε) νέοι προοδευτικοί και αποδοτικοί αλγόριθμοι επεξεργασίας top-k ερωτημάτων κυριαρχίας σε μετρικούς χώρους και (στ) νέες μέθοδοι εκτίμησης του μέγιστου σκορ κυριαρχίας και του πλήθους των αντικειμένων skyline σε πολυδιάστατα σύνολα δεδομένων. Η κατασκευή των προτεινόμενων αλγορίθμων και μεθόδων για την επεξεργασία ερωτημάτων ομοιότητας και κυριαρχίας έγινε για απαιτητικά περιβάλλοντα εφαρμογών με κριτήρια: (α) την ελαχιστοποίηση του συνολικού κόστους επεξεργασίας (κόστους υπολογισμών και κόστους προσπελάσεων), (β) την ελαχιστοποίηση του συνολικού χώρου μνήμης που απαιτείται για την εκτέλεσή τους, (γ) την μεγιστοποίηση της ακρίβειας και της επιτυχίας των αποτελεσμάτων που επιστρέφουν, (δ) την ελαχιστοποίηση της πολυπλοκότητάς τους, (ε) την προοδευτική εμφάνιση των αποτελεσμάτων τους ώστε ο χρήστης να έχει όσο το δυνατόν άμεσα τα πρώτα αποτελέσματα. Η έρευνα που έγινε στο χώρο της επεξεργασίας ερωτημάτων ομοιότητας και κυριαρχίας ολοκληρώθηκε με τη διεξοδική πειραματική αποτίμηση και σύγκριση όλων των νέων μεθόδων και αλγορίθμων που αναφέρθηκαν προηγουμένως. Επίσης, έγινε πλήρης υλοποίηση όλων των προταθέντων μεθόδων και αλγορίθμων σε C++ και διεξήχθησαν εξαντλητικά πειράματα για τη σύγκρισή τους σε πραγματικά και συνθετικά σύνολα δεδομένων. Από τα αποτελέσματα προέκυψε ότι οι νέες αυτές μέθοδοι μπορούν να χρησιμοποιηθούν αποτελεσματικά σε εφαρμογές ομοιότητας και κυριαρχίας, καθώς και σε απαιτητικά περιβάλλοντα που χειρίζονται τις εφαρμογές αυτές. Επιπλέον, έχουν σημαντικές πρακτικές εφαρμογές σε διάφορα επιστημονικά πεδία όπως: σε χωρικές βάσεις δεδομένων, σε γενικές βάσεις δεδομένων, σε συστήματα ανάκτησης πληροφορίας και ανακάλυψης γνώσης, σε γεωγραφικά συστήματα πληροφοριών, σε εφαρμογές οδικών δικτύων, σε συστήματα πρόβλεψης, σε εφαρμογές του διαδικτύου, σε μηχανές αναζήτησης, σε κατανεμημένα και σε παράλληλα συστήματα, σε κοινωνικά δίκτυα, σε ανακάλυψη κοινοτήτων στο διαδίκτυο.