zbMATH — the first resource for mathematics

Linear-space data structures for range minority query in arrays. (English) Zbl 1318.68068
Fomin, Fedor V. (ed.) et al., Algorithm theory – SWAT 2012. 13th Scandinavian symposium and workshops, Helsinki, Finland, July 4–6, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31154-3/pbk). Lecture Notes in Computer Science 7357, 295-306 (2012).
Summary: We consider range queries in arrays that search for low-frequency elements: least frequent elements and \(\alpha \)-minorities. An \(\alpha \)-minority of a query range has multiplicity no greater than an \(\alpha \) fraction of the elements in the range. Our data structure for the least frequent element range query problem requires \(O(n)\) space, \(O(n ^{3/2})\) preprocessing time, and \(O(\sqrt{n})\) query time. A reduction from boolean matrix multiplication to this problem shows the hardness of simultaneous improvements in both preprocessing time and query time. Our data structure for the \(\alpha \)-minority range query problem requires \(O(n)\) space, supports queries in \(O(1/\alpha )\) time, and allows \(\alpha \) to be specified at query time.
For the entire collection see [Zbl 1243.68018].

68P05 Data structures
Full Text: DOI