{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:54:21Z","timestamp":1777676061977,"version":"3.51.4"},"reference-count":77,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T00:00:00Z","timestamp":1700438400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:p>The need for speeding up data analytics increases inevitably due to the need for extracting valuable information from social media, data generated by smart devices with sensors, patterns of people\u2019s communications over the web, items viewed and bought by global-scale customers, cloud applications, etc., all of which take part in the \u201cBig Data.\u201d Such kind of interaction data is very well represented as sparse graphs to enable the graph analytics, which requires efficient underlying kernels. The breadth-first search (BFS)-based traversal is a commonly used kernel in graph algorithms such as the betweenness centrality algorithm for centrality analysis. In this work, we focus on parallel BFS operations and propose hypergraph-based combinatorial models that aim at reducing cache misses and hence exploiting data locality during the parallel BFS operations. Our models are based on finding new vertex visit orders so that locality in accessing the data associated with vertices is exploited. Experiments on graphs arising in a wide range of applications show that our proposed models achieve on average 9% performance improvement in the CPU-based Ligra data analytics framework.<\/jats:p>","DOI":"10.1177\/10943420231214532","type":"journal-article","created":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T15:59:40Z","timestamp":1700495980000},"page":"210-224","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Hypergraph-based locality-enhancing methods for graph operations in Big Data applications"],"prefix":"10.1177","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1057-1590","authenticated-orcid":false,"given":"Kadir","family":"Akbudak","sequence":"first","affiliation":[{"name":"College of Engineering, The University of Tennessee, Knoxville, TN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2023,11,20]]},"reference":[{"key":"bibr1-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2656893"},{"key":"bibr2-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1007\/s11301-018-00152-3"},{"key":"bibr3-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.86"},{"key":"bibr4-10943420231214532","unstructured":"Apache Giraph (2012) Available at: http:\/\/giraph.apache.org\/(Accessed 16 June 2020)."},{"key":"bibr5-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.110"},{"key":"bibr6-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2006.57"},{"key":"bibr7-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2018.8573478"},{"key":"bibr8-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC50251.2020.00031"},{"key":"bibr9-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.50"},{"key":"bibr10-10943420231214532","volume-title":"The GAP Benchmark Suite","author":"Beamer S","year":"2015"},{"key":"bibr11-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2015.12"},{"key":"bibr12-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.112"},{"key":"bibr13-10943420231214532","volume-title":"Hypergraphs: Combinatorics of Finite Sets, Volume 45","author":"Berge C","year":"1984"},{"key":"bibr14-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/3078597.3078616"},{"key":"bibr15-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2004.11.008"},{"key":"bibr16-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/1941487.1941507"},{"key":"bibr17-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"bibr18-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011403516"},{"key":"bibr19-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/588\/11709"},{"key":"bibr20-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"bibr21-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-4054-2_12"},{"key":"bibr22-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"bibr23-10943420231214532","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350247"},{"key":"bibr24-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592101"},{"key":"bibr25-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/800195.805928"},{"key":"bibr26-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"bibr27-10943420231214532","unstructured":"DBG (2019) Available at: http:\/\/github.com\/faldupriyank\/dbg (Accessed 16 June 2020)."},{"key":"bibr28-10943420231214532","volume":"149","author":"Ding Z","year":"2018","journal-title":"PACIS"},{"key":"bibr29-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2010.66"},{"key":"bibr30-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC47752.2019.9041948"},{"key":"bibr31-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00028"},{"key":"bibr32-10943420231214532","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"bibr33-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2621934.2621936"},{"key":"bibr34-10943420231214532","first-page":"17","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI\u201912","author":"Gonzalez JE","year":"2012"},{"key":"bibr35-10943420231214532","unstructured":"Gorder (2016) Available at: http:\/\/github.com\/datourat\/Gorder (Accessed 16 June 2020)."},{"key":"bibr36-10943420231214532","first-page":"1","volume":"2","author":"Gregor D","year":"2005","journal-title":"Parallel Object-Oriented Scientific Computing (POOSC)"},{"key":"bibr37-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.14"},{"key":"bibr38-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0305-0"},{"key":"bibr39-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"bibr40-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2600212.2600227"},{"key":"bibr41-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250759"},{"key":"bibr42-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2009.4919639"},{"key":"bibr43-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1007\/s41109-020-00300-3"},{"key":"bibr44-10943420231214532","first-page":"31","volume-title":"Presented as Part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12)","author":"Kyrola A","year":"2012"},{"key":"bibr45-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2017.00039"},{"key":"bibr46-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/3380942"},{"key":"bibr47-10943420231214532","first-page":"459","volume-title":"2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Lee E","year":"2019"},{"key":"bibr48-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/PADSW.2018.8644918"},{"key":"bibr49-10943420231214532","unstructured":"Ligra (2014) Available at: http:\/\/github.com\/jshun\/ligra\/(Accessed 16 June 2020)."},{"key":"bibr50-10943420231214532","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"bibr51-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.80"},{"key":"bibr52-10943420231214532","doi-asserted-by":"publisher","DOI":"10.2172\/951102"},{"key":"bibr53-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"bibr54-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2013.6670338"},{"key":"bibr55-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/3307681.3325399"},{"key":"bibr56-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1111\/j.1745-9125.2008.00103.x"},{"key":"bibr57-10943420231214532","first-page":"45","volume":"19","author":"Murphy RC","year":"2010","journal-title":"Cray Users Group (CUG)"},{"key":"bibr58-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1007\/s11135-013-9831-7"},{"key":"bibr59-10943420231214532","unstructured":"Neo4j (2007) Available at: http:\/\/neo4j.com\/(Accessed 16 June 2020)."},{"key":"bibr60-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"bibr61-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"bibr62-10943420231214532","first-page":"41","volume-title":"Presented as Part of the 2012 USENIX Annual Technical Conference (USENIX ATC 12)","author":"Prabhakaran V","year":"2012"},{"key":"bibr63-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1080\/15472450.2012.716663"},{"key":"bibr64-10943420231214532","unstructured":"Rabbit (2016) Available at: https:\/\/github.com\/araij\/rabbit_order (Accessed 07 January 2023)."},{"key":"bibr65-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"bibr66-10943420231214532","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809983"},{"key":"bibr67-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2703149"},{"key":"bibr68-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9128(199704)9:4<255::AID-CPE250>3.0.CO;2-2"},{"key":"bibr69-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"bibr70-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/3108140"},{"key":"bibr71-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00576-7"},{"key":"bibr72-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915220"},{"key":"bibr73-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2365952.2366010"},{"key":"bibr74-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484427"},{"key":"bibr75-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8257937"},{"key":"bibr76-10943420231214532","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"},{"key":"bibr77-10943420231214532","first-page":"1601","volume":"19","author":"Zhou D","year":"2006","journal-title":"Advances in Neural Information Processing Systems"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/10943420231214532","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/10943420231214532","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/10943420231214532","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:17:33Z","timestamp":1777450653000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/10943420231214532"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,20]]},"references-count":77,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["10.1177\/10943420231214532"],"URL":"https:\/\/doi.org\/10.1177\/10943420231214532","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,20]]}}}