×

Linear-space data structures for range frequency queries on arrays and trees. (English) Zbl 1411.68034

Summary: We present \(O(n)\)-space data structures to support various range frequency queries on a given array \(A[0:n-1]\) or tree \(T\) with \(n\) nodes. Given a query consisting of an arbitrary pair of pre-order rank indices \((i,j)\), our data structures return a least frequent element, mode, \(\alpha\)-minority, or top-\(k\) colors (values) of the multiset of elements in the unique path with endpoints at indices \(i\) and \(j\) in \(A\) or \(T\). We describe a data structure that supports range least frequent element queries on arrays in \(O(\sqrt{n/w})\) time, improving the \(\Theta(\sqrt n)\) worst-case time required by the data structure of T. M. Chan et al. [Lect. Notes Comput. Sci. 7357, 295–306 (2012; Zbl 1318.68068)], where \(w\in\Omega(\log n)\) is the word size in bits. We describe a data structure that supports path mode queries on trees in \(O(\log\log n\sqrt{n/w})\) time, improving the \(\Theta(\sqrt n\log n)\) worst-case time required by the data structure of D. Krizanc et al. [Lect. Notes Comput. Sci. 2906, 517–526 (2003; Zbl 1205.68130)]. We describe the first data structures to support path least frequent element queries, path \(\alpha\)-minority queries, and path top-\(k\) color queries on trees in \(O(\log\log n\sqrt{n/w})\), \(O(\alpha^{-1}\log\log n)\), and \(O(k)\) time, respectively, where \(\alpha\in[0,1]\) and \(k\in\{1,\dots,n\}\) are specified at query time.

MSC:

68P05 Data structures
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Belazzougui, D., Botelho, F.C., Dietzfelbinger, M.: Hash, displace, and compress. In: Proceedings of ESA, LNCS, vol. 5757, pp. 682-693. Springer (2009) · Zbl 1256.68046
[2] Belazzougui, D., Gagie, T., Navarro, G.: Better space bounds for parameterized range majority and minority. In: Proceedings of WADS, LNCS, vol. 8037. Springer (2013) · Zbl 1391.68046
[3] Belazzougui, D., Navarro, G.: New lower and upper bounds for representing sequences. In: Proceedings of ESA, LNCS, vol. 7501, pp. 181-192. Springer (2012) · Zbl 1365.68260
[4] Belazzougui, D., Navarro, G., Valenzuela, D.: Improved compressed indexes for full-text document retrieval. J. Discrete Algorithms 18, 3-13 (2013) · Zbl 1268.68075 · doi:10.1016/j.jda.2012.07.005
[5] Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of LATIN, LNCS, vol. 1776, pp. 88-94. Springer (2000) · Zbl 0959.68133
[6] 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
[7] Brodal, G.S., Gfeller, B., Jørgensen, A.G., Sanders, P.: Towards optimal range medians. Theor. Comput. Sci. 412(24), 2588-2601 (2011) · Zbl 1220.68052 · doi:10.1016/j.tcs.2010.05.003
[8] Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. In: Proceedings of STACS, vol. 14, pp. 291-301 (2012) · Zbl 1245.68071
[9] Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. Theor. Comput. Syst. 55(4), 719-741 (2014) · Zbl 1319.68062
[10] Chan, T.M., Durocher, S., Skala, M., Wilkinson, B.T.: Linear-space data structures for range minority query in arrays. In: Proceedings of SWAT, LNCS, vol. 7357, pp. 295-306. Springer (2012) · Zbl 1318.68068
[11] Chazelle, B.: Filtering search: a new approach to query-answering. SIAM J. Comput. 15(3), 703-724 (1986) · Zbl 0612.68088 · doi:10.1137/0215051
[12] Davoodi, P., Raman, R., Rao, S.S.: Succinct representations of binary trees for range minimum queries. In: Proceedings of COCOON, LNCS, vol. 7434, pp. 396-407. Springer (2012) · Zbl 1364.68150
[13] Demaine, E.D., Landau, G.M., Weimann, O.: On cartesian trees and range minimum queries. In: Proceedings of ICALP, LNCS, vol. 5555, pp. 341-353. Springer (2009) · Zbl 1248.68165
[14] Durocher, S.: A simple linear-space data structure for constant-time range minimum query. In: Proceedings of Conference on Space Efficient Data Structures, Streams and Algorithms (Munro Festschrift), vol. 8066, pp. 48-60 (2013) · Zbl 1394.68093
[15] Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. In: Proceedings of ICALP, LNCS, vol. 6755, pp. 244-255. Springer (2011) · Zbl 1332.68032
[16] Durocher, S., He, M., Munro, J.I., Nicholson, P.K., Skala, M.: Range majority in constant time and linear space. Inf. Comput. 222, 169-179 (2013) · Zbl 1266.68097 · doi:10.1016/j.ic.2012.10.011
[17] Durocher, S., Munro, J.I., El-Zein, H., Thankachan, S.V.: Low space data structures for geometric range mode query. In: Proceedings of CCCG (2014) · Zbl 1315.68113
[18] Durocher, S., Shah, R., Skala, M., Thankachan, S.: Linear-space data structures for range frequency queries on arrays and trees. In: Proceedings of MFCS, LNCS, vol. 8087, pp. 325-336. Springer (2013) · Zbl 1400.68062
[19] Durocher, S., Shah, R., Skala, M., Thankachan, S.: Top-\[k\] k color queries on tree paths. In: Proceedings of SPIRE, LNCS, vol. 8214, pp. 109-115. Springer (2013)
[20] Emde Boas, P.V.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Proc. Lett. 6(3), 80-82 (1977) · Zbl 0364.68053 · doi:10.1016/0020-0190(77)90031-X
[21] Fischer, J.: Optimal succinctness for range minimum queries. In: Proceedings of LATIN, LNCS, vol. 6034, pp. 158-169. Springer (2010) · Zbl 1283.68141
[22] Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48(3), 533-551 (1994) · Zbl 0806.68057 · doi:10.1016/S0022-0000(05)80064-9
[23] Gagie, T., He, M., Munro, J.I., Nicholson, P.: Finding frequent elements in compressed 2D arrays and strings. In: Proceedings of SPIRE, LNCS, vol. 7024, pp. 295-300. Springer (2011) · Zbl 1220.68052
[24] Gagie, T., Kärkkäinen, J., Navarro, G., Puglisi, S.J.: Colored range queries and document retrieval. Theor. Comput. Sci. 483, 36-50 (2013) · Zbl 1292.68045 · doi:10.1016/j.tcs.2012.08.004
[25] Gagie, T., Puglisi, S.J., Turpin, A.: Range quantile queries: another virtue of wavelet trees. In: Proceedings of SPIRE, LNCS, vol. 5721, pp. 1-6. Springer (2009) · Zbl 1085.68103
[26] Gfeller, B., Sanders, P.: Towards optimal range medians. In: Proceedings of ICALP, LNCS, vol. 5555, pp. 475-486. Springer (2009) · Zbl 1248.68180
[27] Hagerup, T., Tholey, T.: Efficient minimal perfect hashing in nearly minimal space. In: Proceedings of STACS, LNCS, vol. 2010, pp. 317-326. Springer (2001) · Zbl 0976.68594
[28] He, M., Munro, J.I., Zhou, G.: Path queries in weighted trees. In: Proceedings of ISAAC, pp. 140-149 (2011) · Zbl 1350.68073
[29] He, M., Munro, J.I., Zhou, G.: Succinct data structures for path queries. In: Proceedings of ESA, pp. 575-586 (2012) · Zbl 1365.68181
[30] Hon, W.K., Shah, R., Vitter, J.S.: Space-efficient framework for top-k string retrieval problems. In: Proceedings of FOCS, pp. 713-722 (2009) · Zbl 1292.68182
[31] Jørgensen, A.G., Larsen, K.D.: Range selection and median: tight cell probe lower bounds and adaptive data structures. In: Proceedings of SODA, pp. 805-813 (2011) · Zbl 1373.68196
[32] Karpinski, M., Nekrich, Y.: Top-k color queries for document retrieval. In: Proceedings of SODA, pp. 401-411 (2011) · Zbl 1373.68197
[33] Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. In: Proceedings of ISAAC, LNCS, vol. 2906, pp. 517-526. Springer (2003) · Zbl 1205.68130
[34] Krizanc, D., Morin, P., Smid, M.: Range mode and range median queries on lists and trees. Nordic J. Comput. 12, 1-17 (2005) · Zbl 1083.68028
[35] Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: Proceedings of SODA, pp. 657-666 (2002) · Zbl 1093.68588
[36] Navarro, G., Nekrich, Y.: Top-\[k\] k document retrieval in optimal time and linear space. In: Proceedings of SODA, pp. 1066-1077 (2012) · Zbl 1422.68063
[37] Patil, M., Shah, R., Thankachan, S.V.: Succinct representations of weighted trees supporting path queries. J. Discrete Algorithms 17, 103-108 (2012) · Zbl 1268.68069 · doi:10.1016/j.jda.2012.08.003
[38] Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proceedings of SODA, pp. 134-149 (2010) · Zbl 1288.05046
[39] Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19(5), 775-786 (1990) · Zbl 0711.68039 · doi:10.1137/0219054
[40] Skala, M.: Array range queries. In: Proceedings of Conference on Space Efficient Data Structures, Streams and Algorithms (Munro Festschrift), vol. 8066, pp. 333-350 (2013) · Zbl 1394.68103
[41] Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362-391 (1983) · Zbl 0509.68058 · doi:10.1016/0022-0000(83)90006-5
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.