# 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].

##### MSC:
 68P05 Data structures
Full Text: