Document - Fast and compact set intersection through recursive universe partitioning

2021

Conference article Open Access

Fast and compact set intersection through recursive universe partitioning

Pibiri G. E.

Inverted Indexes Efficiency SIMD Compressed Set Intersection

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.

Source: DCC 2021 - IEEE Data Compression Conference, pp. 293–302, Online Conference, 23-26/03/2021

Metrics

Back to previous page

Cite as

BibTeX entry

@inproceedings{oai:it.cnr:prodotti:446384,
	title = {Fast and compact set intersection through recursive universe partitioning},
	author = {Pibiri G. E.},
	doi = {10.1109/dcc50243.2021.00037},
	booktitle = {DCC 2021 - IEEE Data Compression Conference, pp. 293–302, Online Conference, 23-26/03/2021},
	year = {2021}
}