Extracting co-occurrence relations from ZDDs

DOI10.3390/A5040654MaRDI QIDQ1736536zbMATH OpenOpenAlexFDO

Authors Takahisa Toda

Publication date 26 March 2019

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/a5040654

zbMATH Keywords

BDDco-occurrencedata miningpartitionZDD

Mathematics Subject Classification ID

Data structures (68P05) Learning and adaptive systems in artificial intelligence (68T05) Nonnumerical algorithms (68W05)

Review text

Summary: A zero-suppressed binary decision diagram (ZDD) is a graph representation suitable for handling sparse set families. Given a ZDD representing a set family, we present an efficient algorithm to discover a hidden structure, called a co-occurrence relation, on the ground set. This computation can be done in time complexity that is related not to the number of sets, but to some feature values of the ZDD. We furthermore introduce a conditional co-occurrence relation and present an extraction algorithm, which enables us to discover further structural information.

Recommendations

• Storing set families more compactly with top ZDDs
• DenseZDD: a compact and fast index for families of sets
• Zero-suppression and computation models
• Characteristics of the maximal independent set ZDD
• Zero-suppressed BDDs and their applications

Cites work

• Binary Decision Diagrams
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 437527 (Why is no real title available?)
• Partially-shared zero-suppressed multi-terminal BDDs: Concept, algorithms and applications
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.

Cited in

(4)

• Editorial: Special issue on graph algorithms
• DenseZDD: a compact and fast index for families of sets
• Z-Skip-Links for Fast Traversal of ZDDs Representing Large-Scale Sparse Datasets
• Characteristics of the maximal independent set ZDD

Describes a project that uses

Uses Software

• GraphBase
• CUDD

This page was built for publication: Extracting co-occurrence relations from ZDDs

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