HINT on Steroids: Batch Query Processing for Interval Data

Panagiotis Bouros, Artur Titkov, George Christodoulou, Christian Rauch, Nikos Mamoulis

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

14 Downloads (Pure)


A wide range of applications manage interval data. HINT was recently proposed to hierarchically index intervals in main memory. The index outperforms competitive structures by a wide margin, but under its current setup, HINT is able to service only single query requests. In practice however, real systems receive a large number of queries at the same time and so, our focus in this paper is on batch query processing. We propose two novel evaluation strategies termed level-based and partition-based, which both work in a per-level fashion, i.e., all queries for an index level are computed before moving to the next level. The new strategies operate in a cache-aware fashion to reduce the cache misses caused by climbing the index hierarchy or accessing multiple partitions per level, and to decrease the total execution time for a query batch. Our experimental analysis with both real and synthetic datasets showed that our batch processing strategies always outperform a baseline that executes queries in a serial fashion, and that partition-based is overall the most efficient strategy.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT
Number of pages7
ISBN (Electronic)9783893180912, 9783893180943, 9783893180950
Publication statusPublished - 2024
Event27th International Conference on Extending Database Technology, EDBT 2024 - Paestum, Italy
Duration: 25 Mar 202428 Mar 2024

Publication series

NameAdvances in Database Technology - EDBT
ISSN (Electronic)2367-2005


Conference27th International Conference on Extending Database Technology, EDBT 2024


Dive into the research topics of 'HINT on Steroids: Batch Query Processing for Interval Data'. Together they form a unique fingerprint.

Cite this