Processing windowed Top-k
Q i on UQueries
Uncertaini SStreams
Cheqing Jin 金澈清 cqjin@ecust.edu.cn
cqjin@ecust edu cn
East China Normal University, Shanghai,China
華東師范大學上海 中國

Outline Introduction

Top-k queries
 contribution
 Our solution
 Experiments
 Conclusion

2

Possible World Model
A small record setof reading logs

IDSpeed(*10)

Prob.

1

50.8

If we ignore the2probability field,field the3semantic of top-k query4
is very clear.
16 possible worldinstances
Tuples60.5

8040.4

20.4Pr.

TuplesPr.

TuplesPr.

8, 6, 5, 2.064

8, 6, 5.096 8, 5, 2.064

8 5
8,.096096

8 68,6, 2.016
016 8,8 6.024
024

8, 2.016

8.024 6, 5, 2.096

6 5
6,.144

6 2
6,.024 6.036

5, 2.096

5.144 2.024

Empty.036

0.096 = 0.4 * 0.8 *(1-0.5) * (1-0.4)

0.036=(1-0.8)*(10.5)*(1-0.4)*(1-0.4)

3

Windowed Model on Uncertain Streams
time
Assume W=31234567887293561At time 3
3, possible worlds are:

87

2

72

8

7

8

7

2

8

2

At time 4,, possible
pworlds are:

97

2

7

2

9

7
7

9

2

9

2

Obviously, when a new tuple arrives, half of possible worlds will change.
4

Uncertain Top-kp qqueries
U T k [4]
U-Top




U-kRanks [4]returns the top-k tuples in all possible worlds withmaximum probability.
py
returns the winner for the i-th rank for all 1 ≤ i ≤ k.

PT-k [2]returns all the tuples with maximum aggregate
probability greater than a user-given
user given threshold p aggregate probability: the prob. of being the top-k
among all.

Pk-Top
Topk [this paper]
returns the k most probable tuples of being the top-k
among all.
 A slight
li h modification
difi i off PT
PT-k, while
hil without
ihthresholdhh ldp.


5

Examplep ((k=2))
16 possible
ibl worldld
instances

Query results
QueryTuples

Pr.

TuplesPr.

TuplesPr.

8 6,8,
6 5,
5 2.064064

8 6,8,
6 5.096096

8 5,8,
5 2.064064

8, 5.096

8, 6, 2.016

8, 6.024

8, 2.016

8.024

6, 5, 2.096

6, 5.1446, 2.024

6.036

5, 2.096

5.144

2.024

Empty.036
036

U-kRanks

PT-kU-Topk

Pk-Topk(p=0 3)(p=0.3)Result{6, 5}{8, 5}{5, 6, 8}{5, 6}

Claim: our goal is not to propose yet another new top-k query
definition, but a new framework that all top-k queries canbe processed in the sliding window model.
6

Contributions
Contribution:

However, Sliding-window
solutions on uncertain
streams[Still None]

Uncertain Data
processing[Lots of work]

Ours is the first work
In this area, especially for
Top-k queries!

Sliding window
Slidii d[A lot]
Uncertainstream
processing[quite A fewrecently]

Streamprocessing[[Lotsoff work]k]7

Workingg modelIn the ultimate situation, all tuples in the window
must be saved in memory!


ExampleEl
ti: the i-th tuple in stream, (value:1/i, probability:1/i).
The window size is W, at time n, for any k, tuple tn-W+1 is at thequery result of Pk-Topk query.
So, worst-case bounds are trivial and meaningless.

So, we consider a more general scenario: random
order stream model.
The value and probability of a tuple are both randomly andindependently drawn from some (arbitrary) distribution.
8Naïve solution
 Basici SSynopsisi ((BS)
S)

Reserve all recent W tuples in memory
 Use traditional method to answer top-kqueries Analysis

Time-efficient, but space-inefficient.
 The space complexity is O(W).
9Framework
GOAL: designing a general framework for all kinds of toptop-kk queriesqueries,
not only for a special kind of query.

Design Compact
Set

List all UsefulCompact Sets

1 A small subset of
1.
1. W different windows.
1windows
the original dataseti.e., [t-j, t], for j=0..W-1
2. Self-maintenance
2. One compact set foreach window
C(D∪{t})⊆C(D)∪{t}
3. Capable of answering
a top-k query

Compress
Compact Sets

1 CSQ,1.
CSQ CCSQ,CCSQ SCSQ,SCSQ
SCSQ-buffer
2. Space-efficient
3. TimeTime-efficientefficient

10

Example:p Compact
p Set for Pk-Topkp


Symbols
Sb l
1.
Di: the subset of D containing the first i tuples in D.
2.
ri,j: the probability that a randomly generated world from Di hasexactlyl j tuples.
l
1.

3.
4.

5.

6.



ri,j can be maintained through dynamic program.

p(ti): the probability of tuple ti.
p(ti)ri-1,j-1: theh probability
b bili thath ti ranks
k theh jj th
h in
i a randomly
d lgenerated world from D.
p(ti)Σi=1..kri-1,j-1: the probability that ti ranks top-k in all possible
worlds generated from D.
DΣi=1..kri-1,d-1: The up-bound probability of any other tuple outsideof Dd that ranks top-k in all possible worlds generated from D.

Compact set for Pk-Topk
 Smallest Dd with k tuples (ta) satisfying: p(ta)Σi=1..kri-1,a-1 > Σi=1..kri1,d-1
11

Possible sub-windows Assume window size

W=8, k=3

time 1

2

3

4

56

7

8

8

7

2

93

5

6

1

56

1

3

56

1

9

3

56

1

2

9

3

56

1

72

9

3

56

1

72

93

561

910

1112

13

Possible sub-windows
[6,8]
[5,8]
[4,8][3,8]
[2,8]
[1,8]

8

Create a compact
pset for each
sub-window!

12Create compact
p setstime

123456788

72

93561561565

6[6,8][5 8][5,8]

3[4,8]

9Duplicate!
p[3,8]

9[2,8]
[1,8]

8

5

6

7

96

7

9

Goal: Compress theremaining compact sets.

13

Synopsisy p (1):( )Compact Set Queue

time

182

73

2

4

95

3

6

5

[5,9]
[5,8]

3[4,9]
[4,8]

99

1

46145614565642. Generate a2
new compact set

3. Updatecompact sets
6. Duplicate
pruning
4. Compact setsare unchanged

[3,8]
[3,9]
[2,8]
[2,9]
[1 8]
[1,8]

8

6

[7,9]
[6,9]
[69]
[6,8]
8]

7

1. A new tuple
arrives

8

7

9

7

9

6

5. Remove
Compact set if
expired14

Compact
p Set Q
Queue: AnalysisyAdvantages
Easy to understand The space consumption and the per-tuple processing
cost are small.


Disadvantages


Redundancy exists between neighbor compact setssets.

S l iSolution
compress neighbor compact sets!
15Synopsis
y p (2):( )Compressed Compact Set Queuetime12345678

9872935614561456

3. Process tuple 556

4. Process tuple 36

2. Maintain acompact set.

[[6,8], ]
[5,8]

3

[4 8]
[4,8]

9

[3,8]
[2,8]
[[1,8], ]1. A new tuple
arrives, reserve
it in CCSQ

88

7

97

97

9

6. Remove
expired tuple 8

5. State after
processing tuple 73561416

CompressedpCompactp Set Q
Queue: Analysisy

AdAdvantagesDisadvantagesThe space consumption is reduced.

Lots of compact sets must be generated and checked
for each incoming tuple, which results in high pertuple processing cost.

SolutionGroup neighbor
Gi hb compact sets!!
 In fact, it’s the combination of CSQ and CCSQ.
17

Synopsisy p (3):( )Segmental Compact Set Queuetime

12

3

4

5

6

7

8

98

72

93

5

6

1

4

5. Generate anew SCS
RULE: Sum of the affiliatedtuples in two neighbor[6 8] compact sets is smaller than k
[6,8]

[5,8]
[4,8]4. Remove
expired tuple

396

1456

145656

2. update2compact sets

3. Duplicate
pruning

6. merge

[3,8]
[2,8]
[1 8]
[1,8]

4

1. A new tuple
arrives87979618

Segmental
gCompact
p Set Q
Queue: Analysisy

Advantages
Low space consumption.
 Low per-tuple processing cost.
Disadvantages
Some medial compact sets are unnecessary to be
maintainedi i d per tuple.
lSolution
Use a buffer!
19

Synopsisy p (4):( ) SCSQ-bufferQ
 Basic structure contains:

A buffer with size kH to reserve new tuples
 A SCSQ for all tuples except the buffer A compact set C(SW) for query result When a tuplet arrives

IInsert t intoiB remove out-of-date tuples in SCSQ ifpossibleibl
 If B is full, update SCSQ with B;
 Else, update C(SW);20

SCSQ-buffer
QSCSQbuffer

The state at time tDuring [t+1, t+12],
1. Fill buffer till full,
2 Remover expired
2.
tuples in SCSQThenThen,Update SCSQ,Clear buffer21Performance summaryy
SpaceconsumptionProcessing time

Basic Synopsis

O(W + kH)O(kH2/W+logW)

Compact Set
Queue

O(H2logW)

O(kH2)

Compressed
Compact Set
QQueueO(H(k+log W))

O(kH2)

Segmental
Compact Set
Queue

O(H(k+log W))

O(kH logW)

SCSQ-buffer

O(H(k+log W))

O(kH2/W+logW)22

Experimentsp

Dataset:Dtt: IInternationalt
til IIce P
Patrolt l (IIP) IIcebergbSightings Database
informationo at o oon iceberg
cebe g activity
act v ty in Northo t Atlantict a t c tomonitor iceberg danger near the Grand Banks Sighting signals



R/V (radar and visual) – 0.808
VIS (visual only) – 0.7
RAD(radar only) – 0.6
SAT LOW(low earth orbit satellite) – 0.5
SAT-LOW(low05
SAT-MED (medium earth orbit satellite) – 0.4
SAT-HIGH (high earth orbit satellite) – 0.3
EST ((estimated,id useddbbeforef2005) – 0.4
04

we created a 1,000,000-record data stream by
repeatedly selecting records randomly.
23Spacep consumption
p24Per-tuple
p pprocessingg cost25

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

26

Myy idea to produce
pa goodgpaper:p p——Doing as much as possible
Find a valuable
problemApplication arguable?

Hard to sell

Keep working

Get a basic idea
Keep working

Doing more
extended
workworking
andKeepexperiments
Improve writing skill,
Reorganize contents,
Add examples

Write it downwith simple experiments
Submit it now

At most asmallllpaperApotential
goodpaper
A qualifiedpaper27

Conclusion
Conclusion
We propose a general framework to process Slidingwindow
i dTTop-kk queries
i on uncertaint i streams.
t Support U-Topk, U-kRanks, PT-k, Pk-Topk.
 Our work is the first work in processing slidingwindow queries on uncertain streams.
28

Future work Handle other kinds of queries with thisframework
 Handle more complex uncertain models,such as with constraints?
 Attribute level uncertainty?
 Using probability density function?
 Distributed uncertain stream?
 From top-k to NN query, range query, orskyline query?
29

Reference ((uncertain top-kp qqueries))[1] J.
J ChenCh andd K.
K Yi.
Yi Dynamic
Di structurestt
ffor ttop-k
k queries
ion uncertain data. In Proc. of ISAAC, 2007.
[2] M. Hua, J. Pei, W. Zhang, and X. Lin. Efficiently answering
probabilistic threshold top-k
top k queries on uncertain data
data. In
Proc. of ICDE, 2008.
[3] M. Hua, J. Pei, W. Zhang, and X. Lin. Ranking queries on
uncertain data:
data A probabilistic threshold approach. In Proc. ofSIGMOD, 2008.
[4] M. A. Soliman, I. F. Ilyas, and K. C.-C. Chang. Top-kquery processing in uncertain databases. In Proc. of ICDE,
2007.
2007
[5] K. Yi, F. Li, G. Kollios, and D. Srivastava. Efficient
processing of top-k queries in uncertain databases. In Proc. ofICDE, 2008.
2008

30

Reference ((uncertain stream processing)
pg)










[6] C.
C C.
C Aggarwal
Al andd P.
P S
S. Y
Yu. A fframework
k ffor clusteringli
uncertain data streams. In Proc. of ICDE, 2008.
[7] G. Cormode and M. Garofalakis. Sketching probabilistic
data streams. In Proc. of ACM SIGMOD, 2007.
[8] T. Jayram, S. Kale, and E. Vee. Efficient aggregation
algorithms for probabilistic data. In Proc. of SODA, 2007.
[9] T. Jayram, A. McGregor, S. Muthukrishnan, and E. Vee.
Estimating statistical aggregates on probabilistic data
streams. In Proc. of PODS, 2007.
[10] C. Jin, K. Yi, L. Chen, Jeffrey X. Yu and X. Lin. Slidingwindow top-k queries on uncertain streams. In Proc. Of
VLDB, 2008[11] Q. Zhang, F. Li, and K. Yi. Finding frequent items inprobabilistic data. In Proc. of SIGMOD, 2008.

31

Questions?

Thanks.
Thanks