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.
2021
Istituto di Scienza e Tecnologie dell'Informazione "Alessandro Faedo" - ISTI
978-1-6654-0333-7
Compressed Set Intersection
SIMD
Inverted Indexes
Efficiency
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/427038
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact