Data Stream and its RealTime Processing

Aoying Zhou (周傲英)Institute of Massive computing(IMC)
East China Normal University(ECNU)

Outline
Overview of data stream
Some research work done by us Frequent pattern Clustering and density estimate
 Streaming system
 Aggregate
gg g
query
q
y
 Complex data Uncertain stream

Conclusions and future work2

Data
a a Stream
a a
and
d Qu
QueriesStreaming
Data

Applications

Results

Queries

Data Stream
Processing
Engine Digits (e.g.,head of a data

packet) Structured tuple (e.g., Web-log)g,p/ XML documents ((e.g.,
pub/sub
system)Queries

Data
Streams
LimitedStorage

Data streams

 Continuous/ad hoc Queries

 May have different complexity

Synopsis Counting

 Structured queries (SQL) Data analysis and mining

Streamingg Algorithms
g
1
1
0
0
1

MEM
(Synopsis Data Structures)

0
1
1

0

1

1

MEM: poly(1/ε, log N)
Query/Update: poly(1/ε, log N)
N: stream size or window sizeNε: error parameter

4

Data Models
Synopsis
S
i D
Data
t St
Structure
t
(MEM)
I
Input
t streamstStreamalgorithm

Approximatepp
results

AccordingA
di tto D
Datatcharacteristics

According to queryrange

 Time series model Landmark
L dk modeld l

 Cash-register model Sliding-window model Turnstile model Damped
Damped-window
window modelFrequencyqy Related Problems
Top-k most frequent elements
Find elements thatoccupy 0.1% of the tail.

Mean + Variance?
Median?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Find all elementswith frequency > 0.1%

Whatt isWh
i theth frequency
fof element 3?

What is the total frequencyof elements between 8 and 14?

6

Data Stream Management System(DSMS)
Streamed
ResultRlRegister
QueryStoredResultDSMS
Input streams

Archive
Scratch StoreStoredRelations
7

DBMS vs. DSMS
Database Systems

D
Data
S
Stream S
Systems

Model:
M
d l: persistenti t t
relations Relation: tuple
p set/bagg Data update:
modifications
 Query:Q
ttransienti t Query Answer: exact
 Query Evaluation:
arbitrary Query Plan: fixedModel: transient relations
 Relation: tuple sequence Data update:
update appends
 Query: persistent Query Answer:
approximate
 Query Evaluation: onepass Query Plan: adaptive

8

Some SystemsyDevelopedpat
Labs
AuroraA

Brow University, MIT, Brandeis University httphttp://www.cs.brown.edu/research/aurora///www.cs.brown.edu/research/aurora/NiagaraUniversity of Wisconsin http://www.cs.wisc.edu/niagara/

STREAM
Stanford University http://infolab.stanford.edu/stream/TelegraphCQ
U. C. Berkley
 http://telegraph.cs.berkeley.edu/telegraphcq/v0.2/
9

From Laboratories to
I d t iIndustries
Aurora → StreamBase http://www.streambase.com/

STREAM → Coral8
 http://www.coral8.com/
http://www coral8 com/

TelegraphCQ → Truviso
 http://www.truviso.com/
h
//
i
/

CEP: Complex Event Processing
RT-BI: Real Time Business IntelligenceOur Research Interests
JOS

SurveyFrequent pattern
Clustering,
Density estimate

CIKM

VLDB

DASFAA,WAIMDASFAA

JCRD

StreamsystemAggregate query

APWEB

IS
SDM,WAI
M,JCST

KAIS,IC
DE,JOSDASFAAFCSCDASFAA ICDE,
JOS

ICDE

ICDE

ICDE

ICDE

Complex Data
VLDB

Uncertainty
2003

2004

2005

2006

2007

2008
11

Frequentq
Pattern Miningg
JOS

SurveyFrequent pattern
Clustering,
Density estimate

CIKM

VLDB

DASFAA,WAIMDASFAA

JCRD

StreamsystemAggregate query

APWEB

IS
SDM,WAI
M,JCST

KAIS,IC
DE,JOSDASFAAFCSCDASFAA ICDE,
JOS

ICDE

ICDE

ICDE

ICDE

Complex Data
VLDB

Uncertainty
2003

2004

2005

2006

2007

2008
12

Synopsis Maintenance & Counting–
B k
Background
d

Data
D
t items：<id,+/->
itid /Queries：count(id) Usually,Ull hot-spots,h t
t i.e.,
i

the
th it
items withithhighest count(id)ʼs, are most interested.

Existing approaches

Sketch-based [CCFC02]
 Space complexity: Ω(k/ε2 log
l n)) Group-test [CM03]
 Space complexity: O(k(log k+log 1/δ)log M)hCount: Structure andalgorithm[Jin, CIKM03]

S
Synopsisi datad t structurett Hash table: S[m][h], each item is a count（Bloom-filter + counters）
 h hash functions: H1, H2, …, Hh (Hi:
[1:M]Æ[1:m])
 Maintenance When an item arrives, the hash table isupdatedp When a count estimation query arrives
 Select one candidate item in each line

 Return the candidate item with lowest value
14

hCount: An examplep

S
Steps:(1－6):
1.
2.
3.
4.
5
5.
6.

Hash table at t4
At t5 : insert(9)At t6 : delete(6)Hash table at t38
Estimating item 9
Estimating item 6

15

hCount: Conclusion
Low space complexity：O(ε -1log M)
Fast per-tuplepp processingpg costHigh recall and precision16

Frequent Pattern (FP) Mining:
P bl
ProblemDescriptionDi tiFrequent pattern mining is a basic problem in data mining
 Given a set of transactions, each of which is a set of items
 The support of an itemset is the frequency of thet ansactions contain the itemset
transactions
 To find out all the itemsets whose support is greater than
the threshold
Frequent pattern mining
i iover datadstreams iis diffdifferent to FP
mining on static databases The data stream can only be scanned once
 For combinational explosion, previous FP-mining methods
cannot be extended to be applied on data streams
Basic idea
 Frequent item mining is the first step of FP mining Existing methods can be classified as: False positive methods
methods, and False negative methods

FP Mining – False Positive vs. False
N
Negativeti

False positive methods
 The itemsets whose support is lower than the thresholdmay be returned
Too many false positive results may greatly affect thereliability of the mining process Previous methods (based on error control parameter ε ) all

report a large amount of false positive results A large amount of combinations of items should be considered
due to the false positive items/itemsets
 May result in huge consumptions of memory storage

False negative methods
 May ignore itemsets whose support is above the threshold
9 Higher accuracy
9 Much fewer storageg consumptionpFDPM (Frequent Data-stream Pattern
Mining)[Yu, VLDB04]

Mining frequent patterns (items/itemsets) from a high speedtransactional data stream.
A large data item domain (I)A virtually unbounded sequence of a data stream (N)Limit memory space (M)One-scan of data

Th mainThe
i difficultydiffi lt off ffrequentt ititemsetst miningi iThe possible number of itemsets is 2I-1
When N becomes very large, the possibility of an itemset to be
frequent becomes larger
larger, and it is difficult to track with limited
memory.

The technique of frequent itemsets mining is largely
dependent on the technique developed for frequent items
mining.


Approximate mining with two parameters ε and δ, using a
synopsis.

19

FDPM: Basic Ideas
Mi i
Miningfrequentft itemsit Using dynamic error parameter εn(decided byminimumi isupportt andd probability
b bilit parametert δ) δ is used to control the memory consumption


S
Space
complexity
l it isi relatedl t d tot ln(1/l (1/δ),) nott 1/ε Pruning technique: Chernoff bound

Extension: Mining frequent itemsets

 Using rules to reserve frequent itemsets

20

FDPM – Summary
FDPM: One-scan false-negativef lalgorithmlh fforfrequent pattern mining The frequent itemsets that are falsely dropped areprobabilistically bounded The accuracy of frequent item mining is theoreticallygguaranteed The empirical bound of accuracy for frequent itemset
mining is investigated Empirical result show the effectiveness and efficiencyof our FDPM method

Clustering and Density
estimation
JOS

SurveyFrequent pattern
Clustering,
Density estimate

CIKM

VLDB

DASFAA,WAIMDASFAA

JCRD

StreamsystemAggregate query

APWEB

IS
SDM,WAI
M,JCST

KAIS,IC
DE,JOSDASFAAFCSCDASFAA ICDE,
JOS

ICDE

ICDE

ICDE

ICDE

Complex Data
VLDB

Uncertainty
2003

2004

2005

2006

2007

2008
22

Clustering using GPU[Cao, WAIM06]

G
Graphics
hi P
Processing
i
Units
U it
 Parallel processing
 SIMD

Observation

 K-means is a widely used clustering method
 GPU can optimize two time-cost operations
 Distance calculation

 Distance comparison

 The above operators can be optimized byGPU

Clustering an Evolving
StreamSt[Cao, SDM06]

The clusters will change their shapes withtime going on.
 Important to report the changes.
changes
Our method: Density-based clustering
method Capable of summarizing clusters with
arbitrary shape.
Contributions
 Can handle arbitrary shape, not only
spheres.
h Capable of reporting outliers
 Using outlier-buffero tlie b ffe to hasten theprocessing.
 achieves consistently high clustering

Clustering an Evolving Stream:
Al
Algorithm
ithStructureS C-Micro-cluster:
Main buffer used for p
potential clusters
 In the main buffer
Outlier buffer O-micro-cluster: potential
t ti l outlierstlimemory In the outlier buffer
Merge operator
 For each new pointer p Try to find an existed micro-cluster in main buffer to merge
 If failed,failed check whether it can be absorbed by an o-microcluster.
 If step 2 successes, try to convert an o-micro-cluster to ac-micro-cluster If Step 2 failed, this point is created as an o-micro-cluster.

Clustering an Evolving Stream:
E
ExperimentsitClustering over Sliding Windows–Problem
D
Descriptioni ti

For continuouslyFtil arriving
i imultilti
dimensional (d-dimʼl) tuples Xi(xi1,xi2,…xid),
analyzing The clusters on the last N tuples

 The emerge,
emerge development and trends ofthese clusters Previous methods：

y processp
g windows,,
Cannot efficiently
over sliding
or
Cannot accurately analyze the evolving of a
specific cluster

SWClustering: Clustering over Sliding
Windowsd[Zhou, KAIS07]

G l
Goal:

 Clustering over sliding window Tracking the evolving of clusters

28

SWClustering: Clustering over Sliding
Windowsd[Zhou, KAIS07]

Basic
B
i ideaid
 Integrate information of time in cluster features

Maintain sufficient information about the evolving of acluster

Embed cluster features (CF) in exponential histograms(EH) {EHi({CFji})} Can maintain the sufficient information for clustering withapproximation factor 1+ε Compared with pyramidal technology [AHWY03] SSi({CFj}):
9 NeedN d not to store snapshot
h SS
9 Since a specific cluster can be retrieved to be analyzed
alone,, it is more flexible
29

SWClustering:g DataStructure
P1

P2

P3

TCF
Temporal CF

TCF
Temporal CF:(CF2,CF1,t,n)

P4

P5

P6 P7

P8

P9

P10

2 1-tier TCFs 2 0-tier TCFs

• Maintaining multiple EHCF
simultaneously

EHCF
EH+CF

• Clustering is in fact themerge of multiple EHCF
• Efficiency can be further
improved by later merging
off EHCF30

SWClustering:g Experiments
SWClusteringv.s.
CluStream
Economic
space
consumptionti

31

Clustering Analysis –Summary

SWClusteringSWClt i
iis more accuratet anddefficient than snapshot-based methods
Due to the embedding of CF in EH, theanalysisyis more flexible
Theoretical analysis show that the spaceconsumption is limited
Empirical result show that this method isefficient for clustering a data stream

Distributed Clustering:
S
Scenarioi[Zhou, ICDE07]

G l Reducing
Goal:
R d i
the
th communication
i ti
costt

Expectation-Maximization (EM)Al
Algorithm
ithDistributed Clustering: Basic
Steps
St

Remote site processing
 Divide & Conquer
 Cluster the incoming data records only after theydonʼt pass the test
Coordinator Processing
 Avoid local maximal --Over component population

 In general, when many data records lead to almost

equal posterior probability for any two components,
it can be thought that these two components might
be merged.
gDistributed Clustering:
Summary

A frameworkfk tto clusterl t ththe di
distributedt ib t ddata streams with soft membership in
consideration
Event driven clustering for capturing
the distribution of individual stream at
remotet siteit
Can also be applied
pp
to a lot of related
problems

Our Interests: StreaminggsystemJOS

SurveyFrequent pattern
Clustering,
Density estimate

CIKM

VLDB

DASFAA,WAIMDASFAA

JCRD

StreamsystemAggregate query

APWEB

IS
SDM,WAI
M,JCST

KAIS,IC
DE,JOSDASFAAFCSCDASFAA ICDE,
JOS

ICDE

ICDE

ICDE

ICDE

Complex Data
VLDB

Uncertainty
2003

2004

2005

2006

2007

2008

Shared Window Joins:
D
Definition
fi itiExampleQ1: SELECT count(A.Id)
A B
FROM
A,
WHERE A.Id=B.Id and A.value>δ
WINDOW 1 min;Q2: SELECT A. Id, MAX(B.value)
FROM
A, B
WHERE A
A.Id=B.Id
Id=B Id GROUP BY A.
A Id
WINDOW 1 hour;Previous methods

MQT[HFAE03]：schedule tuples according
to the window sizes

Cannot adapt to the bursty stream rates

Shared Window Joins: Load
Shedding[Yan, JCRD04]

B i Idea
Basic
Id
(L
(Load
d shedding)h ddi )


9

When the query cannot be handled with current
resources, parts of data is dropped to shed systemʼssystem s load
Can enhance systemʼs throughput
Can only provide approximate results

Steps




Deploy load shedding
operators at every window
d

wi

w1

Two strategies
w1wi Uniform sheddingwn Small-window exact sheddingwnShared Window Joins: Adaptive
Scheduling[Jin,
FCSC07]

B i Idea
Basic
Id




Schedule tuples according to the count of data items, notthe timetime-base
base window sizes
Can reduce the response time

ExamplepConsider three queries Q1, Q2, Q3 over two streams A,
B, whose window sizes w1, w2, and w3 are 1 second, 2second and 3 seconds respectively
respectively. The rate of stream A is
1tuple /sec.
[0, w1]( 1 w2](w1,
2](w2, w3]b f
beforet(t t + 1](t,(t + 1,
1 t + 2](t + 2,2 t + 3]

Shared Window Joins: Adaptive
S h d li
Scheduling

The method
1. All uncompleted tuples are reserved in a BUFFER.
2. Monitoring the number of tuples in the BUFFER.
1.

Normally, the number of tuples is in low level.
When it exceeds a threshold, a burst rises.

1.
2.

Generate a real-time scheduling plan according to tuple
distribution.
Schedule future tuples and buffered tuples by the new schedulingplan.

Analysis The real-time scheduling plan is optimal for bursty
t ltuples.
 Cost to generate a scheduling plan can be ignored.
 It much outperforms MQT (best previous method)
method for applications where rate changes violently It owns comparable performance with MQT method
when rate is steadySMART: Background[Zhou, ICDE08]

SMART: A System for Online Monitoring Large
Volumes of Network Traffic, a project from
Shanghai Telecomm
More and more business of Telecomm are run on
IP network
Acquire network traffic patterns and take quick
actions on abnormalities
Problems of current systemsyin telecom
companies
 Based on Flow-tools in a disk-based offline manner Inefficiency,
Inefficiency too long response time

Solutions ̶ streaming algorithms
 Memory based

 Approximate with error guarantee

 Abstract in formations into sketches

SMART: Sliding Window Frequent
T
Top-k
k

Multi-level structure
stream.->….24 hours

24 hours…12 hours

12 hours

6
3

3

6
3

12 hours

6
3

3

3

24 hours ……

6
3

3

6
3

3

3

12 hours

12 …

6

6

3

6
3

3

3

3

SMART: System ArchitectureSMART: Visualizations

Our Interests: Streamingg
SystemJOS

SurveyFrequent pattern
Clustering,
Density estimate

CIKM

VLDB

DASFAA,WAIMDASFAA

JCRD

StreamsystemAggregate query

APWEB

IS
SDM,WAI
M,JCST

KAIS,IC
DE,JOSDASFAAFCSCDASFAA ICDE,
JOS

ICDE

ICDE

ICDE

ICDE

Complex Data
VLDB

Uncertainty
2003

2004

2005

2006

2007

2008

Aggregate Monitoring:
P bl
Problem

Aggregate functions: sum
sum, avg
avg, minmin,max, …
Applications of online monitoring data
streams:
 Networks traffic management
management, trend
trend-related
relatedanalysis, web-click streams analysis, stocks
exchange, e-mail and news articles, and sensor
networks.
networks

However, existing methods suffer
several problems: Expensive cost of time O(m) Aggregate functions are restricted to be first-orderfirst order

statistic or monotonic with respect to the windowsize.

Aggregate Monitoring:
P bl
ProblemAssuming that F is an aggregate
function,, wi is a sliding
g window withgiven length, and T(wi ) is the thresholdof F(wi ) given by users beforehand
beforehand.
The result is reported on wi when
st eam X is updated
streampdated and if F(wi ) ≥T(wi).

Fractal-based Approach:contributions
t ib ti[Qin, ICDE06]
Incorporate the tool of fractal
analysis and can process data
which does not obey the exact
fractal models.
The monotony property ofaggregate monitoring is revealed
and monotonic search space is built
to decrease the time overhead
from O(m) to O(log m)m).
Propose a novel synopsis, called
Inverted Histogram (IH)
(IH), andprovide the error bound for IH
based monitoring algorithm

Fractal-based Approach:F t lFractal•Power Law Scaling Relationship•When a quantitative property, q, ismeasured on scale s,s its value depends on s
according to the following power law scaling
relationship:

log q
d=
log s

llog F ( wi )d=logg wiExact fractal: +Statistical fractal: ·Fractal-based Approach: Inverted
Histogramizxiʼ is suffix sum of stream x1…xnnxi ' = ∑ x j
j =iz

Relative Error is bounded by dzTime cost:

z

Space
p
cost:

O(n log(nR ) log(1 + δ ))O(log(g(nR ) log(
g(1 + δ ))

Fractal-based Approach: Inverted
Histogramz

Histogram building procedure¾ When xn comes

1: increase bucket number B by
1
1;
¾ Add a new bucket
2: j ← B;¾ For all buckets from thelatesta totheoldest3: create
newbucketfor onex n;¾Update each bucket
5: add xn to both bia &¾Merge two consecutive bucketsbib ;¾ End For
6: If b b ≤ (1+ d)b a thenibjb ← bib ;

j

7:
8:
add width of bi to width of bj ;9:delete bi ;10: decrease bucket number B
by 1;

Fractal-based Approach:C
Conclusions
l i

A novel method for monitoring
aggregates of multi-granularity
windows over a data stream
Fractal analysis is introduced totransform the original data stream
to an intermediate one
I
Invertedd hihistogram iis adopteddd as
the core synopsis for ourmonitoring
it i
tasks
t k with
ith guaranteedt dspace and error

kNN monitoring[Böhm ICDE07][Böhm,

Two scenarios

 Network Monitoring Administrator specifies suspicious packages,gthesystem is constantly surveyed for similar packages
 Advertisement
 Users specify property of interested products or
news, the system informs users when new items fit
their requirementsrSimilaritylquery Range query K-NNK NN query

Basic idea skyline

B
A k=5

kNN monitoring: Object
M i t
Maintenance
Sk li
SkylinekNN monitoring: Object
D l i
Delaying

Approximate and exact skyline Buffer : size |B|, in life span order Exact skyline: stores skyline points fromapproximate skyline
 Approximatepp
skyline:ystores the address of skyline
ypoints in buffer

Buffer

kNN monitoring: Experimental
R
ResultsltOur Interests: Complex
p
data
JOS

SurveyFrequent pattern
Clustering,
Density estimate

CIKM

VLDB

DASFAA,WAIMDASFAA

JCRD

StreamsystemAggregate query

APWEB

IS
SDM,WAI
M,JCST

KAIS,IC
DE,JOSDASFAAFCSCDASFAA ICDE,
JOS

ICDE

ICDE

ICDE

ICDE

Complex Data
VLDB

Uncertainty
2003

2004

2005

2006

2007

2008

XML Streaming:ag Motivation [Gong, ICDE05]
Data
Producers<doc><tag> value </tag><doc></doc><tag> value </tag><doc></doc><tag> value </tag></doc>XML Packets

Router<doc><tag> value </tag><doc></doc><tag> value </tag><doc></doc><tag> value </tag></doc><doc>d<tag> value </tag></doc><doc><tag> value </tag></doc><doc><tag> value </tag><doc></doc><tag> value </tag><doc></doc><tag> value </tag><doc></doc></d ><tag> value </tag></doc><doc><tag> value </tag></doc><doc><tag> value </tag><doc></doc><tag> value </tag><doc></doc><tag> value </tag></doc>

Data
Consumers

XML Streaming: Content
R ti
Routing
Problem Each node is a router, which disseminates incoming XML

packets to its neighbors or users.
 EachE h router maintainii a route structure forf eachh user,which is used to determine if the XML packet will bematched by userʼs queries.
<bib><book>...
</bib>

Challenges

XML streams

Filter structures for its users and neighbors
 Large number of users and queries

 Changes of queries

Basic Idea

 Using bloom filter to build the route table

XML Stream Processing: Application
S
Scenarioi

DataConsumers

PublishData
Producers

RouterData
C
Consumers

Transform
RouterRouterRouterData
Consumers

Data
Producers
RouterPublish/subscribe systems,
systems monitor applications,applications content
content-routing
routing systems …

XML Stream Processing:
B k
Backgroundd

XML stream: a sequence of XML packets
packets, each ofwhich is an XML document or a fragment of XML
document
 A large XML document is also treated as a stream of

XML fragments (packets)

Applications

 Stock
St k andd sports
t ti
tickersk Traffic information systems

 Electronic personalized newspapers
 …

XML Stream Processing: Application
S
Scenarioi

DataConsumers

PublishData
Producers

RouterData
C
Consumers

Transform
RouterRouterRouterData
Consumers

Data
Producers
RouterPublish/subscribe systems,
systems monitor applications,applications content
content-routing
routing systems …

XML Stream Filtering: Application
S
Scenarioi

DataConsumers

PublishData
Producers

RouterData
C
Consumers

Transform
RouterRouterRouter<bib><book>...
</bib><bib><book>...
</bib>

Data
Producers

01001010

N1

11011001

N2

Data
Consumers
01110011
U
1

11000110

RouterU2<bib><book>...
</bib>

Routerroutermaintainsa routingtable
Publish/subscribe systems,
systems monitorEach
applications,applications
content
content-routing
routing systems…

XML Stream Filtering: Previous
S l tiSolutions

Autonoma-based
Autonomabasedtechnology
 Using an automata tob ld thebuild
h routing table,blwhich sharing theprefixes of all pathqueries.
i
 XFilter[AF00],
YFilter[DFF+02],[C G 02], XPush[GS03],
XTrie[CFG+02]…
Index-based technology
 Building an (start, end,
level) index on XML tagsfor each packet
 Evaluate path prefix tree
th i dXML Stream Filtering: YFilter vs.
I d Filt
IndexFilter

YFilter is more efficient than Index
Index-Filter
Filter when
the number of queries is large and the XML
packets are small.
Index-Filter is fit for large XML documents andlittle queries.

XML Stream Filtering: Bloom-filter
b
based
dM
Methodth d

An XML path query istreated as a query
string.
Using Bloom Filter tobuild the routing table.
A XML packetAn
k t isi parseddto generate a set ofcandidate paths.
pPrefix filters are used todecrease the number of
redundant candidate
paths.

Routing Table Construction: Bloom Filter based
vs YFilter
vs.

9

9

Bloom Filter-based is more efficient than Automata-based
when building routing table
The size of the routing table is much smaller when using
Bloom Filter-based
Filter based techniqueXML Packet Filtering: Bloom Filter based vs.
YFilter

99Bloom Filter-based technique can handle millions of pathqueries efficiently.
When the depth of the XML packet is no more 5, Bloom
Filter-based
Filterbased is efficient than Automata
Automata-based.
based.

XML Streama Filtering:g Summaryy
BothB
th highhi h accuracy and
d hi
high
h performancefcan be achieved by using Bloom-filterb
based
d approximateifilfilteringi
methodh dCurrent technique cannot efficiently
process complex XML packets (i
(i.e.
e XML
documents with large depth)Video Stream[Yan, ICDE08]

G l
Goal:

 Continuous Content-Based Copy Detection

over Streaming Videos

Motivation

 Copy right problem

 Originalgvideos may
y be edited with their frames

being reordered, to avoid detection VDBMS V.S. VDSMS

 Many concurrent video streams and many

continuous video copy monitoring queries.

Video Stream: System
I
Implementationlt ti
A hit tArchitectureVideo Stream: Key TechniquesF
Frame
FingerprintFii t
 Frame signature

extraction
 Dimension reduction

Similarity Measure

Min-hash techniqueVideo Stream: Subsequences
Comparison

Our Interests: Uncertaintyy
JOS

SurveyFrequent pattern
Clustering,
Density estimate

CIKM

VLDB

DASFAA,WAIMDASFAA

JCRD

StreamsystemAggregate query

APWEB

IS
SDM,WAI
M,JCST

KAIS,IC
DE,JOSDASFAAFCSCDASFAA ICDE,
JOS

ICDE

ICDE

ICDE

ICDE

Complex Data
VLDB

Uncertainty
2003

2004

2005

2006

2007

2008

Uncertain Stream: Definition[Jin, VLDB08]

76

Framework
GOAL: designing a general
GOAL
gene al frameworkf ame o k fo
for all kinds of top
topk queries,
not only for a special kind of query.
DesignCompact Set

List all UsefulCompact Sets

Compress
Compact Sets

1. W different windows. 1. CSQ, CCSQ, SCSQ,
1 A small subset of
1.
i.e., [t-j, t], for j=0..W-1 SCSQ-buffer
the original dataset
2. One compact set for 2. Space-efficient
2. Self-maintenanceeach window
3. Time-efficientC(D∪{t})⊆C(D)∪{t}
3. Capable of answering
a top-k query
Sliding-window Top-k Queries on Uncertain
Streams, VLDB 200877

Performance summaryySpaceconsumption

Processing time

Basic
i S
SynopsisiO( + kO(WkH))

O(kH2/W+logW)
O(k
/
l
)

Compact Set QueueO(H2logW)

O(kH2)

Compressed
Compact Set Queue

O(H(k+log W))

O(kH2)

Segmental Compact O(H(k+log W))
Set Queue

O(kH logW)

SCSQ-bufferO(kH2/W+logW)

O(H(k+log W))

Sliding-window Top-k Queries on Uncertain
Streams, VLDB 200878

Look ahead …
Q PProcessing
Query
XML document
filtering
Online XML documenttransformation
Execution andscheduling of multiple
jjoinsMining frequent items anditemsets

Synopsis maintenance andcountingti

Cluster analysis: Analyzing changes of frequency on
multi-dim’l spaces

Burst detection: Analyzing changes offrequency on 1-dim’l spaces
Data Analysis and MiningReferences[AF00][] Mehmet Altinel,, Michael J. Franklin: Efficient Filtering
g of XML Documents for Selective
Dissemination of Information, VLDB’2000[AHWY03] C. C. Aggarwal, J. Han, J. Wang, and P. S. Yu. A framework for clustering evolving
data streams. VLDB’2003.
[AMS96][] N. Alon,, Y. Matias and M. Szegedy.
g y The spacepcomplexitypy of approximatingpp
g thefrequency moments. STOC’1996[BGK+03] Nicolas Bruno, Luis Gravano, Nick Koudas and Divesh Srivastava: Navigation- vs.
Index-Based XML Multi-Query Processing. ICDE’2003[CCFC02][] M. Charikar,, K. Chen,, and M. Farach-Colton. Finding
g frequentqitems in data streams.
In Proc. of the 29th ICALP, 2002.
[CFG+02] C. Chan, P. Felber, M. Garofalakis, R. Rastogi: Efficient Filtering of XML Documentswith XPath Expressions, ICDE’2002[CM03]
[C
03] G
G. Co
Cormodeode a
andd S.Muthukrishnan.
S ut u s a What’s
at s hotot anda d what’s
at s not:ot Tracking
ac g mostost frequenteque titems dynamically. In Proc. of ACM PODS, 2003.
[DFF+02] Yanlei Diao, Peter Fischer, Michael Franklin and Raymond To: YFilter: Efficient andScalable Filtering of XML Documents. Demo paper. ICDE’2002[GMMO00] S. Guha, N. Mishra, R. Motwani, and L. O
O’Callaghan.
Callaghan. Clustering data stream.
FOCS’2000[GMO+03] Todd J. Green, Gerome Miklau, Makoto Onizuka, Dan Suciu: Processing XML
Streams with Deterministic Automata, ICDT 2003
[GS03] Ashish Gupta and Dan Suciu: Stream Processing of XPath Queries with Predicates.
SIGMOD’2003[HFAE03] M. A. Hammad, M. J. Franklin and W. G. Aref and A. K. Elmagarmid. In proc of
VLDB, 2003.

References (2003-2004)()[Zhou, DASFAA03] Aoying[Zh
A i ZhZhou, Zhi
Zhiyuan C
Cai,
i Li W
Wei,
i W
Weiningi i QiQian::
M-Kernel Merging: Towards Density Estimation over Data Streams.
DASFAA, 2003: 285-292[Jin, CIKM03] Cheqing Jin, Weining Qian, Chaofeng Sha, Jeffrey X.
Yu, and Aoying Zhou. Dynamically Maintaining Frequent Items over a
Data Stream. CIKM, 2003
[Jin, JOS04] Cheqing Jin, Weining Qian, and Aoying Zhou. The
A l i and
AnalysisdM
Managementgt off Str
Streamingi g Data:
D t :AS
Survey.
r(I(In Chi
Chinese))
Journal of Software (JOS), 15(8). 2004
[Yan, JCRD04] Ying Yan, Cheqing Jin, Feng Cao, Hengjie Wang,
Aoying Zhou, Load Shedding for Shared Window Joins over Data
Streams, Journal of Computer Research and Development, (inChinese), Vol. 41, No.10, 2004.
[Yu, VLDB04] Jeffrey Xu Yu, Zhihong Chong, Hongjun Lu, andA i g Zh
AoyingZhou. F
False
l P
Positive
iti orr F
False
l N
Negative:g ti : Mi
Miningi g FrFrequentt
Itemsets from High Speed Transactional Data Streams. VLDB, 2004

81

References (2005)()[Gong, ICDE05] Xueqing[GX
i Gong,G
Weining
W i i Qi
Qian, Yi
Ying YYan anddA
AoyingiZhou: Bloom Filter-based XML Packets Filtering for Millions of Path
Queries. ICDE’2005[Zh[Zhou,DASFAA05] Aoying
A i ZhZhou, Sh
Shoukek Qi
Qin, W
Weiningi i QiQian::
Adaptively Detecting Aggregation Bursts in Data Streams. DASFAA
2005: 435-446[Chong DASFAA05] Zhihong Chong,[Chong,Chong Jeffrey Xu Yu
Yu, Hongjun Lu
Lu,
Zhengjie Zhang, Aoying Zhou: False-Negative Frequent Items Mining
from Data Streams with Bursting. DASFAA 2005: 422-434[Xia WAIM05] Tian Xia[Xia,
Xia, Cheqing Jin,
Jin Xiaofang Zhou
Zhou, Aoying Zhou:
Filtering Duplicate Items over Distributed Data Streams. WAIM 2005:
779-784[Jin APWEB05] Cheqing Jin,
[Jin,
Jin Aoying Zhou: Distinct Estimate of Set
Expressions over Sliding Windows. APWeb 2005: 530-53582

References (2006)()[Qin, ICDE06] Shouke Qin[Qin
Qin, Weining Qian,
Qian Aoying Zhou: Approximately
Processing Multi-granularity Aggregate Queries over Data Streams. ICDE
2006
[Yu, IS06] Jeffrey Xu Yu, Zhihong Chong, Hongjun Lu, Zhenjie Zhang, Aoying
Zh : A ffalse
Zhou:
l negative
ti approachh tto mining
i i ffrequentt ititemsets
t ffrom hihighh speeddtransactional data streams. Inf. Sci. 176(14): 1986-2015 (2006)[Cao, SDM06] Feng Cao, Martin Ester, Weining Qian, Aoying Zhou: DensityBased Clustering over an Evolving Data Stream with Noise. SDM 2006
[Chong, JCST06] Zhihong Chong, Jeffrey Xu Yu, Zhengjie Zhang, Xuemin Lin,Wei Wang, Aoying Zhou: Efficient Computation of k-Medians over Data
Streams Under Memory Constraints. J. Comput. Sci. Technol. 21(2): 284-296(2006)[Zhou, DASFAA06] Yongluan Zhou, Ying Yan, Feng Yu, Aoying Zhou: PMJoin:
Optimizing Distributed Multi-way Stream Joins by Stream Partitioning.
DASFAA 2006: 325-341[Cao WAIM06] Feng Cao,[Cao,
Cao Anthony K
K. H
H. TungTung, Aoying Zhou: Scalable
Clustering Using Graphics Processors. WAIM 2006: 372-384[Qin, JOS06] Shouke Qin, Weining Qian, Aoying Zhou. Fractal-Based
Algorithms for Burst Detection over Data Streams. Journal of Software. Vol.
17 No.
17,No 9,
9 2006.
2006 (In Chinese)83References (2007)()[Zhou, KAIS07] Aoying[Zh
A i ZhZhou, F
Feng C
Cao, W
Weiningi i QiQian andd
Cheqing Jin. Tracking clusters in evolving data streams oversliding windows. In Knowledge and Information Systems: An
International Journal(KAIS Journal), Vol. 10, No. 3, March, 2007.
[Zhou, ICDE07] Aoying Zhou, Feng Cao, Ying Yan, Chaofeng
Sha, Xiaofeng He: Distributed Data Stream Clustering: A Fast
EM-based Approach. ICDE 2007: 736-745[Böhm, ICDE07] Christian Böhm, Beng Chin Ooi, Claudia Plant,
Ying Yan: Efficiently Processing Continuous k-NN Queries on
Data Streams. ICDE 2007: 156-165[Ji FCST07] Cheqing[Jin,
Ch i Ji
Jin, A
Aoyingi ZhZhou, JJeffrey
ff
X
Xu Y
Yu, JJoshuahZhexue Huang and Feng Cao. Adaptive scheduling for sharedwindow joins over data streams. Frontiers of Computer Sciencein China,, Vol. 01,, No. 04,, 2007
[Chang, JOS07] Jianlong Chang, Feng Cao, Aoying Zhou.
Clustering evolving data streams over sliding windows. Journalof Software, Vol. 18, No. 4, 2007 (In Chinese)84

References (2008)()[Yan, ICDE08] Ying Yan, Beng Chin Ooi, Aoying Zhou:
Continuous Content-Based Copy Detection overStreaming Videos
Videos. ICDE 2008: 853-862
853 862[Zhou, ICDE08] Aoying Zhou, Ying Yan, Xueqing Gong,
Jianlong Chang, Dai Dai:
Dai SMARTSMART: A System for Online
Monitoring Large Volumes of Network Traffic. ICDE
2008: 1576-1579 (demo)[Jin, VLDB08] Cheqing Jin, Ke Yi, Lei Chen, Jeffrey
Xu Yu, Xuemin Lin. Sliding-window top-k queries on
Uncertain Streams
Streams. VLDBVLDB, 200885

ThanksTh
k ffor YYour
Att ti !
Attention!

Q&A
86