|
Published Articles >> Table of Contents >> Abstract
22nd International Conference on Data Engineering (ICDE'06)
p. 67
Approximately Processing Multi-granularity Aggregate Queries over Data Streams
Shouke Qin, Fudan University, China
Weining Qian, Fudan University, China
Aoying Zhou, Fudan University, China
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2006.22
Send link to a friend
| Abstract |
|
Aggregate monitoring over data streams is attracting
more and more attention in research community due to its
broad potential applications. Existing methods suffer two
problems, 1) The aggregate functions which could be monitored
are restricted to be first-order statistic or monotonic
with respect to the window size. 2) Only a limited number
of granularity and time scales could be monitored over a
stream, thus some interesting patterns might be neglected,
and users might be misled by the incomplete changing profile
about current data streams. These two impede the development
of online mining techniques over data streams,
and some kind of breakthrough is urged. In this paper,
we employed the powerful tool of fractal analysis to enable
the monitoring of both monotonic and non-monotonic
aggregates on time-changing data streams. The monotony
property of aggregate monitoring is revealed and monotonic
search space is built to decrease the time overhead for accessing
the synopsis from O(m) to O(logm), where m is
the number of windows to be monitored. With the help of
a novel inverted histogram, the statistical summary is compressed
to be fit in limited main memory, so that high aggregates
on windows of any length can be detected accurately
and efficiently on-line. Theoretical analysis show the space
and time complexity bound of this method are relatively low,
while experimental results prove the applicability and efficiency
of the proposed algorithm in different application settings.
|
 Additional Information
|
Citation:
Shouke Qin, Weining Qian, Aoying Zhou,
"Approximately Processing Multi-granularity Aggregate Queries over Data Streams,"
icde,
p. 67,
22nd International Conference on Data Engineering (ICDE'06),
2006
|
|
