×

zbMATH — the first resource for mathematics

Linear-space data structures for range frequency queries on arrays and trees. (English) Zbl 1400.68062
Chatterjee, Krishnendu (ed.) et al., Mathematical foundations of computer science 2013. 38th international symposium, MFCS 2013, Klosterneuburg, Austria, August 26–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40312-5/pbk). Lecture Notes in Computer Science 8087, 325-336 (2013).
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, or \(\alpha \)-minority 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{\frac nw})\) 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 range mode queries on trees in \(O(\log\log n \sqrt{\frac nw})\) 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)]. Finally, we describe a data structure that supports range \(\alpha \)-minority queries on trees in \(O(\alpha ^{ - 1} \log\log n)\) time, where \(\alpha \in [0,1]\) is specified at query time.
For the entire collection see [Zbl 1270.68020].

MSC:
68P05 Data structures
PDF BibTeX XML Cite
Full Text: DOI