{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T02:02:44Z","timestamp":1768096964014,"version":"3.49.0"},"reference-count":39,"publisher":"MDPI AG","issue":"24","license":[{"start":{"date-parts":[[2022,12,15]],"date-time":"2022-12-15T00:00:00Z","timestamp":1671062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Institute for Information &amp; communications Technology Promotion (IITP)","award":["IITP-2022-2021-0-00859"],"award-info":[{"award-number":["IITP-2022-2021-0-00859"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Graph data are pervasive worldwide, e.g., social networks, citation networks, and web graphs. A real-world graph can be huge and requires heavy computational and storage resources for processing. Various graph compression techniques have been presented to accelerate the processing time and utilize memory efficiently. SOTA approaches decompose a graph into fixed-size submatrices and compress it by applying the existing graph compression algorithm. This approach is promising if the input graph is dense. Otherwise, an optimal graph compression ratio cannot be achieved. Graphs such as those used by social networks exhibit a power-law distribution. Thus, applying compression to the fixed-size block of a matrix could lead to the empty cell processing of that matrix. In this paper, we solve the problem of ordered matrix compression on a deep level, dividing the block into sub-blocks to achieve the best compression ratio. We observe that the ordered matrix compression ratio could be improved by adopting variable-shape regions, considering both horizontal- and vertical-shaped regions. In our empirical evaluation, the proposed approach achieved a 93.8% compression ratio on average, compared with existing SOTA graph compression techniques.<\/jats:p>","DOI":"10.3390\/s22249894","type":"journal-article","created":{"date-parts":[[2022,12,16]],"date-time":"2022-12-16T03:55:39Z","timestamp":1671162939000},"page":"9894","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["iRun: Horizontal and Vertical Shape of a Region-Based Graph Compression"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1557-6304","authenticated-orcid":false,"given":"Muhammad","family":"Umair","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Kyung Hee University, Global Campus, Yongin-si 17104, Republic of Korea"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2314-5395","authenticated-orcid":false,"given":"Young-Koo","family":"Lee","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Kyung Hee University, Global Campus, Yongin-si 17104, Republic of Korea"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,15]]},"reference":[{"key":"ref_1","first-page":"1","article-title":"Graph Summarization Methods and Applications: A Survey","volume":"51","author":"Liu","year":"2018","journal-title":"ACM Comput. Surv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ins.2015.12.006","article-title":"itri: Index-based triangle listing in massive graphs","volume":"336","author":"Rasel","year":"2016","journal-title":"Inf. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Kabiljo, I., Karrer, B., Ottaviano, G., Pupyrev, S., and Shalita, A. (2016, January 13\u201317). Compressing graphs and indexes with recursive graph bisection. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA.","DOI":"10.1145\/2939672.2939862"},{"key":"ref_4","unstructured":"Alam, A., Umair, M., Dolgorsuren, B., Akhond, M.R., Ali, M.A., Qudus, U., and Lee, Y.K. (2018). Distributed In-Memory Granularity-Based Time-Series Graph Compression, Korean Society of Information Science and Technology. Korean Society of Information Science and Technology Academic Papers."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"38020","DOI":"10.1109\/ACCESS.2019.2899921","article-title":"StarZIP: Streaming graph compression technique for data archiving","volume":"7","author":"Dolgorsuren","year":"2019","journal-title":"IEEE Access"},{"key":"ref_6","unstructured":"Umair, M., Rasel, M.K., and Lee, Y.K. (2017). BLOCK Formulation Technique for Compressed Graph Computation, Korean Society of Information Science and Technology. Korean Society of Information Science and Technology Academic Papers."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Maserrat, H., and Pei, J. (2010, January 24\u201328). Neighbor query friendly compression of social networks. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/1835804.1835873"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Rasel, M.K., and Lee, Y.K. (2016, January 18\u201320). Exploiting CPU parallelism for triangle listing using hybrid summarized bit batch vector. Proceedings of the 2016 International Conference on Big Data and Smart Computing (BigComp), Hong Kong, China.","DOI":"10.1109\/BIGCOMP.2016.7425819"},{"key":"ref_9","unstructured":"Li, G., Rao, W., and Jin, Z. (2017, January 7\u20139). Efficient compression on real world directed graphs. Proceedings of the Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint Conference on Web and Big Data, Beijing, China."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Shun, J., Dhulipala, L., and Blelloch, G.E. (2015, January 7\u20139). Smaller and faster: Parallel processing of compressed graphs with Ligra+. Proceedings of the Data Compression Conference (DCC), Snowbird, UT, USA.","DOI":"10.1109\/DCC.2015.8"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Li, G., and Rao, W. (2016, January 12\u201316). Compression-aware graph computation. Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing: Adjunct, Heidelberg, Germany.","DOI":"10.1145\/2968219.2968297"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"3077","DOI":"10.1109\/TKDE.2014.2320716","article-title":"Slashburn: Graph compression and mining beyond caveman communities","volume":"26","author":"Lim","year":"2014","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_13","unstructured":"Besta, M., and Hoefler, T. (2018). Survey and taxonomy of lossless graph compression and space-efficient graph representations. arXiv."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3415148","article-title":"Techniques for inverted index compression","volume":"53","author":"Pibiri","year":"2020","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"ref_15","unstructured":"Boldi, P., and Vigna, S. (2014, January 7\u201311). The webgraph framework I: Compression techniques. Proceedings of the 13th International Conference on World Wide Web, Seoul, Republic of Korea."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1080\/15427951.2009.10390641","article-title":"Permuting web and social graphs","volume":"6","author":"Boldi","year":"2009","journal-title":"Internet Math."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Kang, U., and Faloutsos, C. (2011, January 11\u201314). Beyond\u2019caveman communities\u2019: Hubs and spokes for graph compression and mining. Proceedings of the 2011 IEEE 11th International Conference on Data Mining (ICDM), British, CO, Canada.","DOI":"10.1109\/ICDM.2011.26"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Kang, U., Tong, H., Sun, J., Lin, C.Y., and Faloutsos, C. (2011, January 21\u201324). Gbase: A scalable and general graph management system. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA.","DOI":"10.1145\/2020408.2020580"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1007\/s00778-012-0283-9","article-title":"Gbase: An efficient analysis platform for large graphs","volume":"21","author":"Kang","year":"2012","journal-title":"VLDB J.\u2014Int. J. Very Large Data Bases"},{"key":"ref_20","unstructured":"Blandford, D.K., Blelloch, G.E., and Kash, I.A. (2004, January 10). An Experimental Analysis of a Compact Graph Representation. Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, New Orleans, LA, USA."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/2517327.2442530","article-title":"Ligra: A lightweight graph processing framework for shared memory","volume":"48","author":"Shun","year":"2013","journal-title":"Proc. Acm Sigplan Not."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Chan, C.Y., and Ioannidis, Y.E. (1998, January 1\u20134). Bitmap index design and evaluation. Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, Seattle, WA, USA.","DOI":"10.1145\/276304.276336"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1016\/j.is.2008.11.002","article-title":"RLH: Bitmap compression technique based on run-length and Huffman encoding","volume":"34","author":"Stabno","year":"2009","journal-title":"Inf. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Deli\u00e8ge, F., and Pedersen, T.B. (2010, January 22\u201326). Position list word aligned hybrid: Optimizing space and performance for compressed bitmaps. Proceedings of the 13th International Conference on Extending Database Technology, Lausanne, Switzerland.","DOI":"10.1145\/1739041.1739071"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Guzun, G., Canahuate, G., Chiu, D., and Sawin, J. (April, January 31). A tunable compression framework for bitmap indices. Proceedings of the 2014 IEEE 30th International Conference on Data Engineering, Chicago, IL, USA.","DOI":"10.1109\/ICDE.2014.6816675"},{"key":"ref_26","unstructured":"Corrales, F., Chiu, D., and Sawin, J. (September, January 29). Variable length compression for bitmap indices. Proceedings of the International Conference on Database and Expert Systems Applications, Toulouse, France."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.is.2016.07.004","article-title":"SBH: Super byte-aligned hybrid bitmap compression","volume":"62","author":"Kim","year":"2016","journal-title":"Inf. Syst."},{"key":"ref_28","unstructured":"Antoshenkov, G. (1995, January 28\u201330). Byte-aligned bitmap compression. Proceedings of the Data Compression Conference (DCC\u201995), Snowbird, UT, USA."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1132863.1132864","article-title":"Optimizing bitmap indices with efficient compression","volume":"31","author":"Wu","year":"2006","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1016\/j.ipl.2010.05.018","article-title":"Concise: Compressed \u2018n\u2019composable integer set","volume":"110","author":"Colantonio","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.datak.2009.08.006","article-title":"Sorting improves word-aligned bitmap indexes","volume":"69","author":"Lemire","year":"2010","journal-title":"Data Knowl. Eng."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"van Schaik, S.J., and de Moor, O. (2011, January 12\u201316). A memory efficient reachability data structure through bit vector compression. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, Athens, Greece.","DOI":"10.1145\/1989323.1989419"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1002\/spe.2325","article-title":"Better bitmap performance with roaring bitmaps","volume":"46","author":"Chambi","year":"2016","journal-title":"Softw. Pract. Exp."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TST.2015.7040519","article-title":"A survey of bitmap index compression algorithms for big data","volume":"20","author":"Chen","year":"2015","journal-title":"Tsinghua Sci. Technol."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Barik, R., Minutoli, M., Halappanavar, M., Tallent, N.R., and Kalyanaraman, A. (2020, January 27\u201329). Vertex Reordering for Real-World Graphs and Applications: An Empirical Evaluation. Proceedings of the 2020 IEEE International Symposium on Workload Characterization (IISWC), Beijing, China.","DOI":"10.1109\/IISWC50251.2020.00031"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Arai, J., Shiokawa, H., Yamamuro, T., Onizuka, M., and Iwamura, S. (2016, January 23\u201327). Rabbit order: Just-in-time parallel reordering for fast graph analysis. Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Chicago, IL, USA.","DOI":"10.1109\/IPDPS.2016.110"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Jacquelin, M., Ng, E.G., and Peyton, B.W. (2018, January 6\u20138). Fast and effective reordering of columns within supernodes using partition refinement. Proceedings of the 2018 Proceedings of the Seventh SIAM Workshop on Combinatorial Scientific Computing, Bergen, Norway.","DOI":"10.1137\/1.9781611975215.8"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/316194.316229","article-title":"On power-law relationships of the internet topology","volume":"29","author":"Faloutsos","year":"1999","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Sun, J., Vandierendonck, H., and Nikolopoulos, D.S. (2017, January 14\u201316). Graphgrind: Addressing load imbalance of graph partitioning. Proceedings of the International Conference on Supercomputing, Chicago, IL, USA.","DOI":"10.1145\/3079079.3079097"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/24\/9894\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:42:14Z","timestamp":1760146934000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/24\/9894"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,15]]},"references-count":39,"journal-issue":{"issue":"24","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["s22249894"],"URL":"https:\/\/doi.org\/10.3390\/s22249894","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,15]]}}}