Back to search

University of Ioannina

Adaptive Indexing for Complex Data

Abstract

dc:description

As data continues to grow in both volume and complexity, especially in the context of multidimensional datasets, traditional indexing methods often fail to offer efficient solutions for large-scale data exploration. Constructing an index upfront can be costly and inefficient, particularly when query volumes are low or have unpredictable patterns. Adaptive indexing addresses this challenge by dynamically building and optimizing an index incrementally, following the query workload. This approach ensures that the indexing structure evolves to meet the specific needs of the queries being executed, reducing the cumulative cost of index construction and usage. It proves particularly advantageous in environments where query workloads are small or skewed. By building an index only on relevant data, adaptive indexing offers an efficient, flexible solution for accelerating exploratory search operations without the high cost of constructing and maintaining a pre-built index. This is especially beneficial for data analysis tasks, where the goal is to query large, multidimensional datasets stored in main memory efficiently. Adaptive indexing has shown success for single-attribute or simpler data models; however, it encounters challenges when applied to complex spatial data objects and multidimensional range queries. Existing methods for multidimensional adaptive indexing partition space into orthotopes (hyperrectangular units), but this approach is highly ineffective in high-dimensional spaces. To address this limitation, we propose an alternative method for adaptive high-dimensional indexing that partitions the space around query centers into units defined by hyperspheres, leveraging previously computed distances, with the query centers serving as vantage points. Several adaptive indexing techniques have been developed for multidimensional range queries, each with its own strengths and weaknesses. There is a lack of comparative studies that evaluates these methods under diverse conditions, including different data types, distributions, sizes, and workload patterns. To fill this gap, we have developed a comprehensive benchmark to rigorously evaluate the performance, strengths, and weaknesses of existing multidimensional adaptive indexing methods across various scenarios, providing valuable insights that complement previous research. Additionally, we propose technical extensions that enhance the efficiency of existing methods. Finally, we note that existing spatial adaptive indexing methods are generally designed for static data, available in a one-off manner. To date, no spatial adaptive indexing method can accommodate interleaved data updates during data exploration. We propose an update mechanism for adaptive in-memory indices for multidimensional objects, enabling the index to absorb data insertions as they arrive while maintaining up-to-date accuracy. Our design integrates insertions into the structure progressively, allowing them to gradually move down the hierarchy as they accumulate, while reorganizing the underlying data array by moving and splitting partitions. In summary, this dissertation provides a comprehensive exploration of adaptive indexing techniques for multidimensional data, addressing key challenges in efficiently handling large-scale data exploration and complex query workloads. It introduces a novel approach to high-dimensional adaptive indexing by leveraging query centers as vantage points, overcoming the limitations of traditional partitioning methods. Through a proposed benchmark, the dissertation systematically evaluates existing multidimensional adaptive indexing techniques across various data types, distributions, and query patterns, offering valuable insights for optimizing indexing performance. Furthermore, it presents a unique update mechanism that enables dynamic adaptation to real-time data insertions and deletions, ensuring the index remains up to date during data exploration. These contributions significantly advance the field of adaptive indexing, providing practical solutions for managing and querying complex, multidimensional data in dynamic environments.

Degree

thesis:*
Grantor dc:publisher
University of Ioannina
Year dc:date
2025

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Lampropoulos, Konstantinos
  • Λαμπρόπουλος, Κωνσταντίνος

Subjects

dc:subject × 17

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/58799

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Lampropoulos, Konstantinos; Λαμπρόπουλος, Κωνσταντίνος. Adaptive Indexing for Complex Data. University of Ioannina, 2025. http://hdl.handle.net/10442/hedi/58799