Practical algorithms for finding extremal sets

DOI10.1145/2893184zbMATH Open1365.68460arXiv1508.01753OpenAlexW2120457683MaRDI QIDQ5266618FDOQ5266618

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)

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.

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

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

zbMATH Keywords

parallel algorithmextremal setsmemoizationpractical algorithmitemset

Mathematics Subject Classification ID

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

Cites Work

• Theory and Applications of Satisfiability Testing
• Finding extremal sets in less than quadratic time
• Fast sequential and parallel algorithms for finding extremal sets
• An old sub-quadratic algorithm for finding extremal sets
• Opportunistic algorithms for eliminating supersets
• Optimal-depth sorting networks
• Title not available (Why is that?)

Cited In (2)

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

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)