Advertisement
Published in:
2011 | OriginalPaper | Chapter
Dynamic Range Majority Data Structures
Authors : Amr Elmasry, Meng He, J. Ian Munro, Patrick K. Nicholson
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a set
P
of
n
coloured points on the real line, we study the problem of answering range
α
-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
α
-fraction of the points contained in
Q
. We present a new data structure for answering range
α
-majority queries on a dynamic set of points, where
α
∈ (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))$
. For constant values of
α
, 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
≥ 2, as well as dynamic arrays, in which each entry is a colour.