We present a data structure that encodes a sorted integer sequence in small space allowing, at the same time, fast intersection operations. The data layout is carefully designed to exploit word-level parallelism and SIMD instructions, hence providing good practical performance. The core algorithmic idea is that of recursive partitioning the universe of representation: a markedly different paradigm than the widespread strategy of partitioning the sequence based on its length. Extensive experimentation and comparison against several competitive techniques shows that the proposed solution embodies an improved space/time trade-off for the set intersection problem.
Fast and compact set intersection through recursive universe partitioning
Pibiri GE
2021
Abstract
We present a data structure that encodes a sorted integer sequence in small space allowing, at the same time, fast intersection operations. The data layout is carefully designed to exploit word-level parallelism and SIMD instructions, hence providing good practical performance. The core algorithmic idea is that of recursive partitioning the universe of representation: a markedly different paradigm than the widespread strategy of partitioning the sequence based on its length. Extensive experimentation and comparison against several competitive techniques shows that the proposed solution embodies an improved space/time trade-off for the set intersection problem.File | Dimensione | Formato | |
---|---|---|---|
prod_446384-doc_160719.pdf
accesso aperto
Descrizione: preprint - Fast and Compact Set Intersection through Recursive Universe Partitioning
Tipologia:
Versione Editoriale (PDF)
Dimensione
389.14 kB
Formato
Adobe PDF
|
389.14 kB | Adobe PDF | Visualizza/Apri |
prod_446384-doc_192405.pdf
non disponibili
Descrizione: Fast and Compact Set Intersection through Recursive Universe Partitioning
Tipologia:
Versione Editoriale (PDF)
Dimensione
196.41 kB
Formato
Adobe PDF
|
196.41 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.