\texttt{FASTSET}: a fast data structure for the representation of sets of integers

DOI10.3390/A12050091MaRDI QIDQ2004853zbMATH OpenOpenAlexWikidataFDO

Authors Giuseppe Lancia, Marcello Dalpasso

Publication date 7 October 2020

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a12050091

zbMATH Keywords

bitmaskdata structuresset representation

Mathematics Subject Classification ID

Data structures (68P05)

Review text

Summary: We describe a simple data structure for storing subsets of \(\{0, \dots, N-1\}\), with \(N\) a given integer, which has optimal time performance for all the main set operations, whereas previous data structures are non-optimal for at least one such operation. We report on the comparison of a Java implementation of our structure with other structures of the standard Java Collections.

Recommendations

• Representing sets with constant time equality testing
• Deterministic \(k\)-set structure
• scientific article; zbMATH DE number 1982202
• Fast Evaluation of Union-Intersection Expressions
• A compact data structure for representing a dynamic multiset

Cites work

• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 1044821 (Why is no real title available?)
• Introduction to algorithms.

Cited in

(4)

• More on balanced diets
• scientific article; zbMATH DE number 2166728 (Why is no real title available?)
• Fast dynamic arrays
• Deterministic \(k\)-set structure

This page was built for publication: \texttt{FASTSET}: a fast data structure for the representation of sets of integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2004853)