DenseZDD: a compact and fast index for families of sets
Summary: In this article, we propose a succinct data structure of zero-suppressed binary decision diagrams (ZDDs). A ZDD represents sets of combinations efficiently and we can perform various set operations on the ZDD without explicitly extracting combinations. Thanks to these features, ZDDs have been applied to web information retrieval, information integration, and data mining. However, to support rich manipulation of sets of combinations and update ZDDs in the future, ZDDs need too much space, which means that there is still room to be compressed. The paper introduces a new succinct data structure, called DenseZDD, for further compressing a ZDD when we do not need to conduct set operations on the ZDD but want to examine whether a given set is included in the family represented by the ZDD, and count the number of elements in the family. We also propose a hybrid method, which combines DenseZDDs with ordinary ZDDs. By numerical experiments, we show that the sizes of our data structures are three times smaller than those of ordinary ZDDs, and membership operations and random sampling on DenseZDDs are about ten times and three times faster than those on ordinary ZDDs for some datasets, respectively.
- Chain reduction for binary and zero-suppressed decision diagrams
- DenseZDD: a compact and fast index for families of sets
- ESP-index: a compressed index based on edit-sensitive parsing
- Fully functional static and dynamic succinct trees
- Graph-Based Algorithms for Boolean Function Manipulation
- Practical entropy-compressed rank/select dictionary
- Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
- Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
- The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Genera
- Universal codeword sets and representations of the integers
- Z-Skip-Links for Fast Traversal of ZDDs Representing Large-Scale Sparse Datasets
- Zero-suppressed BDDs and their applications
- Extracting co-occurrence relations from ZDDs
- Sequence sentential decision diagrams
- DenseZDD: a compact and fast index for families of sets
- Z-Skip-Links for Fast Traversal of ZDDs Representing Large-Scale Sparse Datasets
- Zero-suppressed binary decision diagrams resilient to index faults
- A contribution to the use of decision diagrams for loading and mining transaction databases
- Characteristics of the maximal independent set ZDD
- DenseZDD
- Estimation of the Density of Datasets with Decision Diagrams
- Boosting over non-deterministic ZDDs
- Boosting over non-deterministic ZDDs
- Storing set families more compactly with top ZDDs
- Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs
- \textsc{Concise}: compressed `\(n\)' composable integer set
This page was built for publication: DenseZDD: a compact and fast index for families of sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2331660)
