Handling Ranges in Main Memory

Speaker: Professor Nikos Mamoulis
Department of Computer Science and Engineering
University of Ioannina (UoI)

Title: Handling Ranges in Main Memory

Date: Wednesday, 19 February 2025

Time: 5:00pm - 6:00pm

Venue: Lecture Theater B (Lam Woo Lecture Theater), HKUST

Abstract:

In many applications, there is a need for indexing and searching (multidimensional) ranges, i.e., intervals or multidimensional boxes. This is a classic problem and been supported by effective access methods, such as the R-tree. Recently, given the fact that main memories have become bigger and cheaper, there is an increasing interest for efficient main-memory indices, where the objective is to minimize the computational cost of queries instead of the I/O cost. Based on this, we revisit the design and implementation of indexing (multidimensional) ranges. We focus on adaptations of classic space-partitioning methods for ranges. We effectively address the inherent problem of assigning ranges using disjoint space partitions, where a data unit may have to be assigned to multiple partitions, causing duplicate results in queries. For 1D intervals, we propose HINT, an efficient hierarchical index that has controlled space requirements, while minimizing the need for comparisons. We also propose LIT, a hybrid temporal index for transaction-time databases, which decouples the handling of static and evolving ranges.

Biography:

Nikos Mamoulis, BEng(CE) University of Patras, PhD(CS) HKUST, is a Professor at the Department of Computer Science and Engineering at the University of Ioannina (UoI). Before joining UoI, he was a faculty member at the Department of Computer Science, University of Hong Kong. His main research interests are in the management, search and analysis of complex data, with a focus on spatially enriched data. He served as PC co-chair of SSTD 2009, COMAD 2013, and HDMS 2014, as a general chair of SSDBM 2008, EDBT 2023, and as a PC member in more than 150 conferences. He has been an Associate Editor for ACM TSAS, VLDB Journal, IEEE Transactions on Knowledge and Data Engineering, Knowledge and Information Systems, and Geoinformatica Journal. He is a Senior ACM member. He has published over 250 papers in top international conferences and journals of data management and mining.