Uncertainty is inherent in many novel and important applications such as market surveillance, information extraction sensor data analysis, etc. In the recent a few decades, uncertain data has attracted considerable research attention. There are various factors that cause the uncertainty, for instance randomness or incompleteness of data, limitations of equipment and delay or loss in data transfer. A probabilistic threshold range aggregate (PRTA) query retrieves summarized information about the uncertain objects in the database satisfying a range query, with respect to a given probability threshold. This thesis is trying to address and handle this important type of query which there is no previous work studying on. We formulate the problem in both discrete and continuous uncertain data model and develop a novel index structure, asU-tree (aggregate-based sampling-auxiliary U-tree) which not only supports exact query answering but also provides approximate results with accuracy guarantee if efficiency is more concerned. The new asU-tree structure is totally dynamic. Query processing algorithms for both exact answer and approximate answer based on this new index structure are also proposed. An extensive experimental study shows that asU-tree is very efficient and effective over real and synthetic datasets.

Uncertainty is inherent in many novel and important applications such as market surveillance, information extraction sensor data analysis, etc. In the recent a few decades, uncertain data has attracted considerable research attention. There are various factors that cause the uncertainty, for instance randomness or incompleteness of data, limitations of equipment and delay or loss in data transfer. A probabilistic threshold range aggregate (PRTA) query retrieves summarized information about the uncertain objects in the database satisfying a range query, with respect to a given probability threshold. This thesis is trying to address and handle this important type of query which there is no previous work studying on. We formulate the problem in both discrete and continuous uncertain data model and develop a novel index structure, asU-tree (aggregate-based sampling-auxiliary U-tree) which not only supports exact query answering but also provides approximate results with accuracy guarantee if efficiency is more concerned. The new asU-tree structure is totally dynamic. Query processing algorithms for both exact answer and approximate answer based on this new index structure are also proposed. An extensive experimental study shows that asU-tree is very efficient and effective over real and synthetic datasets.

A large part of people's lives are spent in indoor spaces such as office and university buildings, shopping malls, subway stations, airports, museums, community centers, etc. Such kind of spaces can be very large and paths inside the locations can be constrained and complex. Deployment of indoor tracking technologies like RFID, Bluetooth, and Wi-Fi can track people and object movements from one symbolic location to another within the indoor spaces. The resulting tracking data can be massive in volume. Analyzing these large volumes of tracking data can reveal interesting patterns that can provide opportunities for different types of location-based services, security, indoor navigation, identifying problems in the system, and finally service improvements. In addition to the huge volume, the structure of the unprocessed raw tracking data is complex in nature and not directly suitable for further efficient analysis. It is essential to develop efficient data management techniques and perform different kinds of analysis to make the data beneficial to the end user. The Ph.D. study is sponsored by the BagTrack Project (http://daisy.aau.dk/bagtrack). The main technological objective of this project is to build a global IT solution to significantly improve the worldwide aviation baggage handling quality. The Ph.D. study focuses on developing data management techniques for efficient and effective analysis of RFID-based symbolic indoor tracking data, especially for the baggage tracking scenario. First, the thesis describes a carefully designed a data warehouse solution with a relational schema sitting underneath a multidimensional data cube, that can handle the many complexities in the massive non-traditional RFID baggage tracking data. The thesis presents the ETL flow that loads the data warehouse with the appropriate tracking data from the data sources. Second, the thesis presents a methodology for mining risk factors in RFID baggage tracking data. The aim is to find the factors and interesting patterns that are responsible for baggage mishandling. Third, the thesis presents an online risk prediction technique for indoor moving objects. The target is to develop a risk prediction system that can predict the risk of an object in real-time during its operation so that the object can be saved from being mishandled. Fourth, the thesis presents two graph-based models for constrained and semi-constrained indoor movements, respectively. These models are used for mapping the tracking records into mapping records that represent the entry and exit times of an object at a symbolic location. The mapping records are then used for finding dense locations. Fifth, the thesis presents an efficient indexing technique, called the $DLT$-Index, for efficiently processing dense location queries as well as point and interval queries. The outcome of the thesis can contribute to the aviation industry for efficiently processing different analytical queries, finding problems in baggage management systems, and improving baggage handling quality. The developed data management techniques also contribute to the spatio-temporal data management and data mining field. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Στο πλαίσιο της διδακτορικής διατριβής αυτής προσπαθήσαμε να δώσουμε λύση στο κεντρικό πρόβλημα του σχεδιασμού και της υλοποίησης κατανεμημένων αρχιτεκτονικών συστήματος, πρωτοκόλλων και αλγορίθμων που παρέχουν την αναγκαία υποδομή για τον υπολογισμό ορισμένων βασικών καθολικών ιδιοτήτων και μεταβλητών της κατάστασης ενός Δικτύου Ομοτίμων Εταίρων (ΔΟΕ). Μπορούμε να διακρίνουμε δύο κύριες διαστάσεις καθολικών ιδιοτήτων: (α) ιδιότητες που αναφέρονται στους κόμβους του δικτύου και τα ιδιαίτερα χαρακτηριστικά τους (υπολογιστική ισχύ, συμπεριφορά, κτλ.) και (β) ιδιότητες και μεταβλητές των αντικειμένων/δεδομένων που χειρίζεται το ΔΟΕ. Για το σκοπό αυτό, κινηθήκαμε προς δύο αλληλοσυμπληρούμενες κατευθύνσεις: (α) ποσοτικοποίηση και εκμετάλλευση της ετερογένειας των κόμβων ενός ΔΟΕ, και (β) υπολογισμός εκτιμήσεων καθολικών μεταβλητών του συστήματος, με απώτερο στόχο την υποστήριξη επεξεργασίας πολύπλοκων ερωτημάτων σε συστήματα διαχείρισης δεδομένων Διαδικτυακής κλίμακας. Στο πρώτο μέρος της διατριβής αυτής, ασχοληθήκαμε με το πρόβλημα της ετερογένειας στις υπολογιστικές δυνατότητες και στις συμπεριφορές των κόμβων ενός ΔΟΕ, καθ'οδόν προς ένα πιό αποδοτικό και ανθεκτικό περιβάλλον δρομολόγησης μηνυμάτων και επεξεργασίας ερωτημάτων, σε σχέση με τα κλασσικά υπάρχοντα δομημένα δικτυακά υποστρώματα ΔΟΕ Κατανεμημένων Πινάκων Κατακερματισμού. Έτσι, πρώτα παρουσιάζουμε ένα νέο παράδειγμα αρχιτεκτονικής δόμησης των ΔΟΕ, το οποίο ονομάζουμε AESOP. Ακόμα, ασχολούμαστε με το πρόβλημα της αποδοτικής επεξεργασίας ερωτημάτων εύρους σε ΔΟΕ βασισμένα σε DHT. Η καινοτομία της προτεινόμενης προσέγγισης βρίσκεται σε αρχιτεκτονικές, αλγορίθμους και πρωτόκολλα ταυτοποίησης και κατάλληλης εκμετάλλευσης δυνατών κόμβων του δικτύων αυτών. Στο δεύτερο μέρος της διατριβής αυτής, ασχολούμστε με την κατανεμημένη εκτίμηση καθολικών μεταβλητών συστημάτων ΔΟΕ, όπως ο πληθάριθμος κατανεμημένων πολυσυνόλων, η επεξεργασία καθολικών συναθροιστικών ερωτημάτων και η διατήρηση ιστογραμμάτων επί δεδομένων κατανεμημένων σε όλους του κόμβους του ΔΟΕ, ώστε να επιτρέψουμε την μεταφορά τεχνικών βελτιστοποίησης ερωτημάτων από τα κεντρικοποιημένα περιβάλλοντα στον ευρέος κατανεμημένο χώρο των συστημάτων διαχείρισης δεδομένων Διαδικτυακής κλίμακας. / As part of this doctoral thesis we tried to solve the central problem of the design and implementation of distributed system architectures, protocols and algorithms that provide the infrastructure necessary to calculate some basic global properties and variables of a peer-to-peer network. We can distinguish two main dimensions of such properties: (a) properties pertaining to the nodes of the network and their particular characteristics (computing power, behavior, etc.) and (b) properties of objects and variables/data managed by the P2P network. For this purpose, we moved in two complementary directions: (a) quantification and exploitation of heterogeneity of nodes in P2P networks, and (b) calculation of estimates of global variables, with a view to support complex query processing in Internet-scale data management systems. First, we dealt with the problem of heterogeneity in computing capabilities and behaviour patterns of the nodes in a P2P network, en route to a more efficient and fault resilient routing and query processing infrastructure compared to classic structure DHT-based data networks. So, first we present a new architecture paradigm, called AESOP. We then use this architecture to tackle the problem of efficient range query processing in DHT-based data management systems. The innovation of the proposed approach lies in architectures, algorithms and protocols for identification and proper exploitation of the powerful nodes of these networks. Then we deal with the distributed estimation of global system variables in P2P networks, such as the cardinality of distributed multisets, distributed aggregate query processing, and the maintenance of distributed histograms over data stored across all nodes of the P2P overlay, so as to allow the porting of query processing and optimization techniques from centralized environments to the widely distributed field of Internet-scale data management systems.