Αποτελεσματικοί αλγόριθμοι και βελτιωμένες τεχνικές αναζήτησης χωρικής, χρονικής και χώρο-χρονικής πληροφορίας

Abstract

The subject of this dissertation is the invention of algorithmic techniques which assure efficient retrieval and searching (optimal or near optimal) of spatial, temporal and spatiotemporal data. Spatial data consist of points (we include either real numbers on the l-dimensional axis or d-dimensional vectors with d≥2), lines, rectangles, regions, surfaces and volumes. The representation of such data is becoming increasingly important in applications in computer graphics, computer vision, database management systems, computer-aided design, solid modeling, robotics, geographic information systems (GIS), image processing, computational geometry, pattern recognition, and other areas. We define as temporal data either the discrete time-stamps where some entities are being appeared on the time-intervals that represent the duration of its appearance. On the current dissertation the term "entity" is concerned with either a "process" in a Parallel or Distributed Environment or a multimedia object in a Database management system. Spatiotemporal data is the combination of spatial and temporal data, for example 3-dimensional moving objects. The second-chapter is concerned with the effective and efficient processing of spatiotemporal selection queries under varying degrees of approximation. Such queues may employ operations like overlaps north during, etc., and then result as a set of entities standing approximately in some spatiotemporal relation θ with respect to a query object X. The contribution of this chapter is twofold. 1) First we describe a mathematical framework for representing multidimensional relations at varying granularity levels, modelling relation approximation through the concept of relation convexity. 2) We subsequently exploit the framework to developing approximate spatiotemporal retrieval mechanisms, employing a set of existing as well as new main memory and secondary memory data structures that achieve either optimal or the best known performance in terms of time and space complexity, for both static and dynamic problems. Our new result studies the static 2D range query problem and an extension of the most well-known technique for static range queries of higher dimensions. At the end of this chapter, we describe the implementation of a real-time system which is based on the integration of GIS, GPS and GSM technologies. Incorporating efficient spatiotemporal algorithms within the GIS, the system's credibility has been increased. The third chapter is concerned with the problem of d-dimensional space searching (where d≥3) for two query types range and partial range geometric searching with Video Database Applications Let Ν be the number of points, s the number of keys specified m a partial match and partial range query and t the number of points retrieved. We present a structure that optimizes the best known time complexity for range queries O(t +logd°N) improving also the partial range query complexity from O(t + logd°2N) to 0(t +(d-s)+log'N). In particular we optimize the best known solution for three-sided range queries presented by Gabow, Bentley and Tarjan [ 60 ] which solve the problem in 0(N+M) space and O(t) time. The structure relies on the Cartesian Tree of Vuillemin [68] which in essence is a predecessor of the priority search tree. Their algorithm finds each point in the range by forming and answering an lca query [67]. This incurs a time overhead for each reported point. The algorithm for lowest common ancestors on arbitrary trees is also somewhat complicated. Here we present a modified priority search tree, which matches the performance of the structure of Gabow et al. [9] but the overall solution is simpler and faster. We also prove this by giving both theoretical and experimental evaluation. Based on this structure we present a d-dimensional data structure, which uses as its skeleton a Range tree, with its last level being replaced by our modified Priority Search tree. Thus we can achieve in a more simple and concrete way, O(t +logd2N) response time in d-dimensional range queries. Then observing a nice property of range trees we are able to perform partial range queries in O(t+(d-s)+log8N) time. We also use the above efficient geometric techniques in order to implement time and space efficient video content queries. Indexing video content is one of the most important problems in video databases. We present a simple optimal algorithm for this problem that answers certain content queries invoking video functions in linear time and space in terms of the number of the objects appearing in the video. To accomplish this, we make a straightforward reduction of this problem to the intersection problem in Computational Geometry. Our result is an improvement over the one of V S Subrahmaman [69] by a logarithmic factor in storage and is achieved by using different basic data structures. This logarithmic save is of great importance in video databases because vast space is needed to store videos and metadata for each video. Finally we present two time efficiently different approaches. We also compare the CPU times of some of our algorithms presenting experimental results. The used model is a unit cost RAM with word size w with each of the d keys having w-bits. In fourth chapter we refer to the Temporal Precedence Problem on Pine Pointer Machines. This problem asks for the design of a data structure, maintaining a set of stored elements and supporting the following two operations insert and precedes. The operation insert (a) introduces a new element a in the structure, while the operation precedes (a b) returns true if element a was inserted before element b temporally. In Ranjan et al. [104] a solution was provided to the problem with worst-case time complexity O(log logn) per operation and O(n log logn) space, where n is the number of elements inserted. It was also demonstrated that the precedes operation has a lower bound of Ω(log logn) for the Pure Pointer Machine model of computation. In this chapter we present two simple solutions with linear space and worst-case constant update time. The problem is important in two distinct ways. Firstly it is the first problem that clearly shows that the Pure Pointer Machine is a less powerful computational model than that of a Pointer Machine, since in a Pointer Machine the specific problem can be solved trivially (using time-stamps) with worst-case constant time for each operation, by using linear space. In [104] a non-constant lower bound on the precedes operation has been proved and as a consequence it was concluded that a Pointer Machine is a more powerful computational model than that of a Pure Pointer Machine. Secondly, the problem is related to a very concrete problem that arises in parallel implementation of logic programming languages. More specifically, in [102] a "tight" relationship between the And-Parallelism problem and the problem of "time stamping" on pointer machines was presented In the And-Parallelism problem, which arises from don't care non-determinism given a resolvent B1,B2, ,Bn multiple subgoals in the resolvent can be concurrently reduced. The computation can be visualized though a tree, the so called And-Tree, the root of which is labeled with the initial goal. If a node contains a conjunction B1,B2, ,Bn then it will have n children, the i-th child of the node is labeled with the body of the clause used to solve the Β. The main problem here is to find a way to efficiently manage the unifiers produced by the concurrent reduction of different subgoals. Two subgoals B1, B1 (l ≤ / ≤ / ≤ n) in the Β1 Bn resolvent should agree in the bindings of all the variables ("dependent" variables in terms of Prolog) that are common to them. In [102] it was shown how the problem of correct binding and assignment of variables in such parallel environments can be reduced to the problem of handling a dynamic tree, capable of growing and shrinking at the leaves and detecting whether the first node is the leftmost leaf in the subtree rooted at the second node. Both operations can be reduced (for more details see [102]) to the insert and precedes operations of the Temporal Precedence problem. The last chapter is concerned with the finger searching problem on a set oi 1-dimensional elements in RAM model of computation. We describe a new implicit tree structure based on Balls in Bins combinatorial games that support finger searching in O(loglogd) expected time with high probability for a large class of input distributions and insertions/deletions in O(1) worst-case update time. In the particular case we have insertions/deletions only at the end of a given set S of n elements, we present a simpler than eager partial rebuilding method of [115] matching the worst-case upper bound O(V(logd/loglogd)) of [115]. Also, in general case we have insertions/deletions anywhere we present the randomized version of [115] achieving the same time bounds with high probability.

Η παρούσα διατριβή μελετάει την κατασκευή αποδοτικών αλγορίθμων και βελτιωμένων τεχνικών αναζήτησης χωρικής, χρονικής και χώρο-χρονικής πληροφορίας. Με τον όρο «χωρική» συμπεριλαμβάνουμε όλη την ευρεία γκάμα που μπορεί να περιέχει από μονοδιάστατους κλασικούς αριθμούς μέχρι πολυδιάστατα γεωμετρικά διανύσματα στο χώρο, επίσης γραμμές, ορθογώνια, περιοχές, επιφάνειες κ.τ.λ. Η αναπαράσταση τέτοιου είδους δεδομένων έχει πολύ μεγάλη εφαρμογή σε περιοχές όπως computer γραφική, συστήματα βάσεων δεδομένων, computer σχεδίαση, αναπαράσταση μοντέλων, ρομποτική, γεωγραφικά συστήματα πληροφοριών (GIS), επεξεργασία εικόνας, υπολογιστική γεωμετρία, αναγνώριση προτύπων, και άλλες τέτοιες παρεμφερείς περιοχές. Με τον όρο «χρονική» εννοούμε είτε διακριτά time-stamps που αναπαριστούν το χρονικό σημείο στο οποίο έκαναν την εμφάνιση τους κάποιες οντότητες (αντικείμενα ή διαδικασίες) ή διαστήματα από time-stamps πάνω στον μονοδιάστατο άξονα του χρόνου που φανερώνουν διάρκεια εμφάνισης.Τέλος με τον όρο «χώρο-χρονική» εννοούμε το συνδυασμό των δύο προηγούμενων π.χ. κινούμενα πολυμεσικά τρισδιάστατα αντικείμενα κ.τ.λ. Το δεύτερο κεφάλαιο μελετάει τον τρόπο με τον οποίο μπορούμε να διαχειριζόμαστε ικανοποιητικά και αποδοτικά ερωτήματα χώρο-χρονικής αναζήτησης (spatiotemporal selection queries) σε διάφορες μορφές προσέγγισης τους. Τέτοια ερωτήματα έχουν να κάνουν με διάφορους τελεστές (operators) όπως επικαλύψεις (overlaps), νότια από (north), κατά τη διάρκεια του (during), κ.τ.λ., και το αποτέλεσμα τους είναι ένα σύνολο από οντότητες οι οποίες ικανοποιούν προσεγγιστικά κάποια χώρο-χρονική σχέση θ πάντα βέβαια σε σχέση με το αντικείμενο Χ του ερωτήματος. Η καινοτομία και συνεισφορά της δουλειάς μας συνίσταται στα εξής: i) Αρχικά περιγράφουμε ένα μαθηματικό μοντέλο αναπαράστασης πολυδιάστατων σχέσεων σε διάφορα επίπεδα λεπτομέρειας, μοντελοποιώντας την προσεγγιστική σχέση με την ιδέα της σχεσιακής κυρτότητας, ii) Αναλύουμε κύριας και δευτερεύουσας μνήμης μηχανισμούς χώρο-χρονικής ανάκτησης πληροφορίας τόσο για δυναμικά όσο και στατικά προβλήματα, περιγράφοντας τους καλύτερους ήδη υπάρχοντες μηχανισμούς καθώς και κάποιους δικούς μας οι οποίοι πετυχαίνουν βέλτιστες ή τις καλύτερες δυνατές χώρο-χρονικές πολυπλοκότητες. Τα νέα μας αποτελέσματα αφορούν το στατικό 2-διάστατο ερώτημα περιοχής καθώς και μία επέκταση των τεχνικών του [ 15] για ερωτήματα περιοχών σε περισσότερες διαστάσεις. Στο τέλος αυτού του κεφαλαίου περιγράφουμε την υλοποίηση ενός real-time συστήματος βασισμένο στην ολοκλήρωση GIS, GPS και GSM τεχνολογιών. Ενσωματώνοντας αποδοτικούς χώρο-χρονικούς αλγορίθμους μέσα στο GIS σύστημα που υλοποιήσαμε καταφέραμε και αυξήσαμε σημαντικά το χρόνο απόκρισης του. Το τρίτο κεφάλαιο μελετάει το πρόβλημα της γεωμετρικής αναζήτησης σε d-διαστάσεις (όπου d≥3) με εφαρμογές σε Video βάσεις δεδομένων. Συγκεκριμένα μελετάει τους εξής δύο τύπους ερωτημάτων: Γεωμετρικά ερωτήματα περιοχών και «μερικών» περιοχών (range και partial range queries). Έστω Ν ο αριθμός των d-διάστατων σημείων, s ο αριθμός των κλειδιών η περιοχή ερωτήματος των οποίων προσδιορίζεται εξαρχής (άρα η περιοχή ερωτήματος των εναπομεινάντων d-s κλειδιών δεν μας ενδιαφέρει, είναι δηλαδή αόριστη) και / ο αριθμός των σημείων της απάντησης που ανακτούμε. Θα παρουσιάσουμε μία δομή δεδομένων η οποία βελτιστοποιεί στην απόδοση (cpu time) τον καλύτερο γνωστό αλγόριθμο που απαντάει range queries με χρονική πολυπλοκότητα Ο(t +logd-2N), ωστόσο βελτιώνει ασυμπτωτικά τη χρονική πολυπλοκότητα για partial-range queries από 0(t +logd-N) σε 0(t+(d-s)+log8N). Στην πραγματικότητα βελτιστοποιούμε την καλύτερη γνωστή λύση για three-sided range queries των Gabow, Bentley και Tarjan [ 60 ] οι οποίοι επιλύουν το πρόβλημα σε 0(Ν+Μ) χώρο και O(t) χρόνο. Η δομή τους στηρίζεται στο Cartesian Tree του Vullemin [68] που ουσιαστικά είναι ο πρόδρομος του δέντρου προτεραιότητας. Ο αλγόριθμος τους κάνει χρήση [63] (βλέπε επίσης και [67]) της δυνατότητας απάντησης του lca (lowest common ancestor-κοντινότερος κοινός πρόγονος) ερωτήματος δύο κόμβων σε ένα τυχαίο δέντρο σε σταθερό 0(1) χρόνο. Ο αλγόριθμος βρίσκει κάθε σημείο της απάντησης εκτελώντας κάθε φορά ένα Ica ερώτημα. Η διαδικασία αυτή εμπεριέχει ένα μεγάλο time overhead για κάθε σημείο της απάντησης. Εξάλλου ο αλγόριθμος του κοντινότερου κοινού προγόνου δύο κόμβων σε τυχαία δέντρα είναι κάπως περίπλοκος. Θα παρουσιάσουμε λοιπόν ένα τροποποιημένο δέντρο προτεραιότητας που επιτυγχάνει ασυμπτωτικά τα ίδια αποτελέσματα με αυτά της δομής τοιν Gabow et al. [60] αλλά η γενική λύση απαιτεί συνολικά το πολύ πέντε lca queries για όλη την απάντηση και όχι για κάθε ένα από τα σημεία της απάντησης. Έτσι, παρόλο που η νέα μας δομή φαίνεται λιγάκι πιο περίπλοκη στην κατασκευή της αφού εισάγει νέες τεχνικές (persistent λίστες και microset table lookup), είναι αρκετά γρηγορότερη. Θα αποδείξουμε την χρονική βελτίωση της δομής μας τόσο θεωρητικά όσο και πρακτικά βάσει πειραματικών εκτιμήσεων. Με βάση λοιπόν αυτή τη νέα μας 2-διάστατη δομή θα χτίσουμε μία νέα d-διάστατη, που χρησιμοποιεί σαν σκελετό το Range tree ([65]) τα τελευταία επίπεδα του οποίου θα αντικαταστίσουμε με το δικό μας τροποποιημένο δέντρο προτεραιότητας. Έτσι μπορούμε να επιτύχουμε και πάλι τον καλύτερο γνωστό ασυμπτωτικά 0(t +logd-2N) χρόνο απόκρισης αλλά στην πράξη γρηγορότερο για d-διάστατα ερωτήματα περιοχής. Στη συνέχεια θα εκτελέσουμε partial range queries σε 0(t+(d-s)+log8N) χρόνο εκμεταλλευόμενοι μία πολύ καλή ιδιότητα των range trees. Τέλος θα χρησιμοποιήσουμε αυτές τις γεωμετρικές τεχνικές με σκοπό να υλοποιήσουμε αποδοτικά ερωτήματα video περιεχομένου σε πολυμεσικές βάσεις δεδομένων Συγκεκριμένα θα παρουσιάσουμε έναν απλό και βέλτιστο αλγόριθμο που απαντάει ερωτήματα που σχετίζονται με λειτουργίες video σε γραμμικό χρόνο και χώρο. Οι πολυπλοκότητες υπολογίζονται πάντα σε σχέση με τον αριθμό των αντικειμένων που εμφανίζονται στο video. Για να επιτύχουμε κάτι τέτοιο, μετασχηματίζουμε αυτό το πολυμεσικό πρόβλημα σε πρόβλημα τομών της υπολογιστικής γεωμετρίας. Το αποτέλεσμα μας επιφέρει βελτίωση κατά έναν λογαριθμικό παράγοντα στο χώρο του αντίστοιχου αποτελέσματος του Subrahmanian [69] και επιτυγχάνεται χρησιμοποιώντας διαφορετικές δομές αποθήκευσης. Αυτή η λογαριθμική μείωση είναι μεγίστης σημασίας στο χώρο των video databases, αν αναλογιστεί κανείς ότι απαιτούνται τεράστιες ποσότητες μνήμης για vu αποθηκεύσουμε αυτά που έχουμε συνηθίσει να τα λέμε μεταδεδομένα (metadata). Παρουσιάζουμε επιπλέον και άλλους τρεις διαφορετικούς αλγορίθμους με πολύ καλή χρονική απόδοση. Τέλος, συγκρίνουμε τους χρόνους εκτέλεσης (CPU times) κάποιων από τους παραπάνω αλγορίθμους βάσει πειραματικών αποτελεσμάτων. Χρησιμοποιούμε RAM μοντέλο υπολογισμού με μέγεθος λέξης w. Το τέταρτο κεφάλαιο μελετάει το Temporal Precedence πρόβλημα σε PPM (Pure Pointer Machine) μοντέλο υπολογισμού. Αυτό το θεμελιώδες πρόβλημα απαιτεί τη σχεδίαση δυναμικής δομής δεδομένων που να υποστηρίζει τις εξής δύο λειτουργίες: insert() και precedes(). Η λειτουργία insert(a) εισάγει ένα νέο στοιχείο α στο τέλος της δομής, καθώς η πράξη precedes(a,b) επιστρέφει true αν και μόνο αν το στοιχείο α εντέθηκε χρονικά πριν από το b. Στο paper [14] προτάθηκε λύση με χρονική πολυπλοκότητα χειρότερης περίπτωσης O(loglogn) για κάθε πράξη-λειτουργία και O(nloglogn) χώρο, όπου n ο αριθμός των στοιχείων που εντέθηκαν στη δομή. Απέδειξαν επίσης ότι το πρόβλημα έχει lower bound Ω(loglogn) για την precedes( ) πράξη σε ΡΡΜ. Σε αυτό το paper παρουσιάζουμε μία πιο απλή λύση με γραμμικό Ο(η) χώρο και βέλτιστο Ο(1) χειρότερης περίπτωσης χρόνο ενημέρωσης. Το πρόβλημα είναι πολύ σημαντικό για δύο διαφορετικούς λόγους. 1) Είναι το πρώτο πρόβλημα το οποίο αποδεικνύει καθαρά ότι το ΡΡΜ μοντέλο υπολογισμού είναι λιγότερο ισχυρά υπολογιστικό μοντέλο από το ΡΜ, καθώς στο δεύτερο μοντέλο το συγκεκριμένο πρόβλημα λύνεται τετριμμένα σε Ο(Ι) χρόνο χειρότερης περίπτωσης για κάθε πράξη και γραμικό χώρο, χρησιμοποιώντας time-stamps . Στο paper [104] αποδεικνύεται ένα μη-σταθερό κάτω όριο για την precedes πράξη και εν κατακλείδι επαληθεύεται ότι η Pointer Machine είναι πιο ισχυρό υπολογιστικό μοντέλο από την Pure Pointer Machine. 2) Το συγκεκριμένο πρόβλημα δομών δεδομένων συσχετίζεται άμεσα με ένα πολύ διακριτό πρόβλημα που έχει τις ρίζες του στην παράλληλη υλοποίηση γλωσσών λογικού προγραμματισμού. Πιο συγκεκριμένα, στο [102] παρουσιάζεται μία ισχυρή ("tight") σχέση μεταξύ ενός And-Parallelism προβλήματος με αυτό του "'time stamping" σε pointer machine μοντέλο υπολογισμού. Στο And-Parallelism πρόβλημα, βασισμένο στην ιδέα «δεν με ενδιαφέρει το μη-ντετερμηνιστικό» δοσμένου ενός συνόλου διεργασιών Β1,Β2,...,Β,, πολλές από αυτές μπορούν ταυτόχρονα να εκτελεστούν (και εν συνεχεία να διαγραφούν). Ο υπολογισμός μπορεί να αναπαρασταθεί μέσω ενός δέντρου, το λεγόμενο And-Tree, η ρίζα του οποίου αντιπροσωπεύει την αρχική διεργασία, πριν ακόμη σπάσει στις επιμέρους διεργασίες οι οποίες είναι ανεξάρτητες και θα εκτελεσθούν παράλληλα. Αν κάποιος κόμβος περιέχει μία παράλληλη συνύπαρξη διεργασιών Β1,Β2,...,Β,, τότε θα έχει n παιδιά, το i-στό παιδί του οποίου θα αποθηκεύει το κομμάτι του κώδικα που θα χρησιμοποιηθεί για την επίλυση της B,. Το βασικό πρόβλημα εδώ είναι να ευρεθεί ένας αποδοτικός τρόπος διαχείρισης των unifiers (συνενωτών) που παράγονται από την ταυτόχρονη εκτέλεση διαφορετικών διεργασιών. Δύο διεργασίες B, B1 (l ≤ / ≤ / ≤ n) που ανήκουν στο Β1…Bn σύνολο θα πρέπει να συμφωνούν στις συνδέσεις (bindings) όλων των μεταβλητών ("εξαρτημένες" μεταβλητές σύμφωνα με ορισμούς της Prolog) που είναι κοινές. Στο [102] αποδείχτηκε πώς το πρόβλημα της σωστής σύνδεσης και εγχώρησης των μεταβλητών αυτών σε τέτοια παράλληλα περιβάλλοντα μπορεί να εξομοιωθεί με το πρόβλημα χειρισμού ενός δυναμικού δέντρου, ικανό να αυξάνεται και να συρρικνώνεται στα φύλλα, στο οποίο μας ενδιαφέρει να εξακριβώνουμε πότε ο πρώτος κόμβος αποτελεί το πιο αριστερό φύλλο στο υποδέντρο με ρίζα τον δεύτερο κόμβο. Και οι δύο πράξεις μπορούν να εξομοιωθούν (για περισσότερες λεπτομέρειες δείτε το [102]) στις insert και precedes πράξεις του Temporal Precedence προβλήματος. Το τελευταίο κεφάλαιο μελετάει το πρόβλημα διερεύνησης με χρήση δακτυλοδείκτη σε ένα σύνολο μονοδιάστατων στοιχείων - αριθμών σε RAM μοντέλο υπολογισμού. Θα παρουσιάσουμε μία Νέα Δομή Δεδομένων βασισμένη στο ΙST (Interpolation Search Tree [108]) η οποία θα υποστηρίζει τη λειτουργία διερεύνησης με χρήση δακτυλοδείκτη σε O(loglogd) μέσο-αναμενόμενο χρόνο με μεγάλη πιθανότητα για μία μεγάλη κλάση Binomial κατανομών εισόδου και ενθέσεις/αποσβέσεις με σταθερό 0(1) χρόνο ενημέρωσης της δομής στη χειρότερη περίπτωση. Στην περίπτωση που έχουμε ενθέσεις/αποσβέσεις μόνο στο τέλος παρουσιάζουμε μία πιο απλή και ευκολότερα υλοποιήσιμη μέθοδο από εκείνη της «άπληστης γενικής ανακατασκευής» γνωστής και ως «eagier global rebuilding» μεθόδου που παρουσίασαν οι Anderson και Thorup στο [115] επιτυγχάνοντας τις ίδιες βέλτιστες χρονικές πολυπλοκότητες 0(V(logd/loglogd)). Επίσης στη γενική περίπτωση που έχουμε ενθέσεις/αποσβέσεις οπουδήποτε παρουσιάζουμε την randomized έκδοση του με μεγάλη πιθανότητα.