Benchmarking Adaptive Multidimensional Indices

By adaptive indexing , an index grows dynamically and progressively through query processing. This mode of index-building, well explored over the past fifteen years, proves especially useful in exploratory scenarios where prebuilt indexes do not pay off the time to construct them, as the query workload variably focuses on particular areas of the search space, or the data become quickly obsolete. Despite a significant body of work in multidimensional adaptive indexing, there remains a gap in comparative studies that evaluate these methods on equal terms in a wide spectrum of settings, including data types, distributions, sizes, and workload patterns. This work fills this gap with a comprehensive benchmark to thoroughly evaluate the performance, strengths, and limitations of existing multidimensional adaptive indexing methods across diverse scenarios, contributing valuable insights that complement previous works. Further, we suggest supplementary technical extensions that enhance the efficiency of existing methods.