Advertisement
Published in:
2010 | OriginalPaper | Chapter
An Space Lower Bound for Finding ε-Approximate Quantiles in a Data Stream
Authors : Regant Y. S. Hung, Hingfung F. Ting
Published in: Frontiers in Algorithmics
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
This paper studies the space complexity of the
ε
-approximate quantiles problem, which asks for some data structure that enables us to determine, after reading a whole data stream, a
φ
-quantile (for any 0 ≤
φ
≤ 1) of the stream within some error bound
ε
. The best known algorithm for the problem uses
$O(\frac{1}{\varepsilon}\log \varepsilon N)$
words where
N
is the total number of items in the stream, or uses
$O(\frac{1}{\varepsilon}\log |U|)$
words where
U
is the set of possible items. It is known that the space lower bound of the problem is
$\Omega(\frac{1}{\varepsilon})$
words; however, improvement of this bound is elusive.
In this paper, we prove that any comparison-based algorithm for finding
ε
-approximate quantiles needs
$\Omega(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$
words.