Processamento de Consultas
Espaciais Baseado em Cache
Semântico Dependente de Localização
Heloise Manica
Murilo S. de Camargo
Cristina Dutra de Aguiar Ciferri
Ricardo Rodrigues Ciferri
Novembro, 2004
1
Contents
Background
Goal and Motivation
Related Work
Location-Dependent Semantic Cache
Spatial Query Processing
Semantic Segment Formation and Reorganization
Conclusion and Future Work
2
Background
Mobility has opened up new classes of applications such as
Location-Dependent Information Service (LDIS).
A location dependent query (LDQ) is a query that is processed
on location dependent data, and whose result depends on the
location criteria explicitly or implicitly specified (Ren and
Dunham,2000).
Example:
“Find
the
restaurants
within
3
miles
from
my
position”
(implicit location)
3
Goal and Motivation
Managing data in LDIS faces challenges (Lee et al., 2002):
Low-quality communication;
Frequent network disconnections;
Limited local resources.
Advantage of caching model for mobile computing:
Wireless network traffic cost down;
System performance up;
Reduce power consumed with server communication;
Improve data availability in case of disconnection.
4
Goal and Motivation
Main goals:
Propose a new semantic cache model for LDIS based on
relationship between the data and its geographical location;
Connects spatial database and mobile computing to location
dependent query processing;
Propose a solution for semantic segments management and
reorganization.
5
Related Work
Dunham and Kumar (1998) and Lee et al. (2002) introduced
the concept of location dependent data and present new
research issues.
Zheng et al. (2002) and Xu et al. (2003) studied cache
management issues for location dependent data under
geometric and cell-based model respectively.
Dar et al. (1996) were the first to use the semantic model with
distance function. Their replacement policy discard semantic
regions that are more distant from the user’s current location.
Ren and Dunham (2000) investigate the semantic caching
model to manage location-dependent data, and proposed the
replacement policy FAR (Furthest Away Replacement).
6
Location-Dependent Semantic Cache (LDSC)
The LDSC index is composed by the tuple (S, SR, SP, SA, SC, Sts, SG):
the name S,
the relation SR,
the selection predicate SP,
the geographic area SA,
the pointer SC,
the timestamp STS and the group SG.
This model maintain the spatial information SA, that represents the
segment geographic area.
SID
SR
SP
SA
SC
Sts
SG
S1
Hotel
Price < 100
[(5,15), (15,25)]
4
T1
1
S2
Restaurant
type = “chinese”
[(10,30), (-30,-10)]
8
T2
1
Example of the Location-Dependent Semantic Cache Index
7
Spatial Query Processing
Our query processing model involves two steps:
select the semantic segments candidate set;
1º) SR = QR
2º) SA  QJ
3º) QP  SP
QP: price < 100
S1P: price < 50
S3P: price < 150
S7P: price > 200
Example: “Give me all hotels within 5
miles with diary price lower than U$10
0”
CjSC = {S1, S3}
8
Spatial Query Processing
process the query against each segment and after in the
database in the server when is necessary.
For each Si in CjSC do {
Ii  intersection (SiA , QJ)
If (QP SiP) {
Send to server AQSi in Ii //**QP^SiP
APQ  APQ  AQSi }
Execute Q in Ii
APQ  APQ  Q
X  X + Ii } } //** vector X
If X <> QJ then
Send to server RQ = Q  ¬X
AQ = RQ  PQ
QP: price < 100
SP QP
QP QP
S1P: price < 50
AQS1: 50<price<100
S3P: price < 150
9
Semantic Segment Formation and Reorganization
Only the data brought into the cache from server should be
stored in a new segment.
The worst case:
Partial geographical relationship
Partial predicate relationship
Example:
QP: price < 100
S3P: price < 150
10
Semantic Segment Formation and Reorganization
Predicate
Adjust
Geographical
Adjust
Remove from Si the content (Si  QP in Ii)
If Si - (Si  QP   ) in Ii then
Create a new segment S’’
SiA  SiA – Ii
If SiA < > rectangle form then {
Adjust SiA with a rectangle representation } }
Example:
QP: price < 100
S3P: price < 150
S’ : price < 100
S’’ : 100 < price < 150
11
Conclusion and Future Work
Our proposed model allows the semantic cache management
based on spatial property of the cached data.
Semantic caching characteristics, spatial query processing
strategy and practical issues of semantic caching client
management were described.
The next step is to investigate the performance of the proposed
model.
Future studies also will explore semantic cache management
issues for more complex spatial location-dependent queries and
replacement policy.
12
Obrigado!
Perguntas?
[email protected]
13
Spatial Query Processing
Problem: The geographic area that it will be searched in the
server is a polygon with complex representation.
To solve this problem we propose the use of a vector X that stores
the rectangle of the areas already searched in cache.
“SELECT Hotel.nome
FROM Hotel
WHERE Hotel.diaria < 100
AND ((Hotel.geometria IN QJ)
AND (Hotel.geometria NOT IN X))”.
Probe and reminder query Geographic Area
14
15