{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:33Z","timestamp":1759637913905},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385261"},{"type":"electronic","value":"9783642385278"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38527-8_3","type":"book-chapter","created":{"date-parts":[[2013,5,8]],"date-time":"2013-05-08T13:23:02Z","timestamp":1368019382000},"page":"5-17","source":"Crossref","is-referenced-by-count":14,"title":["Design of Practical Succinct Data Structures for Large Data Collections"],"prefix":"10.1007","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[]},{"given":"Giuseppe","family":"Ottaviano","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","unstructured":"Apache Hadoop, \n                    \n                      http:\/\/hadoop.apache.org\/"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Arroyuelo, D., C\u00e1novas, R., Navarro, G., Sadakane, K.: Succinct trees in practice. In: ALENEX, pp. 84\u201397 (2010)","DOI":"10.1137\/1.9781611972900.9"},{"issue":"4","key":"3_CR3","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"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol.\u00a01776, pp. 88\u201394. Springer, Heidelberg (2000)"},{"issue":"4","key":"3_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":"6","key":"3_CR6","doi-asserted-by":"publisher","first-page":"1723","DOI":"10.1137\/S0097539702405292","volume":"31","author":"H. Buhrman","year":"2002","unstructured":"Buhrman, H., Miltersen, P.B., Radhakrishnan, J., Venkatesh, S.: Are bitvectors optimal? SIAM Journal on Computing\u00a031(6), 1723\u20131744 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/978-3-642-32241-9_34","volume-title":"Computing and Combinatorics","author":"P. Davoodi","year":"2012","unstructured":"Davoodi, P., Raman, R., Satti, S.R.: Succinct representations of binary trees for range minimum queries. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol.\u00a07434, pp. 396\u2013407. Springer, Heidelberg (2012)"},{"key":"3_CR8","unstructured":"Dean, J., Ghemawat, S.: MapReduce: Simplified data processing on large clusters. In: OSDI, pp. 137\u2013150 (2004)"},{"issue":"2","key":"3_CR9","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P. Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. Journal of the ACM (JACM)\u00a021(2), 246\u2013260 (1974)","journal-title":"Journal of the ACM (JACM)"},{"issue":"3","key":"3_CR10","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1145\/321892.321899","volume":"22","author":"P. Elias","year":"1975","unstructured":"Elias, P., Flower, R.A.: The complexity of some simple retrieval problems. Journal of the ACM\u00a022(3), 367\u2013379 (1975)","journal-title":"Journal of the ACM"},{"key":"3_CR11","unstructured":"Fano, R.: On the number of bits required to implement an associative memory. Memorandum 61. Computer Structures Group, Project MAC. MIT (1971)"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581","DOI":"10.1145\/1082036.1082039"},{"issue":"2","key":"3_CR13","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J. Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput.\u00a040(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Grossi, R., Ottaviano, G.: Fast compressed tries through path decompositions. In: ALENEX, pp. 65\u201374 (2012)","DOI":"10.1137\/1.9781611972924.7"},{"issue":"2","key":"3_CR15","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R. Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput.\u00a035(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Hsu, B.J.P., Ottaviano, G.: Space-efficient data structures for top-k completion. In: Proceedings of the 22st World Wide Web Conference (WWW) (2013)","DOI":"10.1145\/2488388.2488440"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: FOCS, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"3_CR18","unstructured":"JSON specification, \n                    \n                      http:\/\/json.org\/"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Kao, M.Y. (ed.): Encyclopedia of Algorithms. Springer (2008)","DOI":"10.1007\/978-0-387-30162-4"},{"key":"3_CR20","unstructured":"Knuth, D.E.: The Art of Computer Programming. Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams, vol.\u00a04. Addison-Wesley (2009)"},{"key":"3_CR21","unstructured":"libcds - Compact Data Structures Library, \n                    \n                      http:\/\/libcds.recoded.cl\/"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/3-540-56503-5_65","volume-title":"STACS 93","author":"P.B. Miltersen","year":"1993","unstructured":"Miltersen, P.B.: The bit probe complexity measure revisited. In: Enjalbert, P., Wagner, K.W., Finkel, A. (eds.) STACS 1993. LNCS, vol.\u00a0665, pp. 662\u2013671. Springer, Heidelberg (1993)"},{"issue":"3","key":"3_CR23","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 Journal on Computing\u00a031(3), 762\u2013776 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Okanohara, D., Sadakane, K.: Practical entropy-compressed rank\/select dictionary. In: ALENEX (2007)","DOI":"10.1137\/1.9781611972870.6"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Ottaviano, G., Grossi, R.: Semi-indexing semi-structured data in tiny space. In: CIKM, pp. 1485\u20131494 (2011)","DOI":"10.1145\/2063576.2063790"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Succincter. In: FOCS 2008, pp. 305\u2013313 (2008)","DOI":"10.1158\/AACR.EDB-08-8125"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: STOC, pp. 232\u2013240 (2006)","DOI":"10.1145\/1132516.1132551"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Alg. 3(4) (2007)","DOI":"10.1145\/1290672.1290680"},{"key":"3_CR29","unstructured":"rsdic - Compressed Rank Select Dictionary, \n                    \n                      http:\/\/code.google.com\/p\/rsdic\/"},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: SODA 2010, pp. 134\u2013149 (2010)","DOI":"10.1137\/1.9781611973075.13"},{"key":"3_CR31","unstructured":"SDSL - Succinct Data Structure Library, \n                    \n                      http:\/\/www.uni-ulm.de\/in\/theo\/research\/sdsl.html"},{"key":"3_CR32","unstructured":"Succinct library, \n                    \n                      http:\/\/github.com\/ot\/succinct"},{"key":"3_CR33","unstructured":"Sux - Implementing Succinct Data Structures, \n                    \n                      http:\/\/sux.dsi.unimi.it\/"},{"key":"3_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-540-68552-4_12","volume-title":"Experimental Algorithms","author":"S. Vigna","year":"2008","unstructured":"Vigna, S.: Broadword implementation of rank\/select queries. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol.\u00a05038, pp. 154\u2013168. Springer, Heidelberg (2008)"},{"issue":"6","key":"3_CR35","doi-asserted-by":"publisher","first-page":"1593","DOI":"10.1137\/090766619","volume":"41","author":"E. Viola","year":"2012","unstructured":"Viola, E.: Bit-probe lower bounds for succinct data structures. SIAM J. Comput.\u00a041(6), 1593\u20131604 (2012)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38527-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T23:30:44Z","timestamp":1557703844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38527-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385261","9783642385278"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38527-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}