{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T14:29:27Z","timestamp":1774880967236,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T00:00:00Z","timestamp":1548806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1318595 and CCF-1526513"],"award-info":[{"award-number":["CCF-1318595 and CCF-1526513"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            In topological data analysis, a point cloud data\n            <jats:italic>P<\/jats:italic>\n            extracted from a metric space is often analyzed by computing the persistence diagram or barcodes of a sequence of Rips complexes built on\n            <jats:italic>P<\/jats:italic>\n            indexed by a scale parameter. Unfortunately, even for input of moderate size, the size of the Rips complex may become prohibitively large as the scale parameter increases. Starting with the\n            <jats:italic>Sparse Rips filtration<\/jats:italic>\n            introduced by Sheehy, some existing methods aim to reduce the size of the complex to improve time efficiency as well. However, as we demonstrate, existing approaches still fall short of scaling well, especially for high-dimensional data. In this article, we investigate the advantages and limitations of existing approaches. Based on insights gained from the experiments, we propose an efficient new algorithm, called\n            <jats:italic>SimBa<\/jats:italic>\n            , for approximating the persistent homology of Rips filtrations with quality guarantees. Our new algorithm leverages a batch-collapse strategy as well as a new Sparse Rips-like filtration. We experiment on a variety of low- and high-dimensional datasets. We show that our strategy presents a significant size reduction and that our algorithm for approximating Rips filtration persistence is an order of magnitude faster than existing methods in practice.\n          <\/jats:p>","DOI":"10.1145\/3284360","type":"journal-article","created":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T12:58:34Z","timestamp":1548853114000},"page":"1-16","source":"Crossref","is-referenced-by-count":19,"title":["SimBa"],"prefix":"10.1145","volume":"24","author":[{"given":"Tamal K.","family":"Dey","sequence":"first","affiliation":[{"name":"The Ohio State University, Ohio, USA"}]},{"given":"Dayu","family":"Shi","sequence":"additional","affiliation":[{"name":"The Ohio State University, Ohio, USA"}]},{"given":"Yusu","family":"Wang","sequence":"additional","affiliation":[{"name":"The Ohio State University, Ohio, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,1,30]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","author":"Software Simpers","year":"2018","unstructured":"2015. Simpers Software . Retrieved December 24, 2018 from http:\/\/web.cse.ohio-state.edu\/ tamaldey\/SimPers\/Simpers.html. 2015. Simpers Software. Retrieved December 24, 2018 from http:\/\/web.cse.ohio-state.edu\/ tamaldey\/SimPers\/Simpers.html."},{"key":"e_1_2_1_2_1","volume-title":"Retrieved","author":"Software SimBa","year":"2018","unstructured":"2016. SimBa Software . Retrieved December 24, 2018 from http:\/\/web.cse.ohio-state.edu\/ dey.8\/SimBa\/Simba.html. 2016. SimBa Software. Retrieved December 24, 2018 from http:\/\/web.cse.ohio-state.edu\/ dey.8\/SimBa\/Simba.html."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/070711669"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"U. Bauer M. Kerber and J. Reininghaus. 2014. Topological Methods in Data Analysis and Visualization III: Theory Algorithms and Applications. Springer International Publishing 103--117.   U. Bauer M. Kerber and J. Reininghaus. 2014. Topological Methods in Data Analysis and Visualization III: Theory Algorithms and Applications. Springer International Publishing 103--117.","DOI":"10.1007\/978-3-319-04099-8_7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2016.03.008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9999-4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9887-3"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. 168--180","author":"Buchet M.","unstructured":"M. Buchet , F. Chazal , S. Y. Oudot , and D. R. Sheehy . 2015. Efficient and robust persistent homology for measures . In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. 168--180 . M. Buchet, F. Chazal, S. Y. Oudot, and D. R. Sheehy. 2015. Efficient and robust persistent homology for measures. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. 168--180."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9497-x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-09-01249-X"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115437.3115553"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"G. Carlsson and A. Zomorodian. 2009. The theory of multidimensional persistence. Discrete 8 Computational Geometry 42 1 (2009) 71--93.  G. Carlsson and A. Zomorodian. 2009. The theory of multidimensional persistence. Discrete 8 Computational Geometry 42 1 (2009) 71--93.","DOI":"10.1007\/s00454-009-9176-0"},{"key":"e_1_2_1_14_1","volume-title":"Canadian Conference on Computational Geometru (CCCG\u201915)","author":"Cavanna N. J.","unstructured":"N. J. Cavanna , M. Jahanseir , and D. R. Sheehy . 2015. A geometric perspective on sparse filtrations . In Canadian Conference on Computational Geometru (CCCG\u201915) . http:\/\/dblp.uni-trier.de\/db\/conf\/cccg\/cccg2015.html#CavannaJS15 N. J. Cavanna, M. Jahanseir, and D. R. Sheehy. 2015. A geometric perspective on sparse filtrations. In Canadian Conference on Computational Geometru (CCCG\u201915). http:\/\/dblp.uni-trier.de\/db\/conf\/cccg\/cccg2015.html#CavannaJS15"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542407"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of SGP.","author":"Chazal F.","unstructured":"F. Chazal , D. Cohen-Steiner , L. Guibas , F. M\u00e9moli , and S. Y. Oudot . 2009. Gromov-Hausdorff stable signatures for shapes using persistence . In Proceedings of SGP. F. Chazal, D. Cohen-Steiner, L. Guibas, F. M\u00e9moli, and S. Y. Oudot. 2009. Gromov-Hausdorff stable signatures for shapes using persistence. In Proceedings of SGP."},{"key":"e_1_2_1_17_1","unstructured":"F. Chazal V. de Silva M. Glisse and S. Oudot. 2012. The structure and stability of persistence modules. CoRR abs\/1207.3674 (2012).  F. Chazal V. de Silva M. Glisse and S. Oudot. 2012. The structure and stability of persistence modules. CoRR abs\/1207.3674 (2012)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998212"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 27th European Workshop on Computational Geometry.","author":"Chen C.","unstructured":"C. Chen and M. Kerber . 2011. Persistent homology computation with a twist . In Proceedings of the 27th European Workshop on Computational Geometry. C. Chen and M. Kerber. 2011. Persistent homology computation with a twist. In Proceedings of the 27th European Workshop on Computational Geometry."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"D. Cohen-Steiner H. Edelsbrunner and J. Harer. 2007. Stability of persistence diagrams. Discrete 8 Computational Geometry 37 1 (2007) 103--120.  D. Cohen-Steiner H. Edelsbrunner and J. Harer. 2007. Stability of persistence diagrams. Discrete 8 Computational Geometry 37 1 (2007) 103--120.","DOI":"10.1007\/s00454-006-1276-5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1501917.1501921"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137877"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9344-x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582165"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2010.01763.x"},{"key":"e_1_2_1_26_1","volume-title":"Retrieved","author":"Morozov Dmitriy","year":"2012","unstructured":"Dmitriy Morozov . 2012 . Dionysus Software . Retrieved December 24, 2018 from http:\/\/mrzv.org\/software\/dionysus\/. Dmitriy Morozov. 2012. Dionysus Software. Retrieved December 24, 2018 from http:\/\/mrzv.org\/software\/dionysus\/."},{"key":"e_1_2_1_27_1","unstructured":"H. Edelsbrunner and J. Harer. 2010. Computational Topology - An Introduction. American Mathematical Society. I--XII 1--241 pages.  H. Edelsbrunner and J. Harer. 2010. Computational Topology - An Introduction. American Mathematical Society. I--XII 1--241 pages."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2885-2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0004972700028574"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmgm.2014.06.003"},{"key":"e_1_2_1_31_1","volume-title":"SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved","author":"Leskovec J.","year":"2018","unstructured":"J. Leskovec and A. Krevl . 2014 . SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved December 24, 2018 from http:\/\/snap.stanford.edu\/data. J. Leskovec and A. Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved December 24, 2018 from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_32_1","volume-title":"Retrieved","author":"Lichman M.","year":"2013","unstructured":"M. Lichman . 2013 . UCI Machine Learning Repository . Retrieved December 24, 2018 from http:\/\/archive.ics.uci.edu\/ml. M. Lichman. 2013. UCI Machine Learning Repository. Retrieved December 24, 2018 from http:\/\/archive.ics.uci.edu\/ml."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2016.02.021"},{"key":"e_1_2_1_34_1","volume-title":"Gesture Phase Segmentation Data Set. Retrieved","author":"Madeo R. C. B.","year":"2018","unstructured":"R. C. B. Madeo , P. K. Wagner , and S. M. Peres . 2014 . Gesture Phase Segmentation Data Set. Retrieved December 24, 2018 from http:\/\/archive.ics.uci.edu\/ml\/datasets\/Gesture+Phase+Segmentation. R. C. B. Madeo, P. K. Wagner, and S. M. Peres. 2014. Gesture Phase Segmentation Data Set. Retrieved December 24, 2018 from http:\/\/archive.ics.uci.edu\/ml\/datasets\/Gesture+Phase+Segmentation."},{"key":"e_1_2_1_35_1","volume-title":"ANN: A Library for Approximate Nearest Neighbor Searching. Retrieved","author":"Mount D. M.","year":"2018","unstructured":"D. M. Mount and S. Arya . 2010 . ANN: A Library for Approximate Nearest Neighbor Searching. Retrieved December 24, 2018 from https:\/\/www.cs.umd.edu\/&sim;mount\/ANN\/. D. M. Mount and S. Arya. 2010. ANN: A Library for Approximate Nearest Neighbor Searching. Retrieved December 24, 2018 from https:\/\/www.cs.umd.edu\/&sim;mount\/ANN\/."},{"key":"e_1_2_1_36_1","volume-title":"Elements of Algebraic Topology","author":"Munkres James R.","unstructured":"James R. Munkres . 1993. Elements of Algebraic Topology . Addison-Wesley . James R. Munkres. 1993. Elements of Algebraic Topology. Addison-Wesley."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201915)","author":"Reininghaus J.","unstructured":"J. Reininghaus , S. Huber , U. Bauer , and R. Kwitt . 2015. A stable multi-scale kernel for topological machine learning . In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201915) . IEEE, 4741--4748. J. Reininghaus, S. Huber, U. Bauer, and R. Kwitt. 2015. A stable multi-scale kernel for topological machine learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201915). IEEE, 4741--4748."},{"key":"e_1_2_1_38_1","first-page":"503","article-title":"Towards computing homology from finite approximations","volume":"24","author":"Robins V.","year":"1999","unstructured":"V. Robins . 1999 . Towards computing homology from finite approximations . Topology Proceedings 24 , 1 (1999), 503 -- 532 . V. Robins. 1999. Towards computing homology from finite approximations. Topology Proceedings 24, 1 (1999), 503--532.","journal-title":"Topology Proceedings"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261286"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1167\/8.8.11"},{"key":"e_1_2_1_41_1","volume-title":"GUDHI Editorial Board. Retrieved","author":"Project The GUDHI","year":"2015","unstructured":"The GUDHI Project . 2015 . GUDHI User and Reference Manual . GUDHI Editorial Board. Retrieved December 24, 2018 from http:\/\/gudhi.gforge.inria.fr\/doc\/latest\/. The GUDHI Project. 2015. GUDHI User and Reference Manual. GUDHI Editorial Board. Retrieved December 24, 2018 from http:\/\/gudhi.gforge.inria.fr\/doc\/latest\/."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1146-y"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284360","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3284360","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3284360","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:49Z","timestamp":1750207429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284360"}},"subtitle":["An Efficient Tool for Approximating Rips-filtration Persistence via\n            <u>Sim<\/u>\n            plicial\n            <u>Ba<\/u>\n            tch Collapse"],"short-title":[],"issued":{"date-parts":[[2019,1,30]]},"references-count":42,"alternative-id":["10.1145\/3284360"],"URL":"https:\/\/doi.org\/10.1145\/3284360","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,30]]}}}