Ranking Queries Over Range Data
| dc.contributor.author | Kotsinas, Georgios | en |
| dc.date.accessioned | 2024-07-05T11:31:20Z | |
| dc.date.available | 2024-07-05T11:31:20Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/38152 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.17858 | |
| dc.rights | CC0 1.0 Universal | * |
| dc.rights.uri | http://creativecommons.org/publicdomain/zero/1.0/ | * |
| dc.subject | Top k query, temporal data | en |
| dc.title | Ranking Queries Over Range Data | en |
| dc.type | masterThesis | en |
| heal.abstract | 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. | en |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.academicPublisherID | uoi | el |
| heal.access | free | el |
| heal.advisorName | Μαμουλής, Νικόλαος | el |
| heal.classification | Διαχείριση βάσεων δεδομένων | |
| heal.committeeMemberName | Βασιλειάδης, Παναγώτης | el |
| heal.dateAvailable | 2024-07-05T11:32:20Z | |
| heal.fullTextAvailability | true | |
| heal.language | en | el |
| heal.publicationDate | 2024-06-27 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | masterThesis | el |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Master Thesis Kotsinas.pdf
- Μέγεθος:
- 2.46 MB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 3.22 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: