{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T04:29:57Z","timestamp":1768105797282,"version":"3.49.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,12,30]],"date-time":"2014-12-30T00:00:00Z","timestamp":1419897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Research Foundation of Korea (NRF) grant funded by the Korean Government (MSIP) no. NRF-2014R1A1A2002499"},{"name":"GRF","award":["4164\/12 and 4168\/13"],"award-info":[{"award-number":["4164\/12 and 4168\/13"]}]},{"name":"Defense Acquisition Program Administration and Agency for Defense Development under the contract UD140022PD, Korea"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,12,30]]},"abstract":"<jats:p>\n            This article studies I\/O-efficient algorithms for the\n            <jats:italic>triangle listing problem<\/jats:italic>\n            and the\n            <jats:italic>triangle counting problem<\/jats:italic>\n            , whose solutions are basic operators in dealing with many other graph problems. In the former problem, given an undirected graph\n            <jats:italic>G<\/jats:italic>\n            , the objective is to find all the cliques involving 3 vertices in\n            <jats:italic>G<\/jats:italic>\n            . In the latter problem, the objective is to report just the number of such cliques without having to enumerate them. Both problems have been well studied in internal memory, but still remain as difficult challenges when\n            <jats:italic>G<\/jats:italic>\n            does not fit in memory, thus making it crucial to minimize the number of disk I\/Os performed. Although previous research has attempted to tackle these challenges, the state-of-the-art solutions rely on a set of crippling assumptions to guarantee good performance. Motivated by this, we develop a new algorithm that is provably I\/O and CPU efficient at the same time, without making any assumption on the input\n            <jats:italic>G<\/jats:italic>\n            at all. The algorithm uses ideas drastically different from all the previous approaches, and outperforms the existing competitors by a factor of over an order of magnitude in our extensive experimentation.\n          <\/jats:p>","DOI":"10.1145\/2691190.2691193","type":"journal-article","created":{"date-parts":[[2015,1,5]],"date-time":"2015-01-05T13:27:09Z","timestamp":1420464429000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["I\/O-Efficient Algorithms on Triangle Listing and Counting"],"prefix":"10.1145","volume":"39","author":[{"given":"Xiaocheng","family":"Hu","sequence":"first","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chin-Wan","family":"Chung","sequence":"additional","affiliation":[{"name":"Korea Advanced Institute of Science and Technology, Daejeon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","volume-title":"Spencer","author":"Alon Noga","year":"2000","unstructured":"Noga Alon and Joel H . Spencer . 2000 . The Probabilistic Methods 2nd Ed. Wiley , New York. Noga Alon and Joel H. Spencer. 2000. The Probabilistic Methods 2nd Ed. Wiley, New York."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187907"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.09.051"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_21"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043652.2043654"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020513"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382577.2382581"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_16_1","unstructured":"Roman Dementiev. 2006. Algorithm engineering for large data sets hardware software algorithms. http:\/\/algo2.iti.kit.edu\/documents\/DementievDiss.pdf.   Roman Dementiev. 2006. Algorithm engineering for large data sets hardware software algorithms. http:\/\/algo2.iti.kit.edu\/documents\/DementievDiss.pdf."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03367-4_25"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.46"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_15"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213899"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487678"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625260"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.006"},{"key":"e_1_2_1_27_1","unstructured":"Bruno Menegola. 2010. An external memory algorithm for listing triangles. Tech. rep. Universidade Federal do Rio Grande do Sul.  Bruno Menegola. 2010. An external memory algorithm for listing triangles. Tech. rep. Universidade Federal do Rio Grande do Sul."},{"key":"e_1_2_1_28_1","first-page":"1","article-title":"Decomposition of finite graphs into forests","volume":"39","author":"Nash-Williams C. St. J. A.","year":"1964","unstructured":"C. St. J. A. Nash-Williams . 1964 . Decomposition of finite graphs into forests . J. London Math. Soc. 39 , 1 , 12. C. St. J. A. Nash-Williams. 1964. Decomposition of finite graphs into forests. J. London Math. Soc. 39, 1, 12.","journal-title":"J. London Math. Soc."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594552"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_54"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020599"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921073"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078335"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2691190.2691193","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2691190.2691193","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:07Z","timestamp":1750227127000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2691190.2691193"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,30]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12,30]]}},"alternative-id":["10.1145\/2691190.2691193"],"URL":"https:\/\/doi.org\/10.1145\/2691190.2691193","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,30]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}