{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:13Z","timestamp":1759637953341},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403125"},{"type":"electronic","value":"9783642403132"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_30","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T14:36:43Z","timestamp":1376663803000},"page":"325-336","source":"Crossref","is-referenced-by-count":4,"title":["Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees"],"prefix":"10.1007","author":[{"given":"Stephane","family":"Durocher","sequence":"first","affiliation":[]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[]},{"given":"Matthew","family":"Skala","sequence":"additional","affiliation":[]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1007\/978-3-642-04128-0_61","volume-title":"Algorithms - ESA 2009","author":"D. Belazzougui","year":"2009","unstructured":"Belazzougui, D., Botelho, F.C., Dietzfelbinger, M.: Hash, displace, and compress. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 682\u2013693. Springer, Heidelberg (2009)"},{"key":"30_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-3-642-40104-6_11","volume-title":"WADS 2013","author":"D. Belazzougui","year":"2013","unstructured":"Belazzougui, D., Gagie, T., Navarro, G.: Better space bounds for parameterized range majority and minority. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol.\u00a08037, pp. 121\u2013132. Springer, Heidelberg (2013)"},{"key":"30_CR3","unstructured":"Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. In: Proc. STACS, vol.\u00a014, pp. 291\u2013301 (2012)"},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. Theory Comp. Sys. (2013)","DOI":"10.1007\/s00224-013-9455-2"},{"key":"30_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-31155-0_26","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"T.M. Chan","year":"2012","unstructured":"Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T.: Linear-space data structures for range minority query in arrays. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 295\u2013306. Springer, Heidelberg (2012)"},{"issue":"3","key":"30_CR6","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: A new approach to query-answering. SIAM J. Comp.\u00a015(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comp."},{"key":"30_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-22006-7_21","volume-title":"Automata, Languages and Programming","author":"S. Durocher","year":"2011","unstructured":"Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 244\u2013255. Springer, Heidelberg (2011)"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.ic.2012.10.011","volume":"222","author":"S. Durocher","year":"2013","unstructured":"Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. Inf. & Comp.\u00a0222, 169\u2013179 (2013)","journal-title":"Inf. & Comp."},{"key":"30_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-24583-1_29","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2011","unstructured":"Gagie, T., He, M., Munro, J.I., Nicholson, P.K.: Finding frequent elements in compressed 2D arrays and strings. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 295\u2013300. Springer, Heidelberg (2011)"},{"key":"30_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/3-540-44693-1_28","volume-title":"STACS 2001","author":"T. Hagerup","year":"2001","unstructured":"Hagerup, T., Tholey, T.: Efficient minimal perfect hashing in nearly minimal space. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 317\u2013326. Springer, Heidelberg (2001)"},{"key":"30_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/978-3-540-24587-2_53","volume-title":"Algorithms and Computation","author":"D. Krizanc","year":"2003","unstructured":"Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 517\u2013526. Springer, Heidelberg (2003)"},{"key":"30_CR12","first-page":"1","volume":"12","author":"D. Krizanc","year":"2005","unstructured":"Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. Nordic J. Computing\u00a012, 1\u201317 (2005)","journal-title":"Nordic J. Computing"},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proc. ACM-SIAM SODA, pp. 134\u2013149 (2010)","DOI":"10.1137\/1.9781611973075.13"},{"issue":"5","key":"30_CR14","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"J.P. Schmidt","year":"1990","unstructured":"Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput.\u00a019(5), 775\u2013786 (1990)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,21]],"date-time":"2019-07-21T06:26:21Z","timestamp":1563690381000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}