EUVIMEDEUVIMED entdecken
Crossref

Index Intersection for High-Dimensional Range Queries

Maximilian Berens, Jens Teubner

Proceedings of the VLDB Endowment · 01.12.2025 · 19 (4) · 767-779

DOI: 10.14778/3785297.3785315 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 18.03.2026. Verfasst von Maximilian Berens und 1 weiteren Autor:innen. Die Arbeit nennt 30 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Berens, M., & Teubner, J. (2025). Index Intersection for High-Dimensional Range Queries. Proceedings of the VLDB Endowment, 19(4), 767-779. https://doi.org/10.14778/3785297.3785315

Vancouver

Berens M, Teubner J. Index Intersection for High-Dimensional Range Queries. Proceedings of the VLDB Endowment. 2025;19(4):767-779. doi:10.14778/3785297.3785315

BibTeX
@article{Berens2025,
  author = {Berens, Maximilian and Teubner, Jens},
  title = {Index Intersection for High-Dimensional Range Queries},
  journal = {Proceedings of the VLDB Endowment},
  year = {2025},
  volume = {19},
  number = {4},
  pages = {767--779},
  doi = {10.14778/3785297.3785315}
}
Kostenlos starten →