移動オブジェクトに対する最近傍問合せ

Continual Neighborhood Tracking
for Moving Objects
Using Adaptive Distances
Yoshiharu Ishikawa
Hiroyuki Kitagawa
Tooru Kawashima
University of Tsukuba, Japan
{ishikawa,kitagawa}@is.tsukuba.ac.jp
Organization






Background and Overview
Our Approach
Experiments
Query Processing with Spatial Indexes
Incremental Query Update
Conclusions and Future Work
Background



Progress of Digital Cartography
Development of GPS Technologies
Wide Use of PDA and Hand-held Devices
New Types of Information Services: Providing
neighborhood information to moving objects (people
with PDAs, cars with navigation systems) considering
their locations and trajectories
Motivating Example (1)
Neighborhood Query:
A user at point x wants
to find nearby gas stations
x
Typical Approach:
retrieve gas stations
with their distances less
than 200 meters from x
A spatial query based on
the Euclidean distance
Motivating Example (2)
What’s Wrong?
If we know user’s past
and future trajectories,
we can provide more
appropriate information
A
past trajectory
future trajectory
Our Idea (1)


A

Use of an ellipsoid
region to represent a
neighborhood query
An ellipsoid region
is computed based
on the past/future
trajectories
A neighborhood
query is specified as
a spatial query with
an ellipsoid distance
Our Idea (2)
initial
start query
point
parameters
destination
: Data objects
: sampled estimated
positions of the
moving object
Neighborhood Info
Retrieval System
destination


start point

Sample positions are
taken by unit-time basis
At each sample position,
a spatial query is
generated
The system perform
queries continuously
Problems and Solutions
How can we generate appropriate spatial
queries?



Introduction of influence model of trajectory points
Proposal of query derivation models
How about efficiency?



Use of spatial indexes for efficient query processing
Low-cost query update procedure for continuous
queries
Organization


Background and Overview
Our Approach






Influence model of trajectory points
Query derivation model
Experiments
Query Processing with Spatial Indexes
Incremental Query Update
Conclusions and Future Work
Representation of Location
Information (1)

Object locations are represented by d-D vectors
xi  [ xi1,...,xid ]
T
d : no. of dimensions
Representation of Location
Information (2)

Locations of a moving object:
: departure time
t 1
: current time
t 
t     : estimated arrival time
 x x 
x 1
 
x  2

 x2
x1
current point

x  
destination
start point
Assumption:
past/future trajectory points are given in unit-time basis
Influence Model of Trajectory
Points (1)

current
position
We usually set high
importance on
current neighborhood
points
Influence Model of Trajectory
Points (2)

current
position
A user may be
interested in near
future neighborhood
where he or she will
arrive soon
Influence Model of Trajectory
Points (3)


The influence model sets the highest weight “1” on
location information at time t =  + s (s unit times after
the current time )
The influence values decay exponentially towards past
and future with parameters m and n, respectively
m s t (t  1, ...,   s )
 (t )   t  s
n
(t    s , ...,    ) m
m

τ+σ－2
Influence Value
1
n
n

τ+σ
τ+σ+2
τ+σ+1
τ+σ－1
time
Influence Model of Trajectory
Points (4)

Influence value for each point when s = 1
n’-2
m
m
m 
 x2
x1
m


 x x n
x 1
 
x  2

x
 3
current point
start point
n
highest weight point
since s = 1
’-1
n


x  1x  
destination
Organization


Background and Overview
Our Approach






Influence model of trajectory points
Query derivation model
Experiments
Query Processing with Spatial Indexes
Incremental Query Update
Conclusions and Future Work
Query Derivation Model


Neighborhood queries for moving objects are issued to a
spatial database
A spatial query is fixed specifying
 query center q


distance function D


two models (cur, avg)
three models (EU, OV, HB)
D
query task

range query and k-nn query
q
Derivation of Query Centers (1)

Model cur: set the point with the highest
importance to the query center
q  x s
query center q
x x
 s
x1
current
position
x  
Derivation of Query Centers (2)

Model avg: weighted average based on influence
values



  
q

(
t
)
x
t
t 1
 

(
t
)
t 1
Setting of parameters m and n
changes the query center
x1
x
current
position
x  
query center q
Query Derivation Model


Neighborhood queries for moving objects are issued to a
spatial database
A spatial query is fixed specifying
 query center q


distance function D


two models (cur, avg)
three models (EU, OV, HB)
D
query task

range query and k-nn query
q
Distance Function Derivation
Models (1)

Model EU: Euclid distance-based model
D ( x, q)  ( x  q) ( x  q)
2
Pros
- simple and intuitive
- easy to compute
Cons
- do not consider past/future
- trajectory information
T
q
q
Ellipsoid Distance
D ( x, q)  ( x  q) A( x  q)
2
T
Appropriate setting of the distance
matrix A allows flexible
tuning of distances
q
We derive an appropriate matrix
A using past/future trajectory
information
Distance Function Derivation
Models (2)

Model OV: ellipsoid distance-based model
  
M  min  (t )( xt  q) A( xt  q)
T
A
t 1
derive a distance matrix M that reflects the sample point
distribution nearby the query point [19]
q
M  (det(C))1 d C1
  
T
C  t 1  (t)xi  qxi  q
C is the weighted covariance matrix
q
Distance Function Derivation
Models (3)

Model OV: ellipsoid distance-based model

pros


allows retrieval along the trajectory since the derived
distance is an extended version of the Mahalanobis
distance [8, 20]
cons: not robust compared to the Euclidean
distance

When an object is moving along a straight line or
staying in some place, the matrix C becomes an illconditioned matrix: therefore, we cannot derive the
distance matrix M!
Distance Function Derivation
Models (4)

Model HB: hybrid model

integrates the benefits of EU and OV models
~ 1
M  (det(C )) (C)

1d
C
I
~
C
 (1   )
C
I
0    1 I : unit matrix
~
C
becomes an regular matrix
regularization
Query Derivation Model


Neighborhood queries for moving objects are issued to a
spatial database
A spatial query is fixed specifying
 query center q


distance function D


two models (cur, avg)
three models (EU, OV, HB)
D
query task

range query and k-nn query
q
Query Task (1)

Range Query: At each point,
retrieve objects within
distance e
ε
q
Query Task (2)

k-Nearest Neighbor
Query: At each point
retrieve nearest k objects
when k = 3
q
Organization






Background and Overview
Our Approach
Experiments
Query Processing with Spatial Indexes
Incremental Query Update
Conclusions and Future Work
Experiment 1: Observation of
Behaviors



Query generation
example for the
trajectory (blue line)
Target points are
shown in green points
Queries are generated
based on the hybrid
model
Experiment 1 (1)

Comparison of Euclidean distance and ellipsoid
distance
x
Experiment 1 (2)

Set the “near future” point as query center
initial parameters
σ= 0 , μ=0.5
ν=0.5, λ= 1.0
y
x
modified parameters
σ= 5 , μ=0.4
ν=0.4, λ= 1.0
Experiment 1 (3)

Set high weights on future trajectory
initial parameters
σ= 0 , μ=0.4
ν=0.4, λ= 1.0
x
refined parameters
σ= 0 , μ=0.4
ν=0.9, λ= 1.0
Experiment 1 (4)

Use of the regularization parameter 
initial parameters
σ= 0 , μ=0.4
ν=0.4, λ= 1.0
x
refined parameters
σ= 0 , μ=0.4
ν=0.4, λ= 0.7
Experiment 2: Simulation Based
on Trace Data (1)

Car driving trace data is used to compute queries
Experiment 2: Simulation Based
on Trace Data (2)

Each isosurface represents the query generated at the
point
Organization






Background and Overview
Our Approach
Experiments
Query Processing with Spatial Indexes
Incremental Query Update
Conclusions and Future Work
Query Processing Based on
Spatial Indexes

Most of spatial indexes do not support ellipsoid
distance-based queries

We extend the approach of Seidl & Kriegel [30] to
support ellipsoid distance-based queries with
conventional spatial indexes
Assumptions: only three generic retrieval functions
are supported by the underlying spatial indexes

Generic Retrieval Functions (1)

rect_search(r):
retrieve objects within
the specified rectangle
region r
r
Generic Retrieval Functions (2)

dist_search(q, e):
retrieve objects within
distance e from q using
the Euclidean distance
e
q
Generic Retrieval Functions (3)

knn_search(q, k):
retrieve nearest k objects
from the query center q
using the Euclidean
distance
q
Minimal Bounding Box (MBB) for
Ellipsoid Isosurface [30]

MBB that tightly encloses the ellipsoid ellip(M, q, e)
j-th dimension ellip(M, q, e)
q j  e Mjj1
1
:
ii
M
q
(i, i) element of
the inverse of M
q j  e Mjj1
i-th dimension
qi  e Mii1
qi  e Mii1
Minimal Bounding Sphere (MBS)
for Ellipsoid Isosuraface [30]

MBS that tightly encloses the ellipsoid ellip(M, q, e)
e
min
q
ellip(M, q, e)
min: the smallest
eigenvalue of M
Query Processing (1)

Range query processing with MBB
approximation
e
q
Query Processing (1)

Range query processing with MBB
approximation
e
q
Query Processing (2)

k-NN query (k = 3)
q
Query Processing (2)

k-NN query (k = 3)
q
1. Perform k-NN query
based on the Euclidean
distance
2. Derive an ellipsoid that
tightly encloses k-NN
objects
3. Perform a range query
with MBS (or MBB) that
tightly encloses the
ellipsoid region
4. Select nearest k objects
from the retrieved objects
using the ellipsoid distance
Experiment: Retrieval I/O Cost
with Spatial Indexes (1)

I/O cost evaluation using R-tree
(GiST)



I/O costs are compared for



Target dataset (green points):
39,226 crossroad points of
Maryland County in U.S.
Query: 62 blue points along the
road
sequential scan
ellipsoid distance query with the
support of spatial indexes
k-NN (k = 1, 10, …, 150) results
are shown
Experiment: Retrieval I/O Cost
with Spatial Indexes (2)

Average page I/O cost per query
Organization






Background and Overview
Our Approach
Examples
Query Processing with Spatial Indexes
Incremental Query Update
Conclusions and Future Work
Query Update

In each query point, a slightly different query is
generated


The query center and the distance function will change
Naïve update strategy


Derive the query center and the distance function from
scratch
The generation cost is quite large


It requires calculation from past/future trajectory
information
Can we update queries incrementally?

Answer: Yes, but periodic reorganization is required
Incremental Query Update (1)

Basic Idea



Decompose statistics used to generate a query into past
part and future part
At each update, make “one step shift” from the future
part to the past part
Exponential decay factors allow a simple and efficient
procedure
Incremental Query Update (2)

Example: Incremental update of query center for
model avg

Decompose x| as
s-  s
x|τ 
w |
 s
s  |   m  s t xt
t 1
s  | 
  '
t  s
n
xt

t  s 1
Incremental Query Update (3)

Then update using the following formulas
s  | 1  ms - |  x s 1
1 

s | 1  s |  x s 1
m
s  | 1  s  | 1
x | 1 
w | 1

We can make an incremental update for
covariance matrix (C) in a similar manner
Incremental Query Update (4)


Incremental query update procedure allows constant
update cost for fixed dimensionality d
Bad news: two problems



A moving object may reach early or late to the next point.
Moreover, it may change the estimated route.
A number of incremental updates will result in incorrect
query generation since the proposed incremental update
procedure amplifies the noise.
Practical update procedure

Use incremental update procedure for short period and
recalculate statistics periodically
Organization






Background and Overview
Our Approach
Examples
Query Processing with Spatial Indexes
Incremental Query Update
Conclusions and Future Work
Conclusions

Generation of Neighborhood Tracking Queries
Based on Adaptive Distances (Ellipsoid
Distances)




Introduction of Influence Decay Model of Trajectory
Points
Proposal of Spatial Query Generation Models
Efficient Query Evaluation with Spatial Indexes
Query Update Method for Continual Query
Processing
Future Work



Development of parameter set-up method that
considers query workloads and query tasks
Use of previous query results (cached results) for
efficient continual query processing
Development of Prototype System
Prototype System
Under
development
on top of
ArcView GIS
Support of
dynamic
location feeding
from GPS

Download Report