Abstract
Array range queries are of current interest in the field of data structures. Given an array of numbers or arbitrary elements, the general array range query problem is to build a data structure that can efficiently answer queries of a given type stated in terms of an interval of the indices. The specific query type might be for the minimum element in the range, the most frequently occurring element, or any of many other possibilities. In addition to being interesting in themselves, array range queries have connections to computational geometry, compressed and succinct data structures, and other areas of computer science. We survey recent and relevant past work on this class of problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
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. 223, pp. 1–56. American Mathematical Society, Providence (1999)
Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.): ICALP 2009, Part I. LNCS, vol. 5555. Springer, Heidelberg (2009)
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–207 (2000)
Amir, A., Fischer, J., Lewenstein, M.: Two-dimensional range minimum queries. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 286–294. Springer, Heidelberg (2007)
Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.): ISAAC 2011. LNCS, vol. 7074. Springer, Heidelberg (2011)
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. 8037, pp. 121–132. Springer, Heidelberg (2013)
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–86 (1983)
Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88–94. Springer, Heidelberg (2000)
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–202. IEEE Computer Society Press, Los Alamitos (1989)
Berkman, O., Vishkin, U.: Recursive star-tree parallel data structure. SIAM J. Comput. 22(2), 221–242 (1993)
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óth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 98–109. Springer, Heidelberg (2009)
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. 3404, pp. 377–388. Springer, Heidelberg (2005)
Bozanis, P., Kitsios, N., Makris, C., Tsakalidis, A.: New upper bounds for generalized intersection searching problems. In: Fülöp, Z., Gécseg, F. (eds.) ICALP 1995. LNCS, vol. 944, pp. 464–474. Springer, Heidelberg (1995)
Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica 63(4), 815–830 (2012)
Brodal, G.S., Fagerberg, R., Greve, M., López-Ortiz, A.: Online sorted range reporting. In: [28], pp. 173–182
Brodal, G.S., Gfeller, B., Jørgensen, A.G., Sanders, P.: Towards optimal range medians. Theoret. Comput. Sci. 412(24), 2588–2601 (2011)
Brodal, G.S., Jørgensen, A.G.: Data structures for range median queries. In: [28], pp. 822–831
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. 209, pp. 103–114. Springer, Boston (2006)
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ürr, C., Wilke, T. (eds.) 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, Paris, France, February 29-March 3. LIPIcs, vol. 14, pp. 290–301. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)
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–23 (2013)
Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T.: Linear-space data structures for range minority query in arrays. In: [36], pp. 295–306
Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3), 427–462 (1988)
Chazelle, B., Rosenberg, B.: The complexity of computing partial sums off-line. Internat. J. Comput. Geom. Appl. 1(1), 33–45 (1991)
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–530. Morgan Kaufmann Publishers (2001)
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. 2748, pp. 462–473. Springer, Heidelberg (2003)
Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian trees and range minimum queries. In: [2], pp. 341–353
Dobkin, D., Munro, J.I.: Determining the mode. Theoret. Comput. Sci. 12(3), 255–263 (1980)
Dong, Y., Du, D.-Z., Ibarra, O. (eds.): ISAAC 2009. LNCS, vol. 5878. Springer, Heidelberg (2009)
Durocher, S.: A simple linear-space data structure for constant-time range minimum query. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds.) Munro Festschrift 2013. LNCS, vol. 8066, pp. 48–60. Springer, Heidelberg (2013)
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. 6755, pp. 244–255. Springer, Heidelberg (2011)
Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. Inform. and Comput. 222, 169–179 (2013)
Elmasry, A., He, M., Munro, J.I., Nicholson, P.K.: Dynamic range majority data structures. In: [5], pp. 150–159
Eppstein, D. (ed.): Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA 2002), January 6-8. ACM Press, New York (2002)
Fischer, J.: Optimal succinctness for range minimum queries. In: López-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 158–169. Springer, Heidelberg (2010)
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. 4614, pp. 459–470. Springer, Heidelberg (2007)
Fomin, F.V., Kaski, P. (eds.): SWAT 2012. LNCS, vol. 7357. Springer, Heidelberg (2012)
Fredman, M.L.: The complexity of maintaining an array and computing its partial sums. J. ACM 29(1), 250–260 (1982)
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–143. ACM Press, Washington, DC (1984)
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. 7024, pp. 295–300. Springer, Heidelberg (2011)
Gagie, T., Kärkkäinen, J.: Counting colours in compressed strings. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 197–207. Springer, Heidelberg (2011)
Gagie, T., Kärkkäinen, J., Navarro, G., Puglisi, S.J.: Colored range queries and document retrieval. Theoret. Comput. Sci. 483, 36–50 (2013)
Gagie, T., Navarro, G., Puglisi, S.J.: Colored range queries and document retrieval. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 67–81. Springer, Heidelberg (2010)
Gagie, T., Puglisi, S.J., Turpin, A.: Range quantile queries: Another virtue of wavelet trees. In: Karlgren, J., Tarhio, J., Hyyrö, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 1–6. Springer, Heidelberg (2009)
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–335. IEEE Computer Society (1999)
Gfeller, B., Sanders, P.: Towards optimal range medians. In: [2], pp. 475–486
Golynski, A.: Optimal lower bounds for rank and select indexes. Theoret. Comput. Sci. 387(3), 348–359 (2007)
Greve, M., Jørgensen, 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. 6198, pp. 605–616. Springer, Heidelberg (2010)
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–850. ACM/SIAM (2003)
Gupta, P., Janardan, R., Smid, M.: Further results on generalized intersection searching problems: Counting, reporting, and dynamization. J. Algorithms 19(2), 282–317 (1995)
Hampapuram, H., Fredman, M.L.: Optimal biweighted binary trees and the complexity of maintaining partial sums. SIAM J. Comput. 28(1), 1–9 (1998)
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338–355 (1984)
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. 6844, pp. 500–511. Springer, Heidelberg (2011)
He, M., Munro, J.I., Nicholson, P.K.: Dynamic range selection in linear space. In: [5], pp. 160–169
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
He, M., Munro, J.I., Zhou, G.: Path queries in weighted trees. In: [5], pp. 140–149
He, M., Munro, J.I., Zhou, G.: Succinct data structures for path queries. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 575–586. Springer, Heidelberg (2012)
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. 26(2), pp. 73–88. ACM Press (1997)
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–184
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–722. IEEE Computer Society (2009)
Jacobson, G.: Space-efficient static trees and graphs. In: 30th Annual Symp. on Foundations of Computer Science, vol. 30, pp. 549–554 (1989)
Jacobson, G.: Succinct Static Data Structures. PhD thesis, Carnegie-Mellon, Technical Report CMU-CS-89-112 (January 1989)
Janardan, R., Lopez, M.: Generalized intersection searching problems. Internat. J. Comput. Geom. Appl. 3(1), 39–69 (1993)
Jørgensen, A.G., Larsen, K.G.: Range selection and median: Tight cell probe lower bounds and adaptive data structures. In: [83], pp. 805–813
Kärkkäinen, J., Stoye, J. (eds.): CPM 2012. LNCS, vol. 7354. Springer, Heidelberg (2012)
Karpinski, M., Nekrich, Y.: Searching for frequent colors in rectangles. In: Proceedings of the 20th Annual Canadian Conference on Computational Geometry, Montréal, Canada, August 13-15 (2008)
Karpinski, M., Nekrich, Y.: Top-k color queries for document retrieval. In: [83], pp. 401–411
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. 2906, pp. 517–526. Springer, Heidelberg (2003)
Krizanc, D., Morin, P., Smid, M.H.M.: Range mode and range median queries on lists and trees. Nord. J. Comput. 12(1), 1–17 (2005)
Lai, Y., Poon, C., Shi, B.: Approximate colored range and point enclosure queries. J. Discrete Algorithms 6(3), 420–432 (2008)
Mäkinen, V., Navarro, G.: Rank and select revisited and extended. Theoret. Comput. Sci. 387(3), 332–347 (2007)
Munro, J.I., Spira, P.M.: Sorting and searching in multisets. SIAM J. Comput. 5(1), 1–8 (1976)
Munro, J.I.: Tables. In: Chandru, V., Vinay, V. (eds.) FSTTCS 1996. LNCS, vol. 1180, pp. 37–42. Springer, Heidelberg (1996)
Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: [33], pp. 657–666
Navarro, G.: Wavelet trees for all. In: [64], pp. 2–26
Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 15–26. Springer, Heidelberg (2007)
Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. Comput. Geom. 42(4), 342–351 (2009)
Nekrich, Y., Navarro, G.: Sorted range reporting. In: [36], pp. 271–282
Patil, M., Shah, R., Thankachan, S.V.: Succinct representations of weighted trees supporting path queries. J. Discrete Algorithms 17, 103–108 (2012)
Patrascu, M.: Succincter. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, Pennsylvania, USA, October 25-23, pp. 305–313. IEEE (2008)
Petersen, H.: Improved bounds for range mode and range median queries. In: Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P., Bieliková, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 418–423. Springer, Heidelberg (2008)
Petersen, H., Grabowski, S.: Range mode and range median queries in constant time and sub-quadratic space. Inf. Process. Lett. 109(4), 225–228 (2009)
Poon, C.K.: Dynamic orthogonal range queries in OLAP. Theoret. Comput. Sci. 296(3), 487–510 (2003)
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)
Sadakane, K.: Succinct representations of lcp information and improvements in the compressed suffix arrays. In: [35], pp. 225–232
Yao, A.C.C.: On the complexity of maintaining partial sums. SIAM J. Comput. 14(2), 277–288 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Skala, M. (2013). Array Range Queries. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds) Space-Efficient Data Structures, Streams, and Algorithms. Lecture Notes in Computer Science, vol 8066. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40273-9_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-40273-9_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40272-2
Online ISBN: 978-3-642-40273-9
eBook Packages: Computer ScienceComputer Science (R0)