{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:13:12Z","timestamp":1792156392543,"version":"4.4.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,9,1]],"date-time":"2012-09-01T00:00:00Z","timestamp":1346457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p>\n            Various methods have been used to represent a tree on\n            <jats:italic>n<\/jats:italic>\n            nodes in essentially the information-theoretic minimum space while supporting various navigational operations in constant time, but different representations usually support different operations. Our main contribution is a succinct representation of ordinal trees, based on that of Geary et al. [2006], that supports all the navigational operations supported by various succinct tree representations while requiring only 2\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) bits. It also supports efficient level-order traversal, a useful ordering previously supported only with a very limited set of operations.\n          <\/jats:p>\n          <jats:p>\n            Our second contribution expands on the notion of a single succinct representation supporting more than one traversal ordering, by showing that our method supports two other encoding schemes as abstract data types. In particular, it supports extracting a word (\n            <jats:italic>O<\/jats:italic>\n            (lg\n            <jats:italic>n<\/jats:italic>\n            ) bits) of the balanced parenthesis sequence or depth first unary degree sequence in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )) time, using at most\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            )+\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) additional bits, for any\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) in\n            <jats:italic>O<\/jats:italic>\n            (lg\n            <jats:italic>n<\/jats:italic>\n            ) and \u03a9(1).\n          <\/jats:p>","DOI":"10.1145\/2344422.2344432","type":"journal-article","created":{"date-parts":[[2012,10,2]],"date-time":"2012-10-02T13:50:00Z","timestamp":1349185800000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Succinct ordinal trees based on tree covering"],"prefix":"10.1145","volume":"8","author":[{"given":"Meng","family":"He","sequence":"first","affiliation":[{"name":"Dalhousie University, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[{"name":"Seoul National University, South Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000820"},{"key":"e_1_2_1_2_1","volume-title":"Tech. Rep. CS-2006-10","author":"Barbay J.","year":"2006"},{"key":"e_1_2_1_3_1","series-title":"Lecture Notes in Computer Science Series","volume-title":"Proceedings of the 4th Latin American Theoretical Informatics Symposium","author":"Bender M. A."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1146-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702411381"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 383--391","author":"Clark D. R."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90128-0"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69903-3_17"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_38"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198516"},{"key":"e_1_2_1_11_1","unstructured":"He M. 2007. Succinct indexes. Ph.D. dissertation University of Waterloo.  He M. 2007. Succinct indexes. Ph.D. dissertation University of Waterloo."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394539.2394601"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.09.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367068"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1151"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_84"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1198-x"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. 134--149","author":"Sadakane K."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187705"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344422.2344432","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2344422.2344432","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:39Z","timestamp":1750273659000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344422.2344432"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["10.1145\/2344422.2344432"],"URL":"https:\/\/doi.org\/10.1145\/2344422.2344432","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9]]},"assertion":[{"value":"2008-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}