Computer Science – Data Structures and Algorithms
Scientific paper
2011-04-28
Computer Science
Data Structures and Algorithms
12 pages, plus 2 page appendix
Scientific paper
Given a set $P$ of coloured points on the real line, we study the problem of answering range $\alpha$-majority (or "heavy hitter") queries on $P$. More specifically, for a query range $Q$, we want to return each colour that is assigned to more than an $\alpha$-fraction of the points contained in $Q$. We present a new data structure for answering range $\alpha$-majority queries on a dynamic set of points, where $\alpha \in (0,1)$. Our data structure uses O(n) space, supports queries in $O((\lg n) / \alpha)$ time, and updates in $O((\lg n) / \alpha)$ amortized time. If the coordinates of the points are integers, then the query time can be improved to $O(\lg n / (\alpha \lg \lg n) + (\lg(1/\alpha))/\alpha))$. For constant values of $\alpha$, this improved query time matches an existing lower bound, for any data structure with polylogarithmic update time. We also generalize our data structure to handle sets of points in d-dimensions, for $d \ge 2$, as well as dynamic arrays, in which each entry is a colour.
He Meng
Munro Ian J.
Nicholson Patrick K.
No associations
LandOfFree
Dynamic Range Majority Data Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dynamic Range Majority Data Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic Range Majority Data Structures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-16984