{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:26Z","timestamp":1759639046896},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,15]],"date-time":"2014-10-15T00:00:00Z","timestamp":1413331200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9947-8","type":"journal-article","created":{"date-parts":[[2014,10,14]],"date-time":"2014-10-14T15:45:01Z","timestamp":1413301501000},"page":"344-366","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees"],"prefix":"10.1007","volume":"74","author":[{"given":"Stephane","family":"Durocher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Skala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,15]]},"reference":[{"key":"9947_CR1","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Botelho, F.C., Dietzfelbinger, M.: Hash, displace, and compress. In: Proceedings of ESA, LNCS, vol. 5757, pp. 682\u2013693. Springer (2009)","DOI":"10.1007\/978-3-642-04128-0_61"},{"key":"9947_CR2","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Gagie, T., Navarro, G.: Better space bounds for parameterized range majority and minority. In: Proceedings of WADS, LNCS, vol. 8037. Springer (2013)","DOI":"10.1007\/978-3-642-40104-6_11"},{"key":"9947_CR3","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Navarro, G.: New lower and upper bounds for representing sequences. In: Proceedings of ESA, LNCS, vol. 7501, pp. 181\u2013192. Springer (2012)","DOI":"10.1007\/978-3-642-33090-2_17"},{"key":"9947_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.jda.2012.07.005","volume":"18","author":"D Belazzougui","year":"2013","unstructured":"Belazzougui, D., Navarro, G., Valenzuela, D.: Improved compressed indexes for full-text document retrieval. J. Discrete Algorithms 18, 3\u201313 (2013)","journal-title":"J. Discrete Algorithms"},{"key":"9947_CR5","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of LATIN, LNCS, vol. 1776, pp. 88\u201394. Springer (2000)","DOI":"10.1007\/10719839_9"},{"issue":"2","key":"9947_CR6","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"MA Bender","year":"2005","unstructured":"Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms 57(2), 75\u201394 (2005)","journal-title":"J. Algorithms"},{"issue":"24","key":"9947_CR7","doi-asserted-by":"crossref","first-page":"2588","DOI":"10.1016\/j.tcs.2010.05.003","volume":"412","author":"GS Brodal","year":"2011","unstructured":"Brodal, G.S., Gfeller, B., J\u00f8rgensen, A.G., Sanders, P.: Towards optimal range medians. Theor. Comput. Sci. 412(24), 2588\u20132601 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9947_CR8","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: Proceedings of STACS, vol. 14, pp. 291\u2013301 (2012)"},{"key":"9947_CR9","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. Theor. Comput. Syst. 55(4), 719\u2013741 (2014)","DOI":"10.1007\/s00224-013-9455-2"},{"key":"9947_CR10","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T.: Linear-space data structures for range minority query in arrays. In: Proceedings of SWAT, LNCS, vol. 7357, pp. 295\u2013306. Springer (2012)","DOI":"10.1007\/978-3-642-31155-0_26"},{"issue":"3","key":"9947_CR11","doi-asserted-by":"crossref","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. Comput. 15(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"key":"9947_CR12","doi-asserted-by":"crossref","unstructured":"Davoodi, P., Raman, R., Rao, S.S.: Succinct representations of binary trees for range minimum queries. In: Proceedings of COCOON, LNCS, vol. 7434, pp. 396\u2013407. Springer (2012)","DOI":"10.1007\/978-3-642-32241-9_34"},{"key":"9947_CR13","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On cartesian trees and range minimum queries. In: Proceedings of ICALP, LNCS, vol. 5555, pp. 341\u2013353. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_29"},{"key":"9947_CR14","doi-asserted-by":"crossref","unstructured":"Durocher, S.: A simple linear-space data structure for constant-time range minimum query. In: Proceedings of Conference on Space Efficient Data Structures, Streams and Algorithms (Munro Festschrift), vol. 8066, pp. 48\u201360 (2013)","DOI":"10.1007\/978-3-642-40273-9_5"},{"key":"9947_CR15","doi-asserted-by":"crossref","unstructured":"Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. In: Proceedings of ICALP, LNCS, vol. 6755, pp. 244\u2013255. Springer (2011)","DOI":"10.1007\/978-3-642-22006-7_21"},{"key":"9947_CR16","doi-asserted-by":"crossref","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. Comput. 222, 169\u2013179 (2013)","journal-title":"Inf. Comput."},{"key":"9947_CR17","doi-asserted-by":"crossref","unstructured":"Durocher, S., Munro, J.I., El-Zein, H., Thankachan, S.V.: Low space data structures for geometric range mode query. In: Proceedings of CCCG (2014)","DOI":"10.1016\/j.tcs.2015.03.011"},{"key":"9947_CR18","doi-asserted-by":"crossref","unstructured":"Durocher, S., Shah, R., Skala, M., Thankachan, S.: Linear-space data structures for range frequency queries on arrays and trees. In: Proceedings of MFCS, LNCS, vol. 8087, pp. 325\u2013336. Springer (2013)","DOI":"10.1007\/978-3-642-40313-2_30"},{"key":"9947_CR19","doi-asserted-by":"crossref","unstructured":"Durocher, S., Shah, R., Skala, M., Thankachan, S.: Top- $$k$$ k color queries on tree paths. In: Proceedings of SPIRE, LNCS, vol. 8214, pp. 109\u2013115. Springer (2013)","DOI":"10.1007\/978-3-319-02432-5_15"},{"issue":"3","key":"9947_CR20","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"PV Emde Boas","year":"1977","unstructured":"Emde Boas, P.V.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Proc. Lett. 6(3), 80\u201382 (1977)","journal-title":"Inf. Proc. Lett."},{"key":"9947_CR21","doi-asserted-by":"crossref","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: Proceedings of LATIN, LNCS, vol. 6034, pp. 158\u2013169. Springer (2010)","DOI":"10.1007\/978-3-642-12200-2_16"},{"issue":"3","key":"9947_CR22","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"ML Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48(3), 533\u2013551 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9947_CR23","doi-asserted-by":"crossref","unstructured":"Gagie, T., He, M., Munro, J.I., Nicholson, P.: Finding frequent elements in compressed 2D arrays and strings. In: Proceedings of SPIRE, LNCS, vol. 7024, pp. 295\u2013300. Springer (2011)","DOI":"10.1007\/978-3-642-24583-1_29"},{"key":"9947_CR24","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.tcs.2012.08.004","volume":"483","author":"T Gagie","year":"2013","unstructured":"Gagie, T., K\u00e4rkk\u00e4inen, J., Navarro, G., Puglisi, S.J.: Colored range queries and document retrieval. Theor. Comput. Sci. 483, 36\u201350 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"9947_CR25","doi-asserted-by":"crossref","unstructured":"Gagie, T., Puglisi, S.J., Turpin, A.: Range quantile queries: another virtue of wavelet trees. In: Proceedings of SPIRE, LNCS, vol. 5721, pp. 1\u20136. Springer (2009)","DOI":"10.1007\/978-3-642-03784-9_1"},{"key":"9947_CR26","doi-asserted-by":"crossref","unstructured":"Gfeller, B., Sanders, P.: Towards optimal range medians. In: Proceedings of ICALP, LNCS, vol. 5555, pp. 475\u2013486. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_40"},{"key":"9947_CR27","doi-asserted-by":"crossref","unstructured":"Hagerup, T., Tholey, T.: Efficient minimal perfect hashing in nearly minimal space. In: Proceedings of STACS, LNCS, vol. 2010, pp. 317\u2013326. Springer (2001)","DOI":"10.1007\/3-540-44693-1_28"},{"key":"9947_CR28","doi-asserted-by":"crossref","unstructured":"He, M., Munro, J.I., Zhou, G.: Path queries in weighted trees. In: Proceedings of ISAAC, pp. 140\u2013149 (2011)","DOI":"10.1007\/978-3-642-25591-5_16"},{"key":"9947_CR29","doi-asserted-by":"crossref","unstructured":"He, M., Munro, J.I., Zhou, G.: Succinct data structures for path queries. In: Proceedings of ESA, pp. 575\u2013586 (2012)","DOI":"10.1007\/978-3-642-33090-2_50"},{"key":"9947_CR30","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Shah, R., Vitter, J.S.: Space-efficient framework for top-k string retrieval problems. In: Proceedings of FOCS, pp. 713\u2013722 (2009)","DOI":"10.1109\/FOCS.2009.19"},{"key":"9947_CR31","doi-asserted-by":"crossref","unstructured":"J\u00f8rgensen, A.G., Larsen, K.D.: Range selection and median: tight cell probe lower bounds and adaptive data structures. In: Proceedings of SODA, pp. 805\u2013813 (2011)","DOI":"10.1137\/1.9781611973082.63"},{"key":"9947_CR32","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Nekrich, Y.: Top-k color queries for document retrieval. In: Proceedings of SODA, pp. 401\u2013411 (2011)","DOI":"10.1137\/1.9781611973082.32"},{"key":"9947_CR33","doi-asserted-by":"crossref","unstructured":"Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. In: Proceedings of ISAAC, LNCS, vol. 2906, pp. 517\u2013526. Springer (2003)","DOI":"10.1007\/978-3-540-24587-2_53"},{"key":"9947_CR34","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. Comput. 12, 1\u201317 (2005)","journal-title":"Nordic J. Comput."},{"key":"9947_CR35","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proceedings of SODA, pp. 657\u2013666 (2002)"},{"key":"9947_CR36","doi-asserted-by":"crossref","unstructured":"Navarro, G., Nekrich, Y.: Top- $$k$$ k document retrieval in optimal time and linear space. In: Proceedings of SODA, pp. 1066\u20131077 (2012)","DOI":"10.1137\/1.9781611973099.84"},{"key":"9947_CR37","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.jda.2012.08.003","volume":"17","author":"M Patil","year":"2012","unstructured":"Patil, M., Shah, R., Thankachan, S.V.: Succinct representations of weighted trees supporting path queries. J. Discrete Algorithms 17, 103\u2013108 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"9947_CR38","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proceedings of SODA, pp. 134\u2013149 (2010)","DOI":"10.1137\/1.9781611973075.13"},{"issue":"5","key":"9947_CR39","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"JP Schmidt","year":"1990","unstructured":"Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19(5), 775\u2013786 (1990)","journal-title":"SIAM J. Comput."},{"key":"9947_CR40","doi-asserted-by":"crossref","unstructured":"Skala, M.: Array range queries. In: Proceedings of Conference on Space Efficient Data Structures, Streams and Algorithms (Munro Festschrift), vol. 8066, pp. 333\u2013350 (2013)","DOI":"10.1007\/978-3-642-40273-9_21"},{"issue":"3","key":"9947_CR41","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9947-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9947-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9947-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T05:31:05Z","timestamp":1565933465000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9947-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,15]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9947"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9947-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,15]]}}}