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

Implementation and Evaluation of
an Adaptive Neighborhood
Information Retrieval System for
Mobile Users
Yoshiharu Ishikawa
Yuichi Tsukamoto
Hiroyuki Kitagawa
University of Tsukuba, Japan
Dec. 13, 2003
W 2GIS2003@Rome
Overview






Background and Overview
Neighborhood Information Retrieval Method
Design and Implementation of the Prototype
Experimental Result
Demo
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
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
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
Overview


Background and Overview
Neighborhood Information Retrieval Method






Influence model of trajectory points
Query derivation model
Design and Implementation of the Prototype
Experimental Result
Demo
Conclusions and Future Work
Representation of Location
Information

Locations of a moving object:
t 1
: departure time
: current time
t 
t     : estimated arrival time
 x x 
x 1
 
x  2

 x
x1 2
current point

x  
destination
start point
Assumption:
past/future trajectory points are given in unit-time basis
Influence Model of Trajectory
Points (1)


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
Influence Value
m  s t (t  1, ...,   s )
 (t )   t  s
n
(t    s , ...,    )
m
1
m

τ+σ－2
n
n

τ+σ
τ+σ+2
τ+σ+1
τ+σ－1
time
Influence Model of Trajectory
Points (2)

Influence value for each point when s = 1
n’-2
m
m
 x
x 1
m
m 
 x2
x1
start point
 n
x  
x  2

x 3
current point
n
highest weight point
since s = 1
n’-1


x  1 x  
destination
Overview


Background and Overview
Neighborhood Information Retrieval Method





Influence model of trajectory points
Query derivation model
Design and Implementation of the Prototype
Experimental Result
Conclusions and Future Work Background and
Overview
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

Model cur: set the point with the highest
importance to the query center
q  x s

Model avg: weighted average based on influence
values
  
 (t ) xt

t 1
q
  
x +'

(
t
)
t 1
x +s
x
current position
x
1
avg
cur
Derivation of Distance Function (1)


Model EU: Euclidian distance-based model
Model OV: ellipsoid distance-based model
D ( x, q)  ( x  q) A( x  q)
2


T
derive a distance matrix A that reflects the sample
point [9]: extended Maharanobis distance
adaptive, but not robust
A  (det(C))1 d C1
  
T
C  t 1  (t ) xi  q  xi  q 
C is the weighted covariance matrix
q
Derivation of Distance Function (2)

Model HB: hybrid model


integrates the benefits of EU and OV models
incorporation of hybrid parameter 

 1
A  (det(C )) (C )
1d
C
I
C 
 (1   )
C
I
0    1 I : unit matrix

C
becomes an regular matrix
regularization
Overview






Background and Overview
Neighborhood Information Retrieval Method
Design and Implementation of the Prototype
Experimental Result
Demo
Conclusions and Future Work
System Architecture
GUI
position &
map data
外部
モジュール
route
info
Tracking
Analyst
GPS events
map data
GPS
position
data feeding
parameter
values
query
result
start
point &
destination
route
Query
info
query
Generation &
invocation Execution
with event
data
query
query
result Route
Calculation
ArcView
Module
map data & data items
GUI
Parameter Setup
Dialog Box
Current Position
qualified items
Map & Query Result View
Result Table
Overview






Background and Overview
Neighborhood Information Retrieval Method
Design and Implementation of the Prototype
Experimental Result
Demo
Conclusions and Future Work
Experiment Set-up

Query task



Driving route



continual k-nearest
neighbor queries (k = 5)
query is issued every 5
seconds
Tsukuba city, Japan
5km driving
Target data


200 items
POI (Point Of Interest)
along the route: gas station,
shops, schools, ...
Evaluation Measure

Evaluation is based on (extended) precision scores


Ideal retrieval result set



for each movement point, precision score is calculated
for each movement point, we have constructed "ideal" ranking of
neighborhood data items
simulates "ideal" user's behavior
Precision formula
| Res(k )  Ans( p) |
| Res(k ) |
| Res(k )  Ans( p) |

k
Res(k): top-k objects ranked by the system
Ans(p): top-p objects based on "ideal" ranking
Precision(k , p) 


Evaluation Results

Overview of the Result





On distance derivation models: EU < OV < HB
 ellipsoid distance-based approach is better in general
On query center generation models: cur > avg
 selecting the current position as the query center is better than the
averaging approach
On past & future parameter settings
 moderate biased weighting (m = 0.4, n = 0.8) was the best
On hybrid parameters
 moderate setting ( = 0.9) was the best
Recommendation

Use HB & cur with appropriate parameter settings
Overview






Background and Overview
Neighborhood Information Retrieval Method
Design and Implementation of the Prototype
Experimental Result
Demo
Conclusions and Future Work
Demo
Overview






Background and Overview
Neighborhood Information Retrieval Method
Design and Implementation of the Prototype
Experimental Result
Demo
Conclusions and Future Work
Conclusions and Future Work

Conclusions




Neighborhood retrieval system for moving objects
 Based on ellipsoidal distance
 Introduction of influence decay model of trajectory points
 Proposal of spatial query generation models
Prototype system
 ArcView & Tracking Analyist
Experimental result
 precision-based evaluation
Future work


Use of more detailed information on road & spatial objects
Use of large spatial datasets

Download Report