|
Title |
Encodings for Range Majority Queries |
|
Authors |
Gonzalo Navarro, Sharma V. Thankachan |
|
Publication date |
2014 |
|
Abstract |
We face the problem of designing a data structure that can report the majority within any range of an array A[1,n], without storing A. We show that Omega(n) bits are necessary for such a data structure, and design a structure using O(n log^* n) bits that answers majority queries in O(log n) time. We extend our results to tau-majorities. |
|
Downloaded |
7 times |
|
Pages |
262-272 |
|
Conference name |
Annual Symposium on Combinatorial Pattern Matching |
|
Publisher |
Springer-Verlag (Berlin/Heidelberg, Germany) |
|
PDF |
|
|
Reference URL |
|
