×

zbMATH — the first resource for mathematics

Tree path majority data structures. (English) Zbl 1453.68062
Summary: We present the first solution to finding \(\tau \)-majorities on tree paths. Given a tree of \(n\) nodes, each with a label from \([1 . . \sigma]\), and a fixed threshold \(0 < \tau < 1\), such a query gives two nodes \(u\) and \(v\) and asks for all the labels that appear more than \(\tau \cdot | P_{u v} |\) times in the path \(P_{u v}\) from \(u\) to \(v\), where \(| P_{u v} |\) denotes the number of nodes in \(P_{u v}\). Note that the answer to any query is of size up to \(1 / \tau \). On a \(w\)-bit RAM, we obtain a linear-space data structure with \(O((1 / \tau) \lg \lg_w \sigma)\) query time, which is worst-case optimal for polylogarithmic-sized alphabets. We also describe two succinct-space solutions with query time \(O((1 / \tau) \lg^\ast n \lg \lg_w \sigma)\). One uses \(2 n H + 4 n + o(n)(H + 1)\) bits, where \(H \leq \lg \sigma\) is the entropy of the label distribution; the other uses \(n H + O(n) + o(n H)\) bits. By using just \(o(n \lg \sigma)\) extra bits, our succinct structures allow \(\tau\) to be specified at query time. We obtain analogous results to find a \(\tau \)-minority, that is, an element that appears between 1 and \(\tau \cdot | P_{u v} |\) times in \(P_{u v}\).
MSC:
68P05 Data structures
05C05 Trees
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Gagie, T.; He, M.; Navarro, G., Tree path majority data structures, (Proc. 29th International Symposium on Algorithms and Computation (ISAAC). Proc. 29th International Symposium on Algorithms and Computation (ISAAC), LIPICs, vol. 123 (2018)), Article 68 pp.
[2] Fang, M.; Shivakumar, N.; Garcia-Molina, H.; Motwani, R.; Ullman, J. D., Computing iceberg queries efficiently, (Proc. 24th VLDB (1998)), 299-310
[3] Demaine, E. D.; López-Ortiz, A.; Munro, J. I., Frequency estimation of internet packet streams with limited space, (Proc. 10th ESA (2002)), 348-360 · Zbl 1019.68502
[4] 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. Syst., 55, 4, 719-741 (2014) · Zbl 1319.68062
[5] Belazzougui, D.; Gagie, T.; Munro, J. I.; Navarro, G.; Nekrich, Y., Range majorities and minorities in arrays (2016), CoRR
[6] Gagie, T.; He, M.; Munro, J. I.; Nicholson, P. K., Finding frequent elements in compressed 2d arrays and strings, (Proc. 18th SPIRE (2011)), 295-300
[7] 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) · Zbl 1083.68028
[8] Durocher, S.; Shah, R.; Skala, M.; Thankachan, S. V., Linear-space data structures for range frequency queries on arrays and trees, Algorithmica, 74, 1, 344-366 (2016) · Zbl 1411.68034
[9] Clark, D. R., Compact PAT trees (1996), University of Waterloo: University of Waterloo Canada, Ph.D. thesis
[10] Raman, R.; Raman, V.; Rao, S. S., Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets, ACM Trans. Algorithms, 3, 4, Article 43 pp. (2007) · Zbl 1446.68046
[11] Belazzougui, D.; Navarro, G., Optimal lower and upper bounds for representing sequences, ACM Trans. Algorithms, 11, 4, Article 31 pp. (2015) · Zbl 1398.68103
[12] Belazzougui, D.; Navarro, G., Alphabet-independent compressed text indexing, ACM Trans. Algorithms, 10, 4, Article 23 pp. (2014) · Zbl 1398.68102
[13] Belazzougui, D.; Gagie, T.; Navarro, G., Better space bounds for parameterized range majority and minority, (Proc. 12th WADS (2013)), 121-132 · Zbl 1391.68046
[14] Misra, J.; Gries, D., Finding repeated elements, Sci. Comput. Program., 2, 2, 143-152 (1982) · Zbl 0497.68041
[15] Bender, M.; Farach-Colton, M., The level ancestor problem simplified, Theor. Comput. Sci., 321, 1, 5-12 (2004) · Zbl 1068.68047
[16] 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
[17] He, M.; Munro, J. I.; Zhou, G., A framework for succinct labeled ordinal trees over large alphabets, Algorithmica, 70, 4, 696-717 (2014) · Zbl 1314.68111
[18] Tsur, D., Succinct representation of labeled trees, Theor. Comput. Sci., 562, 320-329 (2014) · Zbl 1303.68043
[19] Navarro, G.; Sadakane, K., Fully-functional static and dynamic succinct trees, ACM Trans. Algorithms, 10, 3, Article 16 pp. (2014) · Zbl 1333.68084
[20] Sleator, D.; Tarjan, R. E., A data structure for dynamic trees, J. Comput. Syst. Sci., 26, 3, 362-391 (1983) · Zbl 0509.68058
[21] Bell, T. C.; Cleary, J.; Witten, I. H., Text Compression (1990), Prentice Hall
[22] Russo, L.; Navarro, G.; Oliveira, A., Fully-compressed suffix trees, ACM Trans. Algorithms, 7, 4, Article 53 pp. (2011) · Zbl 1295.68103
[23] Chan, T. M.; Durocher, S.; Skala, M.; Wilkinson, B. T., Linear-space data structures for range minority query in arrays, Algorithmica, 72, 4, 901-913 (2015) · Zbl 1319.68063
[24] Muthukrishnan, S., Efficient algorithms for document retrieval problems, (Proc. 13th SODA (2002)), 657-666 · Zbl 1093.68588
[25] Chazelle, B., Computing on a free tree via complexity-preserving mappings, Algorithmica, 2, 1, 337-361 (1987) · Zbl 0636.68092
[26] Chan, T. M.; He, M.; Munro, J. I.; Zhou, G., Succinct indices for path minimum, with applications, Algorithmica, 78, 2, 453-491 (2017) · Zbl 1369.68167
[27] Gagie, T.; He, M.; Navarro, G., Path queries on functions, Theor. Comput. Sci., 770, 34-50 (2019) · Zbl 07050144
[28] Gagie, T.; He, M.; Navarro, G., Compressed dynamic range majority and minority data structures (2018), CoRR
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.