Ranking Queries Over Range Data
Φόρτωση...
Ημερομηνία
Συγγραφείς
Kotsinas, Georgios
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Today's data-driven world has made it essential to manage and analyze large volumes of temporal data efficiently. This thesis addresses the problem of identifying
the top 𝑘 time intervals that best intersect with a query interval within a given
temporal data domain. In pursuit of addressing this issue with maximal efficiency,
we further develop the HINTm index to support ranking queries.
HINTm, is a Hierarchical Index for Intervals in arbitrary domains designed for main
memory and defines a hierarchical domain decomposition which assigns each interval to at most two partitions per level. It has previously been recognized as the most
efficient interval index in the literature, has undergone numerous optimizations to
avoid unnecessary comparisons and expedite range query responses over extensive
collections of intervals. Building on its optimizations, this work adapted HINTm to
effectively handle top 𝑘 queries.
The ranking criterion is defined by the absolute interval intersection, enabling the
identification of intervals that intersect better with a given query interval. Except
from the naive approach that simply traverses the index and scans its partitions for
results, various methods were developed to prioritize partitions that contain larger
intervals first. In reference, “Top-down”, “Depth-first”, “Ordered” and “Sorted” traversals aim to optimize the processing speed of top 𝑘 queries. Additionally, a pruning
mechanism was implemented to bypass scanning index partitions that are guaranteed not to contain intervals of the final set. This pruning mechanism, termed "Upper
bounds", was deployed in two distinct versions. The first version assigns a static
Upper bound to each index partition based on the partition's endpoints. The second,
an updated version, incorporates the metadata information of the maximum interval
within each partition. Extensive experiments were conducted on four datasets with varying characteristics,
measuring the number of queries executed per second. These experiments aimed to
understand system scalability concerning different query extents and values of 𝑘.
The results indicate that larger query extents and higher values of 𝑘 are associated
with reduced throughput. However, the application of the “Upper bounds” accelerates the overall process. Finally, metadata Upper bounds provide even better performance, always with respect to the diverse characteristics of datasets being utilized.
Περιγραφή
Λέξεις-κλειδιά
Top k query, temporal data
Θεματική κατηγορία
Διαχείριση βάσεων δεδομένων
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Όνομα επιβλέποντος
Μαμουλής, Νικόλαος
Εξεταστική επιτροπή
Βασιλειάδης, Παναγώτης
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Ονόματα συντελεστών
Αριθμός σελίδων
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: CC0 1.0 Universal