{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T17:44:58Z","timestamp":1743097498305,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":20,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_638","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:30Z","timestamp":1461269010000},"page":"1776-1780","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Rank and Select Operations on Sequences"],"prefix":"10.1007","author":[{"given":"Travis","family":"Gagie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"4","key":"320_CR18161","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2000807.2000820","volume":"7","author":"J Barbay","year":"2011","unstructured":"Barbay J, He M, Munro JI, Rao SS (2011) Succinct indexes for strings, binary relations and multilabeled trees. ACM Trans Algorithms 7(4):1\u201327","journal-title":"ACM Trans Algorithms"},{"key":"320_CR18162","doi-asserted-by":"crossref","unstructured":"Barbay J, Claude F, Gagie T, Navarro G, Nekrich Y (2014) Efficient fully-compressed sequence representations. Algorithmica 69(1):232\u2013268 [20] was presented in Philadelphia, USA","DOI":"10.1007\/s00453-012-9726-3"},{"key":"320_CR18163","first-page":"181","volume-title":"Proceedings of the 20th European symposium on algorithms","author":"D Belazzougui","year":"2012","unstructured":"Belazzougui D, Navarro G (2012) New lower and upper bounds for representing sequences. In: Proceedings of the 20th European symposium on algorithms, Ljubljana, Slovenia, pp\u00a0181\u2013192"},{"key":"320_CR18164","unstructured":"Belazzougui D, Navarro G (2013) New lower and upper bounds for representing sequences. CoRR abs\/1111.2621v2. To appear in ACM Transactions on Algorithms"},{"issue":"4","key":"320_CR18165","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2635816","volume":"10","author":"D Belazzougui","year":"2014","unstructured":"Belazzougui D, Navarro G (2014) Alphabet-independent compressed text indexing. ACM Trans Algorithms 10(4):1\u201319","journal-title":"ACM Trans Algorithms"},{"key":"320_CR18166","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.is.2014.06.002","volume":"47","author":"F Claude","year":"2015","unstructured":"Claude F, Navarro G, Ord\u00f3\u00f1ez A (2015) The wavelet matrix: an efficient wavelet tree for large alphabets. Inf Syst 47:15\u201332","journal-title":"Inf Syst"},{"key":"320_CR18167","doi-asserted-by":"crossref","unstructured":"Ferragina P, Manzini G, M\u00e4kinen V, Navarro G (2007) Compressed representations of sequences and full-text indexes. ACM Trans Algorithms 3(2)","DOI":"10.1145\/1240233.1240243"},{"key":"320_CR18168","doi-asserted-by":"crossref","unstructured":"Fredman ML, Saks ME (1989) The cell probe complexity of dynamic data structures. In: Proceedings of the 21st symposium on theory of computing, Seattle, USA pp\u00a0345\u2013354","DOI":"10.1145\/73007.73040"},{"key":"320_CR18169","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1137\/1.9781611973068.69","volume-title":"Proceedings of the 20th symposium on discrete algorithms","author":"A Golynski","year":"2009","unstructured":"Golynski A (2009) Cell probe lower bounds for succinct data structures. In: Proceedings of the 20th symposium on discrete algorithms, New York, USA, pp\u00a0625\u2013634"},{"key":"320_CR18170","first-page":"368","volume-title":"Proceedings of the 17th symposium on discrete algorithms","author":"A Golynski","year":"2006","unstructured":"Golynski A, Munro JI, Rao SS (2006) Rank\/select operations on large alphabets: a tool for text indexing. In: Proceedings of the 17th symposium on discrete algorithms, Miami, USA, pp\u00a0368\u2013373"},{"key":"320_CR18171","first-page":"148","volume-title":"Proceedings of the 11th scandinavian workshop on algorithm theory","author":"A Golynski","year":"2008","unstructured":"Golynski A, Raman R, Rao SS (2008) On the redundancy of succinct data structures. In: Proceedings of the 11th scandinavian workshop on algorithm theory, Gothenburg, Sweden, pp\u00a0148\u2013159"},{"key":"320_CR18172","first-page":"841","volume-title":"Proceedings of the 14th symposium on discrete algorithms","author":"R Grossi","year":"2003","unstructured":"Grossi R, Gupta A, Vitter JS (2003) High-order entropy-compressed text indexes. In: Proceedings of the 14th symposium on discrete algorithms, Baltimore, USA, pp\u00a0841\u2013850"},{"key":"320_CR18173","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1007\/978-3-642-14165-2_57","volume-title":"Proceedings of the 37th international colloquium on automata, languages and programming","author":"R Grossi","year":"2010","unstructured":"Grossi R, Orlandi A, Raman R (2010) Optimal trade-offs for succinct string indexes. In: Proceedings of the 37th international colloquium on automata, languages and programming, Bordeaux, France, pp\u00a0678\u2013689"},{"key":"320_CR18174","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1007\/978-3-642-39206-1_43","volume-title":"Proceedings of the 40th international colloquium on languages, automata and programming","author":"R Grossi","year":"2013","unstructured":"Grossi R, Raman R, Satti SR, Venturini R (2013) Dynamic compressed strings with random access. In: Proceedings of the 40th international colloquium on languages, automata and programming, Riga, Latvia, pp\u00a0504\u2013515"},{"key":"320_CR18175","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-16321-0_35","volume-title":"Proceedings of the 17th symposium on string processing and information retrieval","author":"M He","year":"2010","unstructured":"He M, Munro JI (2010) Succinct representations of dynamic strings. In: Proceedings of the 17th symposium on string processing and information retrieval, Los Cabos, Mexico, pp\u00a0334\u2013346"},{"key":"320_CR18176","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1109\/SFCS.1989.63533","volume-title":"Proceedings of the 30th symposium on foundations of computer science","author":"G Jacobson","year":"1989","unstructured":"Jacobson G (1989) Space-efficient static trees and graphs. In: Proceedings of the 30th symposium on foundations of computer science, Research Triangle Park, North Carolina, USA, pp\u00a0549\u2013554"},{"key":"320_CR18177","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/1.9781611973105.62","volume-title":"Proceedings of the 24th symposium on discrete algorithms","author":"G Navarro","year":"2013","unstructured":"Navarro G, Nekrich Y (2013) Optimal dynamic sequence representations. In: Proceedings of the 24th symposium on discrete algorithms, New Orleans, USA, pp\u00a0865\u2013876"},{"key":"320_CR18178","doi-asserted-by":"crossref","unstructured":"Navarro G, Nekrich Y (2013) Optimal dynamic sequence representations. CoRR abs\/1206.6982v2. To appear in SIAM Journal on Computing","DOI":"10.1137\/1.9781611973105.62"},{"issue":"3","key":"320_CR18179","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2601073","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro G, Sadakane K (2014) Fully functional static and dynamic succinct trees. ACM Trans Algorithms 10(3):1\u201339","journal-title":"ACM Trans Algorithms"},{"key":"320_CR18180","first-page":"305","volume-title":"Proceedings of the 49th symposium on foundations of computer science","author":"M P\u01cetra\u015fcu","year":"2008","unstructured":"P\u01cetra\u015fcu M (2008) Succincter. In: Proceedings of the 49th symposium on foundations of computer science, Philadelphia, USA, pp\u00a0305\u2013313"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T19:06:24Z","timestamp":1567796784000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_638","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}