Computing Diameter in the Streaming and Sliding-Window Models |
| |
Authors: | Joan Feigenbaum Sampath Kannan and Jian Zhang |
| |
Affiliation: | (1) Department of Computer Science, Yale University, P.O. Box 208285, New Haven, CT 06520-8285, USA;(2) Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, USA |
| |
Abstract: | We investigate the diameter
problem in the streaming and sliding-window
models. We show that, for
a stream of $n$ points or a sliding window of size $n$, any exact
algorithm for diameter requires $\Omega(n)$ bits of
space. We present a simple $\epsilon$-approximation algorithm
for computing the diameter in the streaming model. Our main result
is an $\epsilon$-approximation algorithm
that maintains the diameter in two dimensions in the sliding-window
model using $O(({1}/{\epsilon^{3/2}}) \log^{3}n(\log R+\log\log n +
\log ({1}/{\epsilon})))$ bits of space, where $R$ is the maximum, over all
windows, of the ratio of the diameter to the minimum non-zero distance
between any two points in the window. |
| |
Keywords: | Massive data streams Sliding window Diameter |
本文献已被 SpringerLink 等数据库收录! |
|