Adaptive Spatial Partitioning for Multidimensional Data Streams |
| |
Authors: | John Hershberger Nisheeth Shrivastava Subhash Suri Csaba D Toth |
| |
Affiliation: | (1) Mentor Graphics Corp., 8005 SW Boeckman Road, Wilsonville, OR 97070, USA;(2) Department of Computer Science, University of California at Santa Barbara, Santa Barbara, CA 93106, USA;(3) Department of Mathematics, Room 2-336, MIT, Cambridge, MA 02139, USA |
| |
Abstract: | We propose a space-efficient scheme for summarizing multidimensional data streams. Our sketch can be used to solve spatial
versions of several classical data stream queries efficiently. For instance, we can track ε-hot spots, which are congruent
boxes containing at least an ε fraction of the stream, and maintain hierarchical heavy hitters in d dimensions. Our sketch
can also be viewed as a multidimensional generalization of the ε-approximate quantile summary. The space complexity of our
scheme is O((1/ε) log R) if the points lie in the domain 0, R]d, where d is assumed to be a constant. The scheme extends to the sliding window model with a log (ε n) factor increase in
space, where n is the size of the sliding window. Our sketch can also be used to answer ε-approximate rectangular range queries
over a stream of d-dimensional points. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|