{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:15:22Z","timestamp":1776802522708,"version":"3.51.2"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2022,12,21]],"date-time":"2022-12-21T00:00:00Z","timestamp":1671580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,1,17]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The Block Tree is a data structure for representing repetitive sequences in compressed space, which reaches space comparable with that of Lempel\u2013Ziv compression while retaining fast direct access to any position in the sequence. In this paper, we generalize Block Trees to two dimensions, in order to exploit repetitive patterns in the representation of images, matrices and other kinds of bidimensional data. We demonstrate the practicality of the two-dimensional Block Trees (2D-BTs) in representing the adjacency matrices of Web graphs, and raster images in GIS applications. For this purpose, we integrate our 2D-BT with the $k^2$-tree\u2014an efficient structure that exploits clustering and sparseness to compress adjacency matrices\u2014so that it also exploits repetitive patterns. Our experiments show that this structure uses 60\u201380% of the space of the original $k^2$-tree, while being 30% faster to three times slower when accessing cells.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac182","type":"journal-article","created":{"date-parts":[[2022,12,22]],"date-time":"2022-12-22T13:18:02Z","timestamp":1671715082000},"page":"391-406","source":"Crossref","is-referenced-by-count":5,"title":["Two-Dimensional Block Trees"],"prefix":"10.1093","volume":"67","author":[{"given":"Nieves R","family":"Brisaboa","sequence":"first","affiliation":[{"name":"Universidade da Coru\u00f1a, CITIC, Facultade de Inform\u00e1tica , 15071 A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"CeBiB, Faculty of Computer Science, Dalhousie University , Halifax, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adri\u00e1n","family":"G\u00f3mez-Brand\u00f3n","sequence":"additional","affiliation":[{"name":"CeBiB, Universidade da Coru\u00f1a, CITIC, Facultade de Inform\u00e1tica , 15071 A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"CeBiB, Department of Computer Science, University of Chile , Beauchef 851, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,12,21]]},"reference":[{"key":"2024012011463239300_ref1","volume-title":"Compact Data Structures \u2013 A practical approach","author":"Gonzalo","year":"2016"},{"key":"2024012011463239300_ref2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TIT.1986.1057132","article-title":"Compression of two-dimensional data","volume":"32","author":"Lempel","year":"1986","journal-title":"IEEE Transactions On Information Theory."},{"key":"2024012011463239300_ref3","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0097-8493(99)00140-5","article-title":"Lossless compression of large binary images in digital spatial libraries","volume":"24","author":"Ageenko","year":"2000","journal-title":"Computers & Graphics."},{"key":"2024012011463239300_ref4","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1109\/MMDBMS.1996.541859","volume-title":"Proc. International Workshop on Multimedia Database Management Systems","author":"Pajarola","year":"1996"},{"key":"2024012011463239300_ref5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2020.11.002","article-title":"Block trees","volume":"117","author":"Bellazzougui","year":"2021","journal-title":"Journal of Computer and System Sciences."},{"key":"2024012011463239300_ref6","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","article-title":"On the complexity of finite sequences","volume":"22","author":"Lempel","year":"1976","journal-title":"IEEE Transactions On Information Theory."},{"key":"2024012011463239300_ref7","doi-asserted-by":"crossref","first-page":"872","DOI":"10.1109\/5.286191","article-title":"The sliding-window Lempel-Ziv algorithm is asymptotically optimal","volume":"82","author":"Wyner","year":"1994","journal-title":"Proc. IEEE"},{"key":"2024012011463239300_ref8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2011.11.022","article-title":"Quasi-distinct parsing and optimal compression methods","volume":"422","author":"Amir","year":"2012","journal-title":"Theoretical Computer Science."},{"key":"2024012011463239300_ref9","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.3390\/a2031031","article-title":"Graph compression by BFS","volume":"3","author":"Apostolico","year":"2009","journal-title":"Algorithms"},{"key":"2024012011463239300_ref10","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1145\/988672.988752","volume-title":"Proc. 13th International Conference on World Wide Web","author":"Boldi","year":"2004"},{"key":"2024012011463239300_ref11","volume-title":"Man-Machine Interactions 2","author":"Grabowski","year":"2011"},{"key":"2024012011463239300_ref12","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s10115-013-0648-4","article-title":"Compressed representations for web and social graphs","volume":"40","author":"Hern\u00e1ndez","year":"2014","journal-title":"Knowledge and Information Systems."},{"key":"2024012011463239300_ref13","doi-asserted-by":"crossref","first-page":"219233","DOI":"10.1109\/ACCESS.2020.3040673","article-title":"Zuckerli: a new compressed representation for graphs","volume":"8","author":"Versari","year":"2020","journal-title":"IEEE Access."},{"key":"2024012011463239300_ref14","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/j.is.2013.08.003","article-title":"Compact representation of web graphs with extended functionality","volume":"39","author":"Brisaboa","year":"2014","journal-title":"Information Systems."},{"key":"2024012011463239300_ref15","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/978-3-319-15579-1_45","volume-title":"Proc. 9th International Conference on Language and Automata Theory and Applications","author":"Bille","year":"2015"},{"key":"2024012011463239300_ref16","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.ins.2019.08.007","article-title":"Extending general compact querieable representations to GIS applications","volume":"506","author":"Brisaboa","year":"2020","journal-title":"Inform. Sci."},{"key":"2024012011463239300_ref17","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Proc. 16th Conference Foundations of Software Technology and Theoretical Computer Science","author":"Munro","year":"1996"},{"key":"2024012011463239300_ref18","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1145\/1963405.1963488","volume-title":"Proc. 20th International Conference on World Wide Web","author":"Boldi","year":"2011"},{"key":"2024012011463239300_ref19","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.is.2017.10.007","article-title":"Scalable and queryable compressed storage structure for raster data","volume":"72","author":"Ladra","year":"2017","journal-title":"Information Systems."},{"key":"2024012011463239300_ref20","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.ipm.2012.08.003","article-title":"DACs: bringing direct access to variable-length codes","volume":"49","author":"Brisaboa","year":"2013","journal-title":"Inf. Process. Manag."},{"key":"2024012011463239300_ref21","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","article-title":"Efficient randomized pattern-matching algorithms","volume":"31","author":"Karp","year":"1987","journal-title":"IBM Journal of Research and Development."},{"key":"2024012011463239300_ref22","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(77)90017-5","article-title":"Two dimensional pattern matching","volume":"6","author":"Bird","year":"1977","journal-title":"Information Processing Letters."},{"key":"2024012011463239300_ref23","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1137\/0207043","article-title":"A technique for extending rapid exact-match string matching to arrays of more than one dimension","volume":"7","author":"Baker","year":"1978","journal-title":"SIAM Journal on Computing."},{"key":"2024012011463239300_ref24","first-page":"326","volume-title":"Proc. 13th International Symposium on Experimental Algorithms","author":"Gog","year":"2014"},{"key":"2024012011463239300_ref25","doi-asserted-by":"crossref","first-page":"1965","DOI":"10.1002\/joc.1276","article-title":"Very high resolution interpolated climate surfaces for global land areas","volume":"25","author":"Hijmans","year":"2005","journal-title":"Int. J. Climatol."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/1\/391\/56167826\/bxac182.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/1\/391\/56167826\/bxac182.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,20]],"date-time":"2024-01-20T11:46:47Z","timestamp":1705751207000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/67\/1\/391\/6955257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,21]]},"references-count":25,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,12,21]]},"published-print":{"date-parts":[[2024,1,17]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac182","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,1]]},"published":{"date-parts":[[2022,12,21]]}}}