{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:33:13Z","timestamp":1725744793922},"publisher-location":"Berlin, Heidelberg","reference-count":85,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642402722"},{"type":"electronic","value":"9783642402739"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40273-9_21","type":"book-chapter","created":{"date-parts":[[2013,8,9]],"date-time":"2013-08-09T21:20:34Z","timestamp":1376083234000},"page":"333-350","source":"Crossref","is-referenced-by-count":8,"title":["Array Range Queries"],"prefix":"10.1007","author":[{"given":"Matthew","family":"Skala","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","series-title":"Contemporary Mathematics","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/conm\/223\/03131","volume-title":"Advances in Discrete and Computational Geometry","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics, vol.\u00a0223, pp. 1\u201356. American Mathematical Society, Providence (1999)"},{"key":"21_CR2","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","year":"2009","unstructured":"Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.): ICALP 2009, Part I. LNCS, vol.\u00a05555. Springer, Heidelberg (2009)"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, California, USA, November 12-14, pp. 198\u2013207 (2000)","DOI":"10.1109\/SFCS.2000.892088"},{"key":"21_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/978-3-540-73437-6_29","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2007","unstructured":"Amir, A., Fischer, J., Lewenstein, M.: Two-dimensional range minimum queries. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 286\u2013294. Springer, Heidelberg (2007)"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Computation","year":"2011","unstructured":"Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.): ISAAC 2011. LNCS, vol.\u00a07074. Springer, Heidelberg (2011)"},{"key":"21_CR6","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":"21_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees (preliminary report). In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, April 25-27, pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"key":"21_CR8","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)"},{"key":"21_CR9","first-page":"196","volume-title":"Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1989","author":"O. Berkman","year":"1989","unstructured":"Berkman, O., Vishkin, U.: Recursive *-tree parallel data-structure. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1989, Research Triangle Park, NC, October 30-November 1, pp. 196\u2013202. IEEE Computer Society Press, Los Alamitos (1989)"},{"issue":"2","key":"21_CR10","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0222017","volume":"22","author":"O. Berkman","year":"1993","unstructured":"Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM J. Comput.\u00a022(2), 221\u2013242 (1993)","journal-title":"SIAM J. Comput."},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-03367-4_9","volume-title":"Algorithms and Data Structures","author":"P. Bose","year":"2009","unstructured":"Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct orthogonal range search structures on a grid with applications to text indexing. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 98\u2013109. Springer, Heidelberg (2009)"},{"key":"21_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/978-3-540-31856-9_31","volume-title":"STACS 2005","author":"P. Bose","year":"2005","unstructured":"Bose, P., Kranakis, E., Morin, P., Tang, Y.: Approximate range mode and range median queries. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 377\u2013388. Springer, Heidelberg (2005)"},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/3-540-60084-1_97","volume-title":"Automata, Languages and Programming","author":"P. Bozanis","year":"1995","unstructured":"Bozanis, P., Kitsios, N., Makris, C., Tsakalidis, A.: New upper bounds for generalized intersection searching problems. In: F\u00fcl\u00f6p, Z., G\u00e9cseg, F. (eds.) ICALP 1995. LNCS, vol.\u00a0944, pp. 464\u2013474. Springer, Heidelberg (1995)"},{"issue":"4","key":"21_CR14","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1007\/s00453-011-9499-0","volume":"63","author":"G.S. Brodal","year":"2012","unstructured":"Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica\u00a063(4), 815\u2013830 (2012)","journal-title":"Algorithmica"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Greve, M., L\u00f3pez-Ortiz, A.: Online sorted range reporting. In: [28], pp. 173\u2013182","DOI":"10.1007\/978-3-642-10631-6_19"},{"issue":"24","key":"21_CR16","doi-asserted-by":"publisher","first-page":"2588","DOI":"10.1016\/j.tcs.2010.05.003","volume":"412","author":"G.S. Brodal","year":"2011","unstructured":"Brodal, G.S., Gfeller, B., J\u00f8rgensen, A.G., Sanders, P.: Towards optimal range medians. Theoret. Comput. Sci.\u00a0412(24), 2588\u20132601 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., J\u00f8rgensen, A.G.: Data structures for range median queries. In: [28], pp. 822\u2013831","DOI":"10.1007\/978-3-642-10631-6_83"},{"key":"21_CR18","series-title":"IFIP","first-page":"103","volume-title":"TCS 2006","author":"A. Brodnik","year":"2006","unstructured":"Brodnik, A., Karlsson, J., Munro, J.I., Nilsson, A.: An O(1) solution to the prefix sum problem on a specialized memory architecture. In: Navarro, G., Bertossi, L.E., Kohayakawa, Y. (eds.) TCS 2006. IFIP, vol.\u00a0209, pp. 103\u2013114. Springer, Boston (2006)"},{"key":"21_CR19","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: D\u00fcrr, C., Wilke, T. (eds.) 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, Paris, France, February 29-March 3. LIPIcs, vol.\u00a014, pp. 290\u2013301. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"key":"21_CR20","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 Comput. Sys., 1\u201323 (2013)","DOI":"10.1007\/s00224-013-9455-2"},{"key":"21_CR21","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: [36], pp. 295\u2013306","DOI":"10.1007\/978-3-642-31155-0_26"},{"issue":"3","key":"21_CR22","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput.\u00a017(3), 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"21_CR23","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1142\/S0218195991000049","volume":"1","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B., Rosenberg, B.: The complexity of computing partial sums off-line. Internat. J. Comput. Geom. Appl.\u00a01(1), 33\u201345 (1991)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"21_CR24","unstructured":"Chun, S.J., Chung, C.W., Lee, J.H., Lee, S.L.: Dynamic update cube for range-sum queries. In: Apers, P.M.G., Atzeni, P., Ceri, S., Paraboschi, S., Ramamohanarao, K., Snodgrass, R.T. (eds.) Proceedings of the Twenty-seventh International Conference on Very Large Data Bases, Roma, Italy, September 11-14, pp. 521\u2013530. Morgan Kaufmann Publishers (2001)"},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/978-3-540-45078-8_40","volume-title":"Algorithms and Data Structures","author":"M. Berg de","year":"2003","unstructured":"de Berg, M., Haverkort, H.J.: Significant-presence range queries in categorical data. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 462\u2013473. Springer, Heidelberg (2003)"},{"key":"21_CR26","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian trees and range minimum queries. In: [2], pp. 341\u2013353","DOI":"10.1007\/978-3-642-02927-1_29"},{"issue":"3","key":"21_CR27","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(80)90057-2","volume":"12","author":"D. Dobkin","year":"1980","unstructured":"Dobkin, D., Munro, J.I.: Determining the mode. Theoret. Comput. Sci.\u00a012(3), 255\u2013263 (1980)","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR28","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Computation","year":"2009","unstructured":"Dong, Y., Du, D.-Z., Ibarra, O. (eds.): ISAAC 2009. LNCS, vol.\u00a05878. Springer, Heidelberg (2009)"},{"key":"21_CR29","doi-asserted-by":"crossref","unstructured":"Durocher, S.: A simple linear-space data structure for constant-time range minimum query. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Munro Festschrift 2013. LNCS, vol.\u00a08066, pp. 48\u201360. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-40273-9_5"},{"key":"21_CR30","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":"21_CR31","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. Inform. and Comput.\u00a0222, 169\u2013179 (2013)","journal-title":"Inform. and Comput."},{"key":"21_CR32","doi-asserted-by":"crossref","unstructured":"Elmasry, A., He, M., Munro, J.I., Nicholson, P.K.: Dynamic range majority data structures. In: [5], pp. 150\u2013159","DOI":"10.1007\/978-3-642-25591-5_17"},{"volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA 2002)","year":"2002","key":"21_CR33","unstructured":"Eppstein, D. (ed.): Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA 2002), January 6-8. ACM Press, New York (2002)"},{"key":"21_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-12200-2_16","volume-title":"LATIN 2010: Theoretical Informatics","author":"J. Fischer","year":"2010","unstructured":"Fischer, J.: Optimal succinctness for range minimum queries. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 158\u2013169. Springer, Heidelberg (2010)"},{"key":"21_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-3-540-74450-4_41","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"J. Fischer","year":"2007","unstructured":"Fischer, J., Heun, V.: A new succinct representation of RMQ-information and improvements in the enhanced suffix array. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol.\u00a04614, pp. 459\u2013470. Springer, Heidelberg (2007)"},{"key":"21_CR36","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithm Theory \u2013 SWAT 2012","year":"2012","unstructured":"Fomin, F.V., Kaski, P. (eds.): SWAT 2012. LNCS, vol.\u00a07357. Springer, Heidelberg (2012)"},{"issue":"1","key":"21_CR37","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1145\/322290.322305","volume":"29","author":"M.L. Fredman","year":"1982","unstructured":"Fredman, M.L.: The complexity of maintaining an array and computing its partial sums. J. ACM\u00a029(1), 250\u2013260 (1982)","journal-title":"J. ACM"},{"key":"21_CR38","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, April 30-May 2, pp. 135\u2013143. ACM Press, Washington, DC (1984)","DOI":"10.1145\/800057.808675"},{"key":"21_CR39","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":"21_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-642-21458-5_18","volume-title":"Combinatorial Pattern Matching","author":"T. Gagie","year":"2011","unstructured":"Gagie, T., K\u00e4rkk\u00e4inen, J.: Counting colours in compressed strings. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 197\u2013207. Springer, Heidelberg (2011)"},{"key":"21_CR41","doi-asserted-by":"publisher","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. Theoret. Comput. Sci.\u00a0483, 36\u201350 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-642-16321-0_7","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2010","unstructured":"Gagie, T., Navarro, G., Puglisi, S.J.: Colored range queries and document retrieval. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 67\u201381. Springer, Heidelberg (2010)"},{"key":"21_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-03784-9_1","volume-title":"String Processing and Information Retrieval","author":"T. Gagie","year":"2009","unstructured":"Gagie, T., Puglisi, S.J., Turpin, A.: Range quantile queries: Another virtue of wavelet trees. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 1\u20136. Springer, Heidelberg (2009)"},{"key":"21_CR44","doi-asserted-by":"crossref","unstructured":"Geffner, S., Agrawal, D., Abbadi, A.E., Smith, T.R.: Relative prefix sums: An efficient approach for querying dynamic OLAP data cubes. In: Kitsuregawa, M., Papazoglou, M.P., Pu, C. (eds.) Proceedings of the 15th International Conference on Data Engineering, Sydney, Austrialia, March 23-26, pp. 328\u2013335. IEEE Computer Society (1999)","DOI":"10.1109\/ICDE.1999.754948"},{"key":"21_CR45","doi-asserted-by":"crossref","unstructured":"Gfeller, B., Sanders, P.: Towards optimal range medians. In: [2], pp. 475\u2013486","DOI":"10.1007\/978-3-642-02927-1_40"},{"issue":"3","key":"21_CR46","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.tcs.2007.07.041","volume":"387","author":"A. Golynski","year":"2007","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. Theoret. Comput. Sci.\u00a0387(3), 348\u2013359 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/978-3-642-14165-2_51","volume-title":"Automata, Languages and Programming","author":"M. Greve","year":"2010","unstructured":"Greve, M., J\u00f8rgensen, A.G., Larsen, K.D., Truelsen, J.: Cell probe lower bounds and approximations for range mode. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 605\u2013616. Springer, Heidelberg (2010)"},{"key":"21_CR48","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: SODA: ACM-SIAM Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms), pp. 841\u2013850. ACM\/SIAM (2003)"},{"issue":"2","key":"21_CR49","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1006\/jagm.1995.1038","volume":"19","author":"P. Gupta","year":"1995","unstructured":"Gupta, P., Janardan, R., Smid, M.: Further results on generalized intersection searching problems: Counting, reporting, and dynamization. J. Algorithms\u00a019(2), 282\u2013317 (1995)","journal-title":"J. Algorithms"},{"issue":"1","key":"21_CR50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539795291598","volume":"28","author":"H. Hampapuram","year":"1998","unstructured":"Hampapuram, H., Fredman, M.L.: Optimal biweighted binary trees and the complexity of maintaining partial sums. SIAM J. Comput.\u00a028(1), 1\u20139 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"21_CR51","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"key":"21_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/978-3-642-22300-6_42","volume-title":"Algorithms and Data Structures","author":"M. He","year":"2011","unstructured":"He, M., Munro, J.I.: Space efficient data structures for dynamic orthogonal range counting. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol.\u00a06844, pp. 500\u2013511. Springer, Heidelberg (2011)"},{"key":"21_CR53","doi-asserted-by":"crossref","unstructured":"He, M., Munro, J.I., Nicholson, P.K.: Dynamic range selection in linear space. In: [5], pp. 160\u2013169","DOI":"10.1007\/978-3-642-25591-5_18"},{"key":"21_CR54","unstructured":"He, M., Munro, J.I., Nicholson, P.K.: Dynamic range selection in linear space. CoRR abs\/1106.5076v3 (2013), http:\/\/arxiv.org\/abs\/1106.5076v3"},{"key":"21_CR55","doi-asserted-by":"crossref","unstructured":"He, M., Munro, J.I., Zhou, G.: Path queries in weighted trees. In: [5], pp. 140\u2013149","DOI":"10.1007\/978-3-642-25591-5_16"},{"key":"21_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/978-3-642-33090-2_50","volume-title":"Algorithms \u2013 ESA 2012","author":"M. He","year":"2012","unstructured":"He, M., Munro, J.I., Zhou, G.: Succinct data structures for path queries. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol.\u00a07501, pp. 575\u2013586. Springer, Heidelberg (2012)"},{"key":"21_CR57","doi-asserted-by":"crossref","unstructured":"Ho, C.T., Agrawal, R., Megiddo, N., Srikant, R.: Range queries in OLAP data cubes. In: Peckman, J.M. (ed.) Proceedings, ACM SIGMOD International Conference on Management of Data: SIGMOD 1997, Tucson, Arizona, USA, May 13-15. SIGMOD Record (ACM Special Interest Group on Management of Data), vol.\u00a026(2), pp. 73\u201388. ACM Press (1997)","DOI":"10.1145\/253260.253274"},{"key":"21_CR58","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Shah, R., Thankachan, S.V.: Towards an optimal space-and-query-time index for top-k document retrieval. In: [64], pp. 173\u2013184","DOI":"10.1007\/978-3-642-31265-6_14"},{"key":"21_CR59","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Shah, R., Vitter, J.S.: Space-efficient framework for top-k string retrieval problems. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, Atlanta, Georgia, USA, October 25-27, pp. 713\u2013722. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.19"},{"key":"21_CR60","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: 30th Annual Symp. on Foundations of Computer Science, vol.\u00a030, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"21_CR61","unstructured":"Jacobson, G.: Succinct Static Data Structures. PhD thesis, Carnegie-Mellon, Technical Report CMU-CS-89-112 (January 1989)"},{"issue":"1","key":"21_CR62","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1142\/S021819599300004X","volume":"3","author":"R. Janardan","year":"1993","unstructured":"Janardan, R., Lopez, M.: Generalized intersection searching problems. Internat. J. Comput. Geom. Appl.\u00a03(1), 39\u201369 (1993)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"21_CR63","unstructured":"J\u00f8rgensen, A.G., Larsen, K.G.: Range selection and median: Tight cell probe lower bounds and adaptive data structures. In: [83], pp. 805\u2013813"},{"key":"21_CR64","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Pattern Matching","year":"2012","unstructured":"K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.): CPM 2012. LNCS, vol.\u00a07354. Springer, Heidelberg (2012)"},{"key":"21_CR65","unstructured":"Karpinski, M., Nekrich, Y.: Searching for frequent colors in rectangles. In: Proceedings of the 20th Annual Canadian Conference on Computational Geometry, Montr\u00e9al, Canada, August 13-15 (2008)"},{"key":"21_CR66","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Nekrich, Y.: Top-k color queries for document retrieval. In: [83], pp. 401\u2013411","DOI":"10.1137\/1.9781611973082.32"},{"key":"21_CR67","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)"},{"issue":"1","key":"21_CR68","first-page":"1","volume":"12","author":"D. Krizanc","year":"2005","unstructured":"Krizanc, D., Morin, P., Smid, M.H.M.: Range mode and range median queries on lists and trees. Nord. J. Comput.\u00a012(1), 1\u201317 (2005)","journal-title":"Nord. J. Comput."},{"issue":"3","key":"21_CR69","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.jda.2007.10.001","volume":"6","author":"Y. Lai","year":"2008","unstructured":"Lai, Y., Poon, C., Shi, B.: Approximate colored range and point enclosure queries. J. Discrete Algorithms\u00a06(3), 420\u2013432 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"21_CR70","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.tcs.2007.07.013","volume":"387","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Rank and select revisited and extended. Theoret. Comput. Sci.\u00a0387(3), 332\u2013347 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"21_CR71","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0205001","volume":"5","author":"J.I. Munro","year":"1976","unstructured":"Munro, J.I., Spira, P.M.: Sorting and searching in multisets. SIAM J. Comput.\u00a05(1), 1\u20138 (1976)","journal-title":"SIAM J. Comput."},{"key":"21_CR72","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"J.I. Munro","year":"1996","unstructured":"Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol.\u00a01180, pp. 37\u201342. Springer, Heidelberg (1996)"},{"key":"21_CR73","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: [33], pp. 657\u2013666"},{"key":"21_CR74","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Wavelet trees for all. In: [64], pp. 2\u201326","DOI":"10.1007\/978-3-642-31265-6_2"},{"key":"21_CR75","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-540-73951-7_3","volume-title":"Algorithms and Data Structures","author":"Y. Nekrich","year":"2007","unstructured":"Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 15\u201326. Springer, Heidelberg (2007)"},{"issue":"4","key":"21_CR76","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":"21_CR77","doi-asserted-by":"crossref","unstructured":"Nekrich, Y., Navarro, G.: Sorted range reporting. In: [36], pp. 271\u2013282","DOI":"10.1007\/978-3-642-31155-0_24"},{"key":"21_CR78","doi-asserted-by":"publisher","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\u00a017, 103\u2013108 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"21_CR79","doi-asserted-by":"crossref","unstructured":"Patrascu, M.: Succincter. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, Pennsylvania, USA, October 25-23, pp. 305\u2013313. IEEE (2008)","DOI":"10.1109\/FOCS.2008.83"},{"key":"21_CR80","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/978-3-540-77566-9_36","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"H. Petersen","year":"2008","unstructured":"Petersen, H.: Improved bounds for range mode and range median queries. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 418\u2013423. Springer, Heidelberg (2008)"},{"issue":"4","key":"21_CR81","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.ipl.2008.10.007","volume":"109","author":"H. Petersen","year":"2009","unstructured":"Petersen, H., Grabowski, S.: Range mode and range median queries in constant time and sub-quadratic space. Inf. Process. Lett.\u00a0109(4), 225\u2013228 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"21_CR82","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/S0304-3975(02)00741-7","volume":"296","author":"C.K. Poon","year":"2003","unstructured":"Poon, C.K.: Dynamic orthogonal range queries in OLAP. Theoret. Comput. Sci.\u00a0296(3), 487\u2013510 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR83","doi-asserted-by":"crossref","unstructured":"Randall, D. (ed.): Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25. SIAM (2011)","DOI":"10.1137\/1.9781611973082"},{"key":"21_CR84","unstructured":"Sadakane, K.: Succinct representations of lcp information and improvements in the compressed suffix arrays. In: [35], pp. 225\u2013232"},{"issue":"2","key":"21_CR85","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"A.C.C. Yao","year":"1985","unstructured":"Yao, A.C.C.: On the complexity of maintaining partial sums. SIAM J. Comput.\u00a014(2), 277\u2013288 (1985)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Space-Efficient Data Structures, Streams, and Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40273-9_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T15:32:00Z","timestamp":1563636720000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40273-9_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642402722","9783642402739"],"references-count":85,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40273-9_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}