Transcript Lazy Updates: An Efficient Technique to Continuously Monitoring

LAZY UPDATES: AN EFFICIENT TECHNIQUE TO
CONTINUOUSLY MONITORING REVERSE KNN
(PVLDB’09)
Presented By: Jing LI
Supervisor: Nikos Mamoulis
1
OUTLINE
Problem
& Motivation
Solution:
 Architecture
 Algorithm
Overview
 Pruning Rules
For Points (Related Works)
For Safe Regions

 Data
Structure
Experiments
2
PROBLEM & MOTIVATION

Nearest Neighbor Query (NN)


Find the object closest to q
Reverse Nearest Neighbor Query (RNN)
Korn et. al. Sigmod 2000
 Find objects s.t. q is their NN


Reverse k Nearest Neighbor Query (RkNN)

Find objects s.t. q is their kNN
3
p2are
is the
of q
p1 and p4
thenearest
reverseneighbor
nearest neighbors
of q
PROBLEM & MOTIVATION
Location
based games
Location based SMS advertising
Army strategic planning …
Continuous
Monitoring of RkNN
 Objects
are moving
 Query point is moving
4
SOLUTION: ARCHITECTURE
Server
 Maintain
the RNN for a query
 Send the result to the user
 Probe the exact locations of objects
Moving
Objects
 If
an object moves out of its safe
regions[1] , it sends an update message
of current location together with a
new safe region to the server
5
[1] If all objects stay inside safe regions, the solution remains the same.
ALGORITHM OVERVIEW

Initial Computation
Filtering: Determine candidates
Verification: Verify each candidate



Continuous Monitoring

Update candidate objects (filtering) if




Query or a candidate moves out of safe region, or
An object enters the unpruned area
The NN of a candidate object is changed
Verify all candidates
6
SOLUTION: PRUNING FOR THE STATIC RNN

Half-space Pruning [VLDB04]


Objects in the half-space
containing a can be pruned
Static RNN query
Filtering

Unpruned area
Repeat until no objects in
unpruned area
b
c

Verification

a
p is RNN iff no object p’ s.t.
q
dist(p,p’) < dist( p,q)
d
e
7
SOLUTION: PRUNING FOR CONTINUOUS RNN


Do filtering starting from the
existing “candidates” if
 Query moves, or Candidate
objects move, or
 An object moves into the
unpruned area or
 The NN of a candidate
object is changed
Continuous RNN query [ICDE07]
Unpruned area
b
c
a
Do verification
q
d
e
8
SOLUTION: FRAMEWORK

Moving objects are assigned
rectangular safe regions.



When an object moves out of its safe
region, it update its exact location
and a new safe region to the server
Easier to define pruning rules
b
c
Prune objects using safe regions
a

q
Advantages

Low Computation Cost

Low Communication Cost
d
e
9
HALF-SPACE PRUNING
– Any x on right side of LN :
• mindist(x,MN) = dist(x,N)
– Hp:N : the half-space
containing p and defined by
the bisector between p and N
mindist(x,MN) > dist(x,p)
LN
LM
x
p
– Any x on left side of LM :
• mindist(x,MN) = dist(x,M)
x
x
Hp:N
– Any x between LM and LN :
• a parabola with mindist(x,
MN) = dist(x,p)
M
q
Hp:M
N
10
HALF-SPACE PRUNING:
NORMALIZATION
– Frontier point Fp
– Moved to Fp, the intersection
of the half-spaces correctly
bounds the pruned area
Hp:M
– Hp:N passing Fp :
normalized half-space H’p:N
p
Fp
H’p:N
Hp:N
H’p:M
M
q
N
11
CHALLENGES
R
?
Q
12
HALF-SPACE PRUNING: PRUNING RULE
1
HM:B
HP:A
N
R
M
Fp
B
A
Q
D
E
O
P
H’N:E
H’M:B
H’O:D
H’P:A
Pairs of antipodal corners are (B,M), (A,P), (E,N) and (D,O)
13
TRIMMING THE RECTANGLE
R
RF2
RF1
Q
14
DOMINANCE PRUNING : PRUNING RULE
2
O
N
R
M
P
Fp
H’N:C
A
B
Q
D
C
H’M:B
H’O:D 15
H’P:A
METRIC BASED PRUNING : PRUNING RULE 3
R’
mindist(R’,Q)
R
maxdist(R,R’)
Q
16
ORDER OF PRUNING RULES

Cost: PR1 > PR2 > PR3

Pruning Power: PR1 < PR2 < PR3

Multi-level pruning strategy

PR3 PR2PR1
17
ORDER OF PRUNING RULES: A EXAMPLE
R3
R1
RF
R2
Fp
Q
18
ILLUSTRATION OF FILTERING
O7
O5
O6
O3
O2
Q
O1
O4
19
ILLUSTRATION OF VERIFICATION
O7
O6
O5 O 5
O6
?
O3
O3
O2
O2
Q
Q
O1
O1
O4
20
DATA STRUCTURE

Query table : id, safe region, candidate objects

Object table : id, safe region
 Use
grid data structure to support update
 Each


cell c of the grid :
Object list : objects whose safe regions overlap c
Influence list : queries whose unpruned area
overlaps c
21
EXPERIMENT SETTINGS
• Generate Moving objects and queries using Brinkhoff Generator [1] on
road map of Texas
• Data space : 1000 Km X 1000 Km
• Our algorithm (SAC) is compared with IGERN [2] for RNN queries and
CRkNN [3] for RkNN queries
[1] T. Brinkhoff. A framework for generating network-based moving objects. GeoInformatica, 2002.
[2] J. M. Kang, M. F. Mokbel, S. Shekhar, T. Xia, and D. Zhang. Continuous evaluation of
monochromatic and bichromatic reverse nearest neighbors. ICDE, 2007.
[3] W. Wu, F. Yang, C. Y. Chan, and K.-L. Tan. Continuous reverse k-nearest-neighbor monitoring. 22
MDM, 2008
Evaluation of pruning rules
Avg. time for
PR3 : 1.1 µs ( metric based pruning rule
)
PR2 : 2.3 µs ( dominance pruning rule
)
PR1 : 10.5 µs ( half space based pruning rule )
23
EXPERIMENTS: SIZE OF SAFE REGION
24
EXPERIMENTS: NUMBER OF OBJECTS
IGERN : ICDE 2007 work for RNN
SAC : Our algorithm
25
EXPERIMENTS: EFFECT OF DATA
MOBILITY
• Data mobility is the percentage of objects/queries that change their
location within one time unit
26
Conclusion
 Study the problem of continuously monitoring
reverse kNN
 Propose a new framework based on safe
region
 Outperform previous algorithms in terms of
computation cost and communication cost
Drawback:
We can assign large safe regions to the
objects that are far away from a query point.
27
Thanks
28
EXPERIMENTS: RKNN QUERIES
CRkNN : MDM 2008 work for continuous monitoring RkNN
SAC : Our algorithm
34