Abstract
We consider encoding problems for range queries on arrays. In these problems the goal is to store a structure capable of recovering the answer to all queries that occupies the information theoretic minimum space possible, to within lower order terms. As input, we are given an array \(A[1..n]\), and a fixed parameter \(k \in [1,n]\). A range top- \(k\) query on an arbitrary range \([i,j] \subseteq [1,n]\) asks us to return the ordered set of indices \(\{\ell _1, ..., \ell _{k}\}\) such that \(A[\ell _m]\) is the \(m\)-th largest element in \(A[i..j]\), for \(1 \le m \le k\). A range selection query for an arbitrary range \([i,j] \subseteq [1,n]\) and query parameter \(k' \in [1,k]\) asks us to return the index of the \(k'\)-th largest element in \(A[i..j]\). We completely resolve the space complexity of both of these heavily studied problems—to within lower order terms—for all \(k = o(n)\). Previously, the constant factor in the space complexity was known only for \(k=1\). We also resolve the space complexity of another problem, that we call range min-max, in which the goal is to return the indices of both the minimum and maximum elements in a range.
P. Gawrychowski—Currently holding a post-doctoral position at Warsaw Center of Mathematics and Computer Science.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, Number of Baxter permutations of length \(n\) (2011). http://oeis.org/A001181 (Accessed 24 September 2014)
Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. Journal of Algorithms 57(2), 75–94 (2005)
Brodal, G.S., Gfeller, B., Jørgensen, A.G., Sanders, P.: Towards optimal range medians. Theoretical Computer Science 412(24), 2588–2601 (2011)
Chan, T.M., Wilkinson, B.T.: Adaptive and approximate orthogonal range counting. In: Proc. of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 241–251. SIAM (2013)
Davoodi, P., Navarro, G., Raman, R., Rao, S.: Encoding Range Minima and Range Top-2 Queries. Phil. Trans. R. Soc. A 372(2016), 1471–2962 (2014)
Dvoretzky, A., Motzkin, T.: A problem of arrangements. Duke Mathematical Journal 14(2), 305–313 (1947)
Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465–492 (2011)
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)
Gawrychowski, P., Nicholson, P.K.: Optimal Encodings for Range Min-Max and Top-k. CoRR abs/1411.6581 (2014). http://arxiv.org/abs/1411.6581
Grossi, R., Iacono, J., Navarro, G., Raman, R., Rao, S.S.: Encodings for range selection and top-k queries. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 553–564. Springer, Heidelberg (2013)
Jacobson, G.: Space-efficient static trees and graphs. In: Proc. of the 30th Annual Symposium on Foundations of Computer Science, pp. 549–554. IEEE (1989)
Jørgensen, A.G., Larsen, K.G.: Range selection and median: tight cell probe lower bounds and adaptive data structures. In: Proc. of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 805–813. SIAM (2011)
Matoušek, J.: Reporting points in halfspaces. Computational Geometry 2(3), 169–186 (1992)
Navarro, G.: Spaces, trees, and colors: The algorithmic landscape of document retrieval on sequences. ACM Comput. Surv. 46(4), 52 (2013)
Navarro, G., Raman, R., Satti, S.R.: asymptotically optimal encodings for range selection. In: Proc. 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs, vol. 29, pp. 291–301. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014)
Sadakane, K.: Succinct data structures for flexible text retrieval systems. Journal of Discrete Algorithms 5(1), 12–22 (2007)
Skala, M.: Array range queries. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 333–350. Springer, Heidelberg (2013)
Vuillemin, J.: A unifying look at data structures. Communications of the ACM 23(4), 229–239 (1980)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gawrychowski, P., Nicholson, P.K. (2015). Optimal Encodings for Range Top-\(k\), Selection, and Min-Max. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_48
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_48
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)