{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:58Z","timestamp":1760202658728},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642402722"},{"type":"electronic","value":"9783642402739"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40273-9_20","type":"book-chapter","created":{"date-parts":[[2013,8,10]],"date-time":"2013-08-10T01:20:34Z","timestamp":1376097634000},"page":"319-332","source":"Crossref","is-referenced-by-count":9,"title":["Succinct Representations of Ordinal Trees"],"prefix":"10.1007","author":[{"given":"Rajeev","family":"Raman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Srinivasa","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: On finding lowest common ancestors in trees. In: Aho, A.V., Borodin, A., Constable, R.L., Floyd, R.W., Harrison, M.A., Karp, R.M., Strong, H.R. (eds.) STOC, pp. 253\u2013265. ACM (1973)","DOI":"10.1145\/800125.804056"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Arroyuelo, D., C\u00e1novas, R., Navarro, G., Sadakane, K.: Succinct trees in practice. In: Blelloch, G.E., Halperin, D. (eds.) ALENEX, pp. 84\u201397. SIAM (2010)","DOI":"10.1137\/1.9781611972900.9"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Arroyuelo, D., Claude, F., Maneth, S., M\u00e4kinen, V., Navarro, G., Nguyen, K., Sir\u00e9n, J., V\u00e4lim\u00e4ki, N.: Fast in-memory XPath search using compressed indexes. In: Li, F., Moro, M.M., Ghandeharizadeh, S., Haritsa, J.R., Weikum, G., Carey, M.J., Casati, F., Chang, E.Y., Manolescu, I., Mehrotra, S., Dayal, U., Tsotras, V.J. (eds.) ICDE, pp. 417\u2013428. IEEE (2010)","DOI":"10.1109\/ICDE.2010.5447858"},{"issue":"4","key":"20_CR4","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/2000807.2000820","volume":"7","author":"J. Barbay","year":"2011","unstructured":"Barbay, J., He, M., Munro, J.I., Satti, S.R.: Succinct indexes for strings, binary relations and multilabeled trees. ACM Transactions on Algorithms\u00a07(4), 52 (2011)","journal-title":"ACM Transactions on Algorithms"},{"issue":"4","key":"20_CR5","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D. Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica\u00a043(4), 275\u2013292 (2005)","journal-title":"Algorithmica"},{"issue":"2","key":"20_CR6","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O. Berkman","year":"1994","unstructured":"Berkman, O., Vishkin, U.: Finding level-ancestors in trees. J. Comput. Syst. Sci.\u00a048(2), 214\u2013230 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings. In: SODA, pp. 373\u2013389. SIAM (2011)","DOI":"10.1137\/1.9781611973082.30"},{"issue":"4","key":"20_CR8","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1137\/S0097539702411381","volume":"34","author":"Y.T. Chiang","year":"2005","unstructured":"Chiang, Y.T., Lin, C.C., Lu, H.I.: Orderly spanning trees with applications. SIAM J. Comput.\u00a034(4), 924\u2013945 (2005)","journal-title":"SIAM J. Comput."},{"key":"20_CR9","unstructured":"Chupa, K.: Efficient Representation of Binary Search Trees. Master\u2019s thesis, University of Waterloo (1997)"},{"key":"20_CR10","unstructured":"Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage (extended abstract). In: ACM-SIAM SODA, pp. 383\u2013391 (1996)"},{"key":"20_CR11","unstructured":"Clark, D.R.: Compact PAT trees. Ph.D. thesis, University of Waterloo, Waterloo, Ontario., Canada (1998)"},{"issue":"3","key":"20_CR12","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/spe.4380230305","volume":"23","author":"J.J. Darragh","year":"1993","unstructured":"Darragh, J.J., Cleary, J.G., Witten, I.H.: Bonsai: a compact representation of trees. Softw. Pract. Exper.\u00a023(3), 277\u2013291 (1993)","journal-title":"Softw. Pract. Exper."},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Delpratt, O., Raman, R., Rahman, N.: Engineering succinct DOM. In: EDBT. ACM Intl. Conference Proceeding Series, vol.\u00a0261, pp. 49\u201360. ACM (2008)","DOI":"10.1145\/1353343.1353354"},{"key":"20_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/11764298_12","volume-title":"Experimental Algorithms","author":"O. Delpratt","year":"2006","unstructured":"Delpratt, O., Rahman, N., Raman, R.: Engineering the LOUDS succinct tree representation. In: \u00c0lvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol.\u00a04007, pp. 134\u2013145. Springer, Heidelberg (2006)"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-540-69903-3_17","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"A. Farzan","year":"2008","unstructured":"Farzan, A., Munro, J.I.: A uniform approach towards succinct representation of trees. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol.\u00a05124, pp. 173\u2013184. Springer, Heidelberg (2008)"},{"issue":"24","key":"20_CR16","doi-asserted-by":"publisher","first-page":"2668","DOI":"10.1016\/j.tcs.2010.10.030","volume":"412","author":"A. Farzan","year":"2011","unstructured":"Farzan, A., Munro, J.I.: Succinct representation of dynamic trees. Theor. Comput. Sci.\u00a0412(24), 2668\u20132678 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-642-02927-1_38","volume-title":"Automata, Languages and Programming","author":"A. Farzan","year":"2009","unstructured":"Farzan, A., Raman, R., Rao, S.S.: Universal succinct representations of trees? In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol.\u00a05555, pp. 451\u2013462. Springer, Heidelberg (2009)"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. J. ACM\u00a057(1) (2009)","DOI":"10.1145\/1613676.1613680"},{"issue":"3","key":"20_CR19","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.tcs.2007.02.047","volume":"379","author":"A. G\u00e1l","year":"2007","unstructured":"G\u00e1l, A., Miltersen, P.B.: The cell probe complexity of succinct data structures. Theor. Comput. Sci.\u00a0379(3), 405\u2013417 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"20_CR20","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/1198513.1198516","volume":"2","author":"R.F. Geary","year":"2006","unstructured":"Geary, R.F., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. ACM Transactions on Algorithms\u00a02(4), 510\u2013534 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"3","key":"20_CR21","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.tcs.2006.09.014","volume":"368","author":"R.F. Geary","year":"2006","unstructured":"Geary, R.F., Rahman, N., Raman, R., Raman, V.: A simple optimal representation for balanced parentheses. Theor. Comput. Sci.\u00a0368(3), 231\u2013246 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR22","unstructured":"Gog, S.: Succinct data structure library, SDSL (2013), https:\/\/github.com\/simongog\/sdsl"},{"key":"20_CR23","doi-asserted-by":"crossref","unstructured":"Golin, M.J., Iacono, J., Krizanc, D., Raman, R., Rao, S.S., Shende, S.: Encoding 2-d range maximum queries. CoRR abs\/1109.2885v2 (2012)","DOI":"10.1007\/978-3-642-25591-5_20"},{"key":"20_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-540-75520-3_34","volume-title":"Algorithms \u2013 ESA 2007","author":"A. Golynski","year":"2007","unstructured":"Golynski, A., Grossi, R., Gupta, A., Raman, R., Rao, S.S.: On the size of succinct indices. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 371\u2013382. Springer, Heidelberg (2007)"},{"issue":"4","key":"20_CR25","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/2344422.2344432","volume":"8","author":"M. He","year":"2012","unstructured":"He, M., Munro, J.I., Rao, S.S.: Succinct ordinal trees based on tree covering. ACM Transactions on Algorithms\u00a08(4), 42 (2012)","journal-title":"ACM Transactions on Algorithms"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Jacobson, G.J.: Space-efficient static trees and graphs. In: IEEE Symposium on Foundations of Computer Science, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"2","key":"20_CR27","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1016\/j.jcss.2011.09.002","volume":"78","author":"J. Jansson","year":"2012","unstructured":"Jansson, J., Sadakane, K., Sung, W.K.: Ultra-succinct representation of ordered trees with applications. Journal of Computer and System Sciences\u00a078(2), 619\u2013631 (2012)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-642-30850-5_20","volume-title":"Experimental Algorithms","author":"S. Joannou","year":"2012","unstructured":"Joannou, S., Raman, R.: Dynamizing succinct tree representations. In: Klasing, R. (ed.) SEA 2012. LNCS, vol.\u00a07276, pp. 224\u2013235. Springer, Heidelberg (2012)"},{"key":"20_CR29","doi-asserted-by":"crossref","unstructured":"Jurkiewicz, T., Mehlhorn, K.: The cost of address translation. In: Sanders, P., Zeh, N. (eds.) ALENEX, pp. 148\u2013162. SIAM (2010)","DOI":"10.1137\/1.9781611972931.13"},{"issue":"4","key":"20_CR30","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1142\/S0129054190000291","volume":"1","author":"J. Katajainen","year":"1990","unstructured":"Katajainen, J., M\u00e4kinen, E.: Tree compression and optimization with applications. Int. J. Found. Comput. Sci.\u00a01(4), 425\u2013448 (1990)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"13","key":"20_CR31","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1002\/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O","volume":"29","author":"S. Kurtz","year":"1999","unstructured":"Kurtz, S.: Reducing the space requirement of suffix trees. Softw., Pract. Exper.\u00a029(13), 1149\u20131171 (1999)","journal-title":"Softw., Pract. Exper."},{"issue":"3","key":"20_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1367064.1367068","volume":"4","author":"H. Lu","year":"2008","unstructured":"Lu, H., Yeh, C.: Balanced parentheses strike back. ACM Trans. Algorithms\u00a04(3), 1\u201313 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"20_CR33","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput.\u00a031(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"20_CR34","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jagm.2000.1151","volume":"39","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V., Rao, S.S.: Space efficient suffix trees. J. Algorithms\u00a039(2), 205\u2013222 (2001)","journal-title":"J. Algorithms"},{"key":"20_CR35","unstructured":"Munro, J.I., Raman, V., Storm, A.J.: Representing dynamic binary trees succinctly. In: Kosaraju, S.R. (ed.) SODA, pp. 529\u2013536. ACM\/SIAM (2001)"},{"key":"20_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1007\/978-3-540-27836-8_84","volume-title":"Automata, Languages and Programming","author":"J.I. Munro","year":"2004","unstructured":"Munro, J.I., Rao, S.S.: Succinct representations of functions. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1006\u20131015. Springer, Heidelberg (2004)"},{"key":"20_CR37","unstructured":"Ottaviano, G.: The succinct library (2013), https:\/\/github.com\/ot\/succinct"},{"key":"20_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/978-3-642-38527-8_3","volume-title":"Experimental Algorithms","author":"R. Grossi","year":"2013","unstructured":"Grossi, R., Ottaviano, G.: Design of practical succinct data structures for large data collections. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol.\u00a07933, pp. 5\u201317. Springer, Heidelberg (2013)"},{"key":"20_CR39","doi-asserted-by":"crossref","unstructured":"Patrascu, M.: Succincter. In: FOCS, pp. 305\u2013313. IEEE Computer Society (2008)","DOI":"10.1109\/FOCS.2008.83"},{"key":"20_CR40","unstructured":"Poyias, A.: XXML: Handling extra-large XML documents. siXML technology whitepaper (February 2013), https:\/\/lra.le.ac.uk\/bitstream\/2381\/27744\/1\/SiXDOMWhitepaper.pdf"},{"issue":"4","key":"20_CR41","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R. Raman","year":"2007","unstructured":"Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms 3(4), 43 (2007); Preliminary version in SODA 2002","journal-title":"ACM Transactions on Algorithms"},{"key":"20_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/3-540-45061-0_30","volume-title":"Automata, Languages and Programming","author":"R. Raman","year":"2003","unstructured":"Raman, R., Rao, S.S.: Succinct dynamic dictionaries and trees. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 357\u2013368. Springer, Heidelberg (2003)"},{"key":"20_CR43","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Charikar, M. (ed.) SODA, pp. 134\u2013149. SIAM (2010)","DOI":"10.1137\/1.9781611973075.13"},{"issue":"3","key":"20_CR44","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM\u00a032(3), 652\u2013686 (1985)","journal-title":"J. ACM"},{"key":"20_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-33122-0_16","volume-title":"Algorithms in Bioinformatics","author":"Y. Tabei","year":"2012","unstructured":"Tabei, Y.: Succinct multibit tree: Compact representation of multibit trees by using succinct data structures in chemical fingerprint searches. In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS, vol.\u00a07534, pp. 201\u2013213. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Space-Efficient Data Structures, Streams, and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40273-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T19:31:44Z","timestamp":1563651104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40273-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642402722","9783642402739"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40273-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}