TY - GEN
T1 - Linear-space data structures for range minority query in arrays
AU - Chan, Timothy M.
AU - Durocher, Stephane
AU - Skala, Matthew
AU - Wilkinson, Bryan T.
N1 - Funding Information:
Work supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC).
PY - 2012
Y1 - 2012
N2 - We consider range queries in arrays that search for low-frequency elements: least frequent elements and α-minorities. An α-minority of a query range has multiplicity no greater than an α 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 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 α-minority range query problem requires O(n) space, supports queries in O(1/α) time, and allows α to be specified at query time.
AB - We consider range queries in arrays that search for low-frequency elements: least frequent elements and α-minorities. An α-minority of a query range has multiplicity no greater than an α 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 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 α-minority range query problem requires O(n) space, supports queries in O(1/α) time, and allows α to be specified at query time.
UR - http://www.scopus.com/inward/record.url?scp=84863109306&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84863109306&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-31155-0_26
DO - 10.1007/978-3-642-31155-0_26
M3 - Conference contribution
AN - SCOPUS:84863109306
SN - 9783642311543
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 295
EP - 306
BT - Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings
T2 - 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012
Y2 - 4 July 2012 through 6 July 2012
ER -