{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:40Z","timestamp":1750306360744,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2016,4,5]],"date-time":"2016-04-05T00:00:00Z","timestamp":1459814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2016,11,4]]},"abstract":"<jats:p>\n            The minimal sets within a collection of sets are defined as the ones that do not have a proper subset within the collection, and the maximal sets are the ones that 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 article, we present two novel improvements of the high-quality extremal set identification algorithm,\n            <jats:italic>AMS-Lex<\/jats:italic>\n            , described by Bayardo and Panda. The first technique uses memoization to improve the execution time of the single-threaded variant of the AMS-Lex, while 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\n            <jats:italic>itemsets<\/jats:italic>\n            increases. We provide experimental results using both real-world and synthetic datasets, and show our multithreaded variant algorithm outperforming 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 multithreaded program executes about as fast as the state-of-the-art parallel GPU-based program using an NVIDIA GTX 580 graphics processing unit.\n          <\/jats:p>","DOI":"10.1145\/2893184","type":"journal-article","created":{"date-parts":[[2016,4,5]],"date-time":"2016-04-05T15:18:51Z","timestamp":1459869531000},"page":"1-21","source":"Crossref","is-referenced-by-count":5,"title":["Practical Algorithms for Finding Extremal Sets"],"prefix":"10.1145","volume":"21","author":[{"given":"Martin","family":"Marinov","sequence":"first","affiliation":[{"name":"Trinity College Dublin, Dublin, Ireland"}]},{"given":"Nicholas","family":"Nash","sequence":"additional","affiliation":[{"name":"Susquehanna International Group, Dublin, Ireland"}]},{"given":"David","family":"Gregg","sequence":"additional","affiliation":[{"name":"Lero, Trinity College Dublin, Dublin, Ireland"}]}],"member":"320","published-online":{"date-parts":[[2016,4,5]]},"reference":[{"volume-title":"Bayardo and Biswanath Panda","year":"2011","author":"Roberto","key":"e_1_2_1_1_1"},{"volume-title":"Optimal-depth sorting networks. CoRR abs\/1412.5302","year":"2014","author":"Bundala Daniel","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11499107_5"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.07.004"},{"key":"e_1_2_1_5_1","unstructured":"M. Marinov and D. Gregg. 2015. On the GI-completeness of a sorting networks isomorphism. ArXiv e-prints (July 2015).  M. Marinov and D. Gregg. 2015. On the GI-completeness of a sorting networks isomorphism. ArXiv e-prints (July 2015)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11893318_18"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261654"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00084-7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207169608804512"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653812"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/139404.139481"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90264-A"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2893184","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2893184","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:13Z","timestamp":1750222573000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2893184"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,5]]},"references-count":12,"alternative-id":["10.1145\/2893184"],"URL":"https:\/\/doi.org\/10.1145\/2893184","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2016,4,5]]}}}