Index Intersection for High-Dimensional Range Queries

doi:10.14778/3785297.3785315

2025-12-01

PRE

Maximilian Berens *

Jens Teubner

DOI：10.14778/3785297.3785315

原文链接

原文求助

摘要

En 中文

针对科学领域中高维分析查询，全表扫描常被视为唯一可行的执行路径，即使已知结果基数很小。本文提出通过在中等大小的属性子集（Teams）上构建多个索引的交集，作为生成待处理候选元组ID列表的方法。虽然该策略与各种索引结构兼容，但其显著区分能力在于多个谓词的联合选择性。类似于位图索引和VA文件，采用简单轻量级的索引方法（而非高精度但成本高昂的方法）仍能实现高整体选择性和精度。因此，关注点从单个索引转向其高效交集。对于选择性查询，仅包含1个成员/属性的Teams（位图索引）因无法避免访问索引大部分区域而表现不佳。例如，5成员的Teams在85维情况下可快6-7倍，且存储需求减少1.58-2.07倍。基于Teams的索引对于高选择性和高维度的查询（如稀有对象搜索）最为适用。

Keyword:

Team-based Indexing

High-dimensional analytics

Index intersection

Selective queries

Range queries

期刊

Proceedings of the VLDB Endowment

IF:

3.3

论文数:

563

被引数:

1.2W

机构

dortmund university of technology

学者数:

9.4K

论文数: 9.1K

被引数: 15

lamarr institute for machine learning & artificial intelligence

学者数:

论文数: 7

被引数: 0

引用论文

Decoding billions of integers per second through vectorization

Software: Practice and Experience

IF0

2013-05-28

OAAI

D. Lemire; L. Boytsov

Better bitmap performance with Roaring bitmaps

Software: Practice and Experience

IF0

2015-04-21

OAAI

Samy Chambi; Daniel Lemire; Owen Kaser; Robert Godin

Memory-Efficient Key/Foreign-Key Join Size Estimation via Multiplicity and Intersection Size

2021 IEEE 37th International Conference on Data Engineering (ICDE)

IF0

2021-04-01

PREAI

Muller,Magnus; Flachs,Daniel; Moerkotte,Guido

Identifying and Filtering Near-Duplicate Documents 识别和过滤近乎重复的文档

Lecture Notes in Computer Science

IF0

2002-11-07

PREAI

Andrei Z. Broder

Introduction to Information Retrieval

IF0

2012-06-05

OAAI

Christopher D. Manning; Prabhakar Raghavan; Hinrich Schütze

Learned cardinality estimation

Proceedings of the VLDB Endowment

IF0

2022-01-14

PREAI

Ji Sun; Jintao Zhang; Zhaoyan Sun; Guoliang Li; Nan Tang

Efficient Set Intersection for Inverted Indexing

ACM TRANSACTIONS ON INFORMATION SYSTEMS

IF9.1

2010-12-27

PREAI

Culpepper, J. Shane; Moffat, Alistair

Zstandard Compression and the 'application/zstd' Media Type

IF0

2021-02-01

PREAI

Y. Collet

Efficient binning for bitmap indices on high-cardinality attributes

IF0

PREAI

Rotem,Doron; Stockinger,Kurt; Wu,Kesheng

The Sloan Digital Sky Survey: Technical summary 斯隆数字天空调查: 技术摘要

ASTRONOMICAL JOURNAL

IF5.1

2000-09-01

9.3K

OAAI

York, DG; Adelman, J; Anderson, JE; Anderson, SF; Annis, J; Bahcall, NA; Bakken, JA; Barkhouser, R; Bastian, S; Berman, E; Boroski, WN; Bracker, S; Briegel, C; Briggs, JW; Brinkmann, J; Brunner, R; Burles, S; Carey, L; Carr, MA; Castander, FJ; Chen, B; Colestock, PL; Connolly, AJ; Crocker, JH; Csabai, I; Czarapata, PC; Davis, JE; Doi, M; Dombeck, T; Eisenstein, D; Ellman, N; Elms, BR; Evans, ML; Fan, XH; Federwitz, GR; Fiscelli, L; Friedman, S; Frieman, JA; Fukugita, M; Gillespie, B; Gunn, JE; Gurbani, VK; de Haas, E; Haldeman, M; Harris, FH; Hayes, J; Heckman, TM; Hennessy, GS; Hindsley, RB; Holm, S; Holmgren, DJ; Huang, CH; Hull, C; Husby, D; Ichikawa, S; Ichikawa, T; Ivezic, Z; Kent, S; Kim, RSJ; Kinney, E; Klaene, M; Kleinman, AN; Kleinman, S; Knapp, GR; Korienek, J; Kron, RG; Kunszt, PZ; Lamb, DQ; Lee, B; Leger, RF; Limmongkol, S; Lindenmeyer, C; Long, DC; Loomis, C; Loveday, J; Lucinio, R; Lupton, RH; MacKinnon, B; Mannery, EJ; Mantsch, PM; Margon, B; McGehee, P; McKay, TA; Meiksin, A; Merelli, A; Monet, DG; Munn, JA; Narayanan, VK; Nash, T; Neilsen, E; Neswold, R; Newberg, HJ; Nichol, RC; Nicinski, T; Nonino, M; Okada, N; Okamura, S; Ostriker, JP; Owen, R; Pauls, AG; Peoples, J; Peterson, RL; Petravick, D; Pier, JR; Pope, A; Pordes, R; Prosapio, A; Rechenmacher, R; Quinn, TR; Richards, GT; Richmond, MW; Rivetta, CH; Rockosi, CM; Ruthmansdorfer, K; Sandford, D; Schlegel, DJ; Schneider, DP; Sekiguchi, M; Sergey, G; Shimasaku, K; Siegmund, WA; Smee, S; Smith, JA; Snedden, S; Stone, R; Stoughton, C; Strauss, MA; Stubbs, C; SubbaRao, M; Szalay, AS; Szapudi, I; Szokoly, GP; Thakar, AR; Tremonti, C; Tucker, DL; Uomoto, A; Berk, DV; Vogeley, MS; Waddell, P; Wang, SI; Watanabe, M; Weinberg, DH; Yanny, B; Yasuda, N

查看更多内容