Title

Index Intersection for High-Dimensional Range Queries

Authors

Maximilian Berens and Jens Teubner,

Published

Proceedings of the VLDB Endowment, Volume 19, Issue 4, pages 767-779, December 2025

Abstract

For high-dimensional analytics queries in scientific domains, a full table scan is often seen as the only feasible execution path, even if result cardinalities are known to be small. In this paper, we argue for intersecting multiple indices built over medium-sized attribute subsets (Teams) as a means to produce a list of (candidate) tuple IDs for further processing. While this strategy is compatible with various index structures, significant discriminative power lies in the combined selectivity of multiple predicates. Akin to bitmap indices and VA-files, adopting simple and lightweight index approaches for each Team, instead of highly accurate but costly ones, still enables high overall selectivity and precision. Thus, the focus shifts away from individual indices towards their efficient intersection. Teams with just 1 member/attribute (bitmap indices) are outperformed for selective queries due to the inability to avoid access to large parts of the index. For example, Teams with 5 members are up to 6–7 times faster for 85 dimensions and require 1.58–2.07 times less storage. Team-based Indexing is most useful for queries with high selectivity and dimensionality, such as the search for rare objects.

Download & Links

https://doi.org/10.14778/3785297.3785315

Github repository (also contains Slides & Poster)

Errata

• In the paper figures featuring a calculated, ideal runtime VA file (figure 8), the volume for the VA file was calculated with 3 bytes, instead of 3 bits. This improves the theoretical baseline wrt. to our prototype runtime measurements, but does not change the scalability argument in any way. As already noted in the paper, our prototype does not feature a full-fledged execution engine and lacks several optimizations that would allow it to capitalize on the significant reduction in access volume, even for lower-dimensional tables/queries (e.g., 2-3 Teams or ~16 dimensions). This error was already fixed for the figures shown in the slides and poster and all presentations are based on the correct numbers.

Publication Log

01.06.2025: Initial submission.

16.07.2025: Revision notification (weak reject, weak accept, weak accept).

15.11.2025: Accept notification (Reject, Accept, Accept).

01.09.2026: Presented Slides and poster @ VLDB 2026 in Boston, MA

09.09.2026: Added Publication Log and github link. Added Errata for an error in the plots.