Name
Abstract | ||
|---|---|---|
We consider range queries that search for low-frequency elements (least frequent elements and $$\\alpha $$¿-minorities) in arrays. 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)$$O(n) space, $$O(n^{3/2})$$O(n3/2) preprocessing time, and $$O(\\sqrt{n})$$O(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)$$O(n) space, supports queries in $$O(1/\\alpha )$$O(1/¿) time, and allows $$\\alpha $$¿ to be specified at query time. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-642-31155-0_26 | Algorithmica |
Keywords | Field | DocType |
Data structures,Range queries,Minority,Least frequent element | Query optimization,Discrete mathematics,Data structure,Computer science,Linear space,Range query (data structures),Multiplicity (mathematics),Preprocessor,Boolean matrix multiplication | Journal |
Volume | Issue | Citations |
72 | 4 | 20 |
PageRank | References | Authors |
0.70 | 48 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Timothy M. Chan | 1 | 2033 | 150.55 |
| Stephane Durocher | 2 | 342 | 42.89 |
| Matthew Skala | 3 | 101 | 12.52 |
| Bryan T. Wilkinson | 4 | 43 | 4.18 |