×

zbMATH — the first resource for mathematics

Succinct indices for path minimum, with applications. (English) Zbl 1369.68167
Summary: In the path minimum problem, we preprocess a tree on \(n\) weighted nodes, such that given an arbitrary path, the node with the smallest weight along this path can be located. We design novel succinct indices for this problem under the indexing model, for which weights of nodes are read-only and can be accessed with ranks of nodes in the preorder traversal sequence of the input tree. We present
\(\bullet\)
an index within \(O(m)\) bits of additional space that supports queries in \(O(\boldsymbol{\alpha}(m, n))\) time and \(O(\boldsymbol{\alpha}(m, n))\) accesses to the weights of nodes, for any integer \(m \geq n\); and
\(\bullet\)
an index within \(2n + o(n)\) bits of additional space that supports queries in \(O(\boldsymbol{\alpha}(n))\) time and \(O(\boldsymbol{\alpha}(n))\) accesses to the weights of nodes.
Here \(\boldsymbol{\alpha}(m, n)\) is the inverse-Ackermann function, and \(\boldsymbol{\alpha}(n) = \boldsymbol{\alpha}(n, n)\). These indices give us the first succinct data structures for the path minimum problem. Following the same approach, we also develop succinct data structures for semigroup path sum queries, for which a query asks for the sum of weights along a given query path. One of our data structures requires \(n\lg \sigma + 2n + o(n\lg \sigma )\) bits of space and \(O(\boldsymbol{\alpha}(n))\) query time, where \(\sigma \) is the size of the semigroup. In the path reporting problem, queries ask for the nodes along a query path whose weights are within a two-sided query range. Using the succinct indices for path minimum queries, we achieve three different time/space tradeoffs for path reporting by designing
\(\bullet\)
an \(O(n)\)-word data structure with \(O(\lg ^\epsilon n + \mathrm{occ} \cdot \lg ^\epsilon n)\) query time;
\(\bullet\)
an \(O(n\lg \lg n)\)-word data structure with \(O(\lg \lg n + \mathrm{occ} \cdot \lg \lg n)\) query time; and
\(\bullet\)
an \(O(n \lg ^\epsilon n)\)-word data structure with \(O(\lg \lg n + \mathrm{occ})\) query time.
Here \(\mathrm{occ}\) is the number of nodes reported and \(\epsilon \) is an arbitrary constant between 0 and 1. These tradeoffs match the state of the art of two-dimensional orthogonal range reporting queries [the first author et al., in: Proceedings of the 27th annual symposium on computational geometry, SoCG’11. New York, NY: Association for Computing Machinery (ACM). 1–10 (2011; Zbl 1283.68139)], which can be treated as a special case of path reporting queries. When the number of distinct weights is much smaller than \(n\), we further improve both the query time and the space cost of these three results.

MSC:
68P05 Data structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N., Schieber, B.: Optimal preprocessing for answering on-line product queries. Technical report, Tel Aviv University, (1987) · Zbl 0434.68047
[2] Alstrup, S., Brodal, G.S., Rauhe, T.: Optimal static range reporting in one dimension. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, STOC 2001, Heraklion, Crete, Greece, 6-8 July 2001, pp. 476-482, (2001) · Zbl 1323.68536
[3] Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Automata, Languages and Programming, 27th International Colloquium, ICALP 2000, Geneva, Switzerland, 9-15 July 2000, Proceedings, pp. 73-84, (2000) · Zbl 0973.68665
[4] Barbay, J; He, M; Munro, JI; Satti, SR, Succinct indexes for strings, binary relations and multilabeled trees, ACM Trans. Algorithms, 7, 52, (2011) · Zbl 1295.68227
[5] Bille, P, A survey on tree edit distance and related problems, Theor. Comput. Sci., 337, 217-239, (2005) · Zbl 1078.68152
[6] Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct orthogonal range search structures on a grid with applications to text indexing. In: Algorithms and Data Structures, 11th International Symposium, WADS 2009, Banff, Canada, 21-23 August 2009. Proceedings, pp. 98-109, (2009) · Zbl 1253.68103
[7] Bringmann, K., Larsen, K.G.: Succinct sampling from discrete distributions. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC 2013, Palo Alto, California, USA, 1-4 June 2013, pp. 775-782, (2013) · Zbl 1293.62019
[8] Brodal, G.S., Davoodi, P., Lewenstein, M., Raman, R., Rao, S.S.: Two dimensional range minimum queries and fibonacci lattices. In: Algorithms—ESA 2012—20th Annual European Symposium, Ljubljana, Slovenia, 10-12 September 2012. Proceedings, pp. 217-228, (2012) · Zbl 1365.68172
[9] Brodal, G.S., Davoodi, P., Rao, S.S.: Path minima queries in dynamic weighted trees. In: Algorithms and Data Structures—12th International Symposium, WADS 2011, New York, NY, USA, 15-17 August 2011. Proceedings, pp. 290-301, (2011) · Zbl 1342.68106
[10] Brodal, GS; Davoodi, P; Rao, SS, On space efficient two dimensional range minimum data structures, Algorithmica, 63, 815-830, (2012) · Zbl 1254.68093
[11] Buchsbaum, AL; Georgiadis, L; Kaplan, H; Rogers, A; Tarjan, RE; Westbrook, J, Linear-time algorithms for dominators and other path-evaluation problems, SIAM J. Comput., 38, 1533-1573, (2008) · Zbl 1181.05079
[12] Chan, T.M., He, M., Munro, J.I., Zhou, G.: Succinct indices for path minimum, with applications to path reporting. In: Algorithms—ESA 2014—22th Annual European Symposium, Wroclaw, Poland, 8-10 September 2014. Proceedings, pp. 247-259, (2014) · Zbl 1365.68174
[13] Chan, T.M., Larsen, K.G., Pǎtraşcu, M.: Orthogonal range searching on the RAM, revisited. In: Proceedings of the 27th ACM Symposium on Computational Geometry, SoCG 2011, Paris, France, 13-15 June 2011, pp. 1-10, (2011) · Zbl 0874.68081
[14] Chazelle, B, Computing on a free tree via complexity-preserving mappings, Algorithmica, 2, 337-361, (1987) · Zbl 0636.68092
[15] Chazelle, B; Rosenberg, B, The complexity of computing partial sums off-line, Int. J. Comput. Geom. Appl., 1, 33-45, (1991) · Zbl 0724.68047
[16] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009) · Zbl 1187.68679
[17] Demaine, ED; Landau, GM; Weimann, O, On Cartesian trees and range minimum queries, Algorithmica, 68, 610-625, (2014) · Zbl 1248.68165
[18] Demaine, ED; López-Ortiz, A, A linear lower bound on index size for text retrieval, J. Algorithms, 48, 2-15, (2003) · Zbl 1079.68029
[19] Dixon, B; Rauch, M; Tarjan, RE, Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM J. Comput., 21, 1184-1192, (1992) · Zbl 0760.68032
[20] Durocher, S., Shah, R., Skala, M., Thankachan, S.V.: Linear-space data structures for range frequency queries on arrays and trees. In: Mathematical Foundations of Computer Science 2013—38th International Symposium, MFCS 2013, Klosterneuburg, Austria, 26-30 August 2013. Proceedings, pp. 325-336, (2013) · Zbl 1400.68062
[21] Durocher, S., Shah, R., Skala, M., Thankachan, S.V.: Top-k color queries on tree paths. In: String Processing and Information Retrieval—20th International Symposium, SPIRE 2013, Jerusalem, Israel, 7-9 October 2013, Proceedings, pp. 109-115, (2013) · Zbl 0724.68047
[22] Farzan, A; Munro, JI, A uniform paradigm to succinctly encode various families of trees, Algorithmica, 68, 16-40, (2014) · Zbl 1286.68117
[23] Farzan, A., Raman, R., Rao, S.S.: Universal succinct representations of trees? In: Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, 5-12 July 2009, Proceedings, Part I, pp. 451-462, (2009) · Zbl 1248.68168
[24] Ferragina, P., Manzini, G., Mäkinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms 3(2), 20 (2007) · Zbl 1321.68263
[25] Fischer, J; Heun, V, Space-efficient preprocessing schemes for range minimum queries on static arrays, SIAM J. Comput., 40, 465-492, (2011) · Zbl 1222.05024
[26] Frederickson, GN, Data structures for on-line updating of minimum spanning trees, with applications, SIAM J. Comput., 14, 781-798, (1985) · Zbl 0575.68068
[27] Frederickson, GN, Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees, SIAM J. Comput., 26, 484-538, (1997) · Zbl 0874.68081
[28] Frederickson, GN, A data structure for dynamically maintaining rooted trees, J. Algorithms, 24, 37-65, (1997) · Zbl 0882.68104
[29] Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, San Francisco, California, USA, 22-24 January 1990, pp. 434-443, (1990) · Zbl 0800.68617
[30] Geary, RF; Raman, R; Raman, V, Succinct ordinal trees with level-ancestor queries, ACM Trans. Algorithms, 2, 510-534, (2006) · Zbl 1321.68223
[31] Golynski, A, Optimal lower bounds for rank and select indexes, Theor. Comput. Sci., 387, 348-359, (2007) · Zbl 1144.68016
[32] Grossi, R., Orlandi, A., Raman, R., Rao, S.S.: More haste, less waste: Lowering the redundancy in fully indexable dictionaries. In: Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 517-528, Dagstuhl, Germany, (2009). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik · Zbl 1236.68064
[33] Harel, D; Tarjan, RE, Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13, 338-355, (1984) · Zbl 0535.68022
[34] He, M; Munro, JI; Satti, SR, Succinct ordinal trees based on tree covering, ACM Trans. Algorithms, 8, 42, (2012) · Zbl 1295.68102
[35] He, M., Munro, J.I., Zhou, G.: Path queries in weighted trees. In: Algorithms and Computation—22nd International Symposium, ISAAC 2011, Yokohama, Japan, 5-8 December 2011. Proceedings, pp. 140-149, (2011) · Zbl 1350.68073
[36] He, M., Munro, J.I., Zhou, G.: Succinct data structures for path queries. In Algorithms—ESA 2012—20th Annual European Symposium, Ljubljana, Slovenia, 10-12 September 2012. Proceedings, pp. 575-586, (2012) · Zbl 1365.68181
[37] He, M., Munro, J.I., Zhou, G.: Dynamic path counting and reporting in linear space. In: Algorithms and Computation—25th International Symposium, ISAAC 2014, Jeonju, Korea, 15-17 December 2014, Proceedings, pp. 565-577, (2014) · Zbl 1432.68092
[38] Meng, H; Munro, JI; Zhou, G, A framework for succinct labeled ordinal trees over large alphabets, Algorithmica, 70, 696-717, (2014) · Zbl 1314.68111
[39] Kaplan, H., S., Nira: Path minima in incremental unrooted trees. In: Algorithms—ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, 15-17 September 2008. Proceedings, pp. 565-576, (2008)
[40] King, V, A simpler minimum spanning tree verification algorithm, Algorithmica, 18, 263-270, (1997) · Zbl 0868.68061
[41] Komlós, J, Linear verification for spanning trees, Combinatorica, 5, 57-65, (1985) · Zbl 0579.05031
[42] Krizanc, D; Morin, P; Smid, MHM, Range mode and range Median queries on lists and trees, Nord. J. Comput., 12, 1-17, (2005) · Zbl 1083.68028
[43] Miltersen, P.B.: Lower bounds on the size of selection and rank indexes. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, 23-25 January 2005, pp. 11-12, (2005) · Zbl 1297.68085
[44] Munro, JI; Raman, V, Succinct representation of balanced parentheses and static trees, SIAM J. Comput., 31, 762-776, (2001) · Zbl 1017.68037
[45] Nivasch, G.: Inverse ackermann without pain. http://www.gabrielnivasch.org/fun/inverse-ackermann
[46] Patil, M; Shah, R; Thankachan, SV, Succinct representations of weighted trees supporting path queries, J. Discrete Algorithms, 17, 103-108, (2012) · Zbl 1268.68069
[47] Pettie, S, An inverse-ackermann type lower bound for online minimum spanning tree verification, Combinatorica, 26, 207-230, (2006) · Zbl 1121.05067
[48] Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007) · Zbl 1268.68069
[49] Sadakane, K., Grossi, R.: Squeezing succinct data structures into entropy bounds. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, 22-26 January 2006, pp. 1230-1239, (2006) · Zbl 1192.68188
[50] Sleator, DD; Tarjan, RE, A data structure for dynamic trees, J. Comput. Syst. Sci., 26, 362-391, (1983) · Zbl 0509.68058
[51] Vuillemin, J, A unifying look at data structures, Commun. ACM, 23, 229-239, (1980) · Zbl 0434.68047
[52] Yao, A.C.-C.: Space-time tradeoff for answering range queries (extended abstract). In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982, San Francisco, California, USA, 5-7 May 1982, pp. 128-136, (1982) · Zbl 0434.68047
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.