{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:09Z","timestamp":1759639089319},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401039"},{"type":"electronic","value":"9783642401046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_35","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T01:36:30Z","timestamp":1373506590000},"page":"402-414","source":"Crossref","is-referenced-by-count":0,"title":["Compressed Persistent Index for Efficient Rank\/Select Queries"],"prefix":"10.1007","author":[{"given":"Wing-Kai","family":"Hon","sequence":"first","affiliation":[]},{"given":"Lap-Kei","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[]},{"given":"Konstantinos","family":"Tsakalidis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Sioutas, S., Tsakalidis, K., Tsichlas, K.: Fully persistent B-trees. In: Proc. SODA, pp. 602\u2013614 (2012)","DOI":"10.1137\/1.9781611973099.51"},{"key":"35_CR2","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proc. STOC, pp. 91\u2013100 (2004)","DOI":"10.1145\/1007352.1007374"},{"key":"35_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-51542-9_8","volume-title":"Algorithms and Data Structures","author":"P.F. Dietz","year":"1989","unstructured":"Dietz, P.F.: Fully Persistent arrays. In: Dehne, F., Santoro, N., Sack, J.-R. (eds.) WADS 1989. LNCS, vol.\u00a0382, pp. 67\u201374. Springer, Heidelberg (1989)"},{"issue":"1","key":"35_CR4","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J.R. Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. Syst. Sci.\u00a038(1), 86\u2013124 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"35_CR5","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proc. FOCS, pp. 390\u2013398 (2000)"},{"key":"35_CR6","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proc. SODA, pp. 841\u2013850 (2003)"},{"key":"35_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1007\/978-3-540-30551-4_49","volume-title":"Algorithms and Computation","author":"J. J\u00e1J\u00e1","year":"2004","unstructured":"J\u00e1J\u00e1, J., Mortensen, C.W., Shi, Q.: Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 558\u2013568. Springer, Heidelberg (2004)"},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"Kaplan, H.: Persistent data structures. In: Handbook on Data Structures and Applications, ch. 31, pp. 31-1\u201331-26. CRC Press (2004)","DOI":"10.1201\/9781420035179.ch31"},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"Kopelowitz, T.: On-line indexing for general alphabets via predecessor queries on subsets of an ordered list. In: Proc. FOCS, pp. 283\u2013292 (2012)","DOI":"10.1109\/FOCS.2012.79"},{"issue":"3","key":"35_CR10","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/cmb.2009.0169","volume":"17","author":"V. M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., Navarro, G., Sir\u00e9n, J., V\u00e4lim\u00e4ki, N.: Storage and retrieval of highly repetitive sequence collections. J. Comp. Biology\u00a017(3), 281\u2013308 (2010)","journal-title":"J. Comp. Biology"},{"issue":"4","key":"35_CR11","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","volume":"42","author":"Y. Nekrich","year":"2009","unstructured":"Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. Comput. Geom.\u00a042(4), 342\u2013351 (2009)","journal-title":"Comput. Geom."},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Lower bounds for 2-dimensional range counting. In: Proc. STOC, pp. 40\u201346 (2007)","DOI":"10.1145\/1250790.1250797"},{"issue":"4","key":"35_CR13","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R. Raman","year":"2007","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms\u00a03(4), 43 (2007)","journal-title":"ACM Transactions on Algorithms"},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proc. SODA, pp. 134\u2013149 (2010)","DOI":"10.1137\/1.9781611973075.13"},{"issue":"7319","key":"35_CR15","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1038\/nature09534","volume":"467","author":"The 1000 Genomes Project Consortium","year":"2010","unstructured":"The 1000 Genomes Project Consortium. A map of human genome variation from population-scale sequencing. Nature 467(7319), 1061\u20131073 (2010)","journal-title":"Nature"},{"issue":"2","key":"35_CR16","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \u0398(n). Information Processing Letters\u00a017(2), 81\u201384 (1983)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40104-6_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T14:27:40Z","timestamp":1557930460000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}