zbMATH — the first resource for mathematics

On space efficient two dimensional range minimum data structures. (English) Zbl 1254.68093
Summary: The two dimensional range minimum query problem is to preprocess a static $$m$$ by $$n$$ matrix (two dimensional array) $$A$$ of size $$N=m\cdot n$$, such that subsequent queries, asking for the position of the minimum element in a rectangular range within $$A$$, can be answered efficiently.
We study the trade-off between the space and query time of the problem. We show that every algorithm enabled to access $$A$$ during the query and using a data structure of size $$O(N/c)$$ bits requires $$\Omega (c)$$ query time, for any $$c$$ where $$1\leq c\leq N$$. This lower bound holds for arrays of any dimension. In particular, for the one dimensional version of the problem, the lower bound is tight up to a constant factor.
In two dimensions, we complement the lower bound with an indexing data structure of size $$O(N/c)$$ bits which can be preprocessed in $$O(N)$$ time to support $$O(c \log^2c)$$ query time. For $$c=O(1)$$, this is the first $$O(1)$$ query time algorithm using a data structure of optimal size $$O(N)$$ bits. For the case where queries can not probe $$A$$, we give a data structure of size $$O(N\cdot \mathrm{min}\, {m,\log n})$$ bits with $$O(1)$$ query time, assuming $$m\leq n$$. This leaves a gap to the space lower bound of $$\Omega (N \log m)$$ bits for this version of the problem.

MSC:
 68P05 Data structures 05C05 Trees 68R10 Graph theory (including graph drawing) in computer science
Full Text:
References:
 [1] Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms 2(1), 53–86 (2004) · Zbl 1115.92303 · doi:10.1016/S1570-8667(03)00065-0 [2] Aho, A., Hopcroft, J., Ullman, J.: On finding lowest common ancestors in trees. In: Proc. 5th Annual ACM Symposium on Theory of Computing, pp. 253–265. ACM, New York (1973) · Zbl 0305.68030 [3] Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: a survey and a new distributed algorithm. In: Proc. 14th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 258–264. ACM, New York (2002) · Zbl 1093.68136 [4] Amir, A., Fischer, J., Lewenstein, M.: Two-dimensional range minimum queries. In: Proc. 18th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 4580, pp. 286–294. Springer, Berlin (2007) · Zbl 1138.68654 [5] Atallah, M.J., Yuan, H.: Data structures for range minimum queries in multidimensional arrays. In: Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 150–160. SIAM, Philadelphia (2010) · Zbl 1288.68055 [6] Bender, M., Farach-Colton, M.: The LCA problem revisited. In: Proc. 4th Latin American Theoretical Informatics Symposium. Lecture Notes in Computer Science, vol. 1776, pp. 88–94. Springer, Berlin (2000) · Zbl 0959.68133 [7] 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–94 (2005) · Zbl 1085.68103 · doi:10.1016/j.jalgor.2005.08.001 [8] Bentley, J.L.: Decomposable searching problems. Inf. Process. Lett. 8(5), 244–251 (1979) · Zbl 0404.68067 · doi:10.1016/0020-0190(79)90117-0 [9] Berkman, O., Galil, Z., Schieber, B., Vishkin, U.: Highly parallelizable problems. In: Proc. 21st Annual ACM Symposium on Theory of Computing, pp. 309–319. ACM, New York (1989) [10] Chazelle, B., Rosenberg, B.: Computing partial sums in multidimensional arrays. In: Proc. 5th Annual Symposium on Computational Geometry, pp. 131–139. ACM, New York (1989) [11] Chen, G., Puglisi, S.J., Smyth, W.F.: Lempel-Ziv factorization using less time and space. Math. Comput. Sci. 1, 605–623 (2008) · Zbl 1181.68315 · doi:10.1007/s11786-007-0024-4 [12] Demaine, E.D., Landau, G.M., Weimann, O.: On Cartesian trees and range minimum queries. In: Proc. 36th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 5555, pp. 341–353. Springer, Berlin (2009) · Zbl 1248.68165 [13] Fischer, J.: Optimal succinctness for range minimum queries. In: Proc. 9th Latin American Theoretical Informatics Symposium. Lecture Notes in Computer Science, vol. 6034, pp. 158–169. Springer, Berlin (2010) · Zbl 1283.68141 [14] Fischer, J., Heun, V.: Theoretical and practical improvements on the rmq-problem, with applications to lca and lce. In: Proc. 17th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 4009, pp. 36–48. Springer, Berlin (2006) · Zbl 1196.68068 [15] Fischer, J., Heun, V.: A new succinct representation of rmq-information and improvements in the enhanced suffix array. In: Proc. 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. Lecture Notes in Computer Science, vol. 4614, pp. 459–470. Springer, Berlin (2007) · Zbl 1176.68058 [16] Fischer, J., Mäkinen, V., Navarro, G.: An(other) entropy-bounded compressed suffix tree. In: Proc. 19th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 5029, pp. 152–165. Springer, Berlin (2008) · Zbl 1143.68382 [17] Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th Annual ACM Symposium on Theory of Computing, pp. 135–143. ACM, New York (1984) [18] Gál, A., Miltersen, P.B.: The cell probe complexity of succinct data structures. Theor. Comput. Sci. 379(3), 405–417 (2007) · Zbl 1152.68428 · doi:10.1016/j.tcs.2007.02.047 [19] Georgiadis, L., Tarjan, R.E.: Finding dominators revisited: extended abstract. In: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 869–878. SIAM, Philadelphia (2004) · Zbl 1318.68188 [20] Golynski, A.: Optimal lower bounds for rank and select indexes. Theor. Comput. Sci. 387(3), 348–359 (2007) · Zbl 1144.68016 · doi:10.1016/j.tcs.2007.07.041 [21] Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338–355 (1984) · Zbl 0535.68022 · doi:10.1137/0213024 [22] Iliopoulos, C.S., Crochemore, M., Kubica, M., Rahman, M.S., Walen, T.: Improved algorithms for the range next value problem and applications. In: Proc. 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics, vol. 1, pp. 205–216. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Leibniz (2008) · Zbl 1259.68226 [23] Miltersen, P.B.: Cell probe complexity–a survey. Advances in Data Structures Workshop (Pre-conference Workshop of Foundations of Software Technology and Theoretical Computer Science) (1999). http://www.daimi.au.dk/$$\sim$$bromille/Papers/survey3.ps [24] Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 657–666. SIAM, Philadelphia (2002) · Zbl 1093.68588 [25] Poon, C.K.: Dynamic orthogonal range queries in OLAP. Theory Comput. Syst. 296(3), 487–510 (2003) · Zbl 1045.68042 · doi:10.1016/S0304-3975(02)00741-7 [26] Sadakane, K.: Compressed suffix trees with full functionality. Theory Comput. Syst. 41(4), 589–607 (2007) · Zbl 1148.68015 · doi:10.1007/s00224-006-1198-x [27] Sadakane, K.: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithms 5(1), 12–22 (2007) · Zbl 1137.68360 · doi:10.1016/j.jda.2006.03.011 [28] Saxena, S.: Dominance made simple. Inf. Process. Lett. 109(9), 419–421 (2009) · Zbl 1209.68590 · doi:10.1016/j.ipl.2008.12.006 [29] Schieber, B., Vishkin, U.: On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput. 17(6), 1253–1262 (1988) · Zbl 0669.68049 · doi:10.1137/0217079 [30] Välimäki, N., Mäkinen, V.: Space-efficient algorithms for document retrieval. In: Proc. 18th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 4580, pp. 205–215. Springer, Berlin (2007) · Zbl 1138.68401 [31] Vuillemin, J.: A unifying look at data structures. Commun. ACM 23(4), 229–239 (1980) · Zbl 0434.68047 · doi:10.1145/358841.358852
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.