Practical algorithms for finding extremal sets

DOI10.1145/2893184MaRDI QIDQ5266618zbMATH OpenOpenAlexFDO

Authors Martin Cvetanov Marinov, Nicholas Nash, David Gregg

Publication date 16 June 2017

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.01753

zbMATH Keywords

parallel algorithmextremal setsmemoizationpractical algorithmitemset

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05) Parallel algorithms in computer science (68W10)

Abstract: The minimal sets within a collection of sets are defined as the ones which do not have a proper subset within the collection, and the maximal sets are the ones which do not have a proper superset within the collection. Identifying extremal sets is a fundamental problem with a wide-range of applications in SAT solvers, data-mining and social network analysis. In this paper, we present two novel improvements of the high-quality extremal set identification algorithm, extit{AMS-Lex}, described by Bayardo and Panda. The first technique uses memoization to improve the execution time of the single-threaded variant of the AMS-Lex, whilst our second improvement uses parallel programming methods. In a subset of the presented experiments our memoized algorithm executes more than $400$ times faster than the highly efficient publicly available implementation of AMS-Lex. Moreover, we show that our modified algorithm's speedup is not bounded above by a constant and that it increases as the length of the common prefixes in successive input extit{itemsets} increases. We provide experimental results using both real-world and synthetic data sets, and show our multi-threaded variant algorithm out-performing AMS-Lex by $3$ to $6$ times. We find that on synthetic input datasets when executed using $16$ CPU cores of a $32$-core machine, our multi-threaded program executes about as fast as the state of the art parallel GPU-based program using an NVIDIA GTX 580 graphics processing unit.

Recommendations

• Fast sequential and parallel algorithms for finding extremal sets
• Extremal problems on finite sets with a monotone measure
• Finding extremal sets in less than quadratic time
• A fast bit-parallel algorithm for computing the subset partial order
• An old sub-quadratic algorithm for finding extremal sets

Cites work

• scientific article; zbMATH DE number 742985 (Why is no real title available?)
• An old sub-quadratic algorithm for finding extremal sets
• Fast sequential and parallel algorithms for finding extremal sets
• Finding extremal sets in less than quadratic time
• Opportunistic algorithms for eliminating supersets
• Optimal-depth sorting networks
• Theory and Applications of Satisfiability Testing

Cited in

(2)

• An old sub-quadratic algorithm for finding extremal sets
• Fast sequential and parallel algorithms for finding extremal sets

Describes a project that uses

Uses Software

• MiniSat

This page was built for publication: Practical algorithms for finding extremal sets

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