1

Processamento de Consultas Espaciais Baseado em Cache

Semântico Dependente de Localização

Heloise Manica

Murilo S. de CamargoCristina Dutra de Aguiar Ciferri

Ricardo Rodrigues Ciferri

Novembro, 2004

2

Contents

Background

Goal and Motivation

Related Work

Location-Dependent Semantic Cache

Spatial Query Processing

Semantic Segment Formation and Reorganization

Conclusion and Future Work

3

Background

Mobility has opened up new classes of applications such as Lo

cation-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 l

ocation criteria explicitly or implicitly specified (Ren and Dunha

m,2000).

Example:

“Find the restaurants within 3 miles from my position” (implic

it location)

4

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.

5

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.

6

Related Work

Dunham and Kumar (1998) and Lee et al. (2002) introduced t

he concept of location dependent data and present new researc

h issues.

Zheng et al. (2002) and Xu et al. (2003) studied cache manag

ement 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 d

istance function. Their replacement policy discard semantic regi

ons that are more distant from the user’s current location.

Ren and Dunham (2000) investigate the semantic caching mo

del to manage location-dependent data, and proposed the repla

cement policy FAR (Furthest Away Replacement).

7

Location-Dependent Semantic Cache (LDSC)

The LDSC index is composed by the tuple (S, SR, SP, SA, SC, Sts, SG):

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 1Example of the Location-Dependent Semantic Cache Index

This model maintain the spatial information SA, that represents the

segment geographic area.

the name S,

the relation SR,

the selection predicate SP,

the geographic area SA,

the pointer SC,

the timestamp STS and the group SG.

8

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

Example: “Give me all hotels within 5 miles with diary price lower

than U$100”

QP: price < 100

S1P: price < 50S3P: price < 150 S7P: price > 200

CjSC = {S1, S3}

9

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

QPQP

QP: price < 100

S1P: price < 50AQS1: 50<price<100

S3P: price < 150

QPSP

10

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

11

Semantic Segment Formation and Reorganization

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 } }

Predicate Adjust

Geographical

Adjust

Example:

QP: price < 100S3P: price < 150

S’ : price < 100 S’’ : 100 < price < 150

12

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.

13

Obrigado!

Perguntas?

heloise@inf.ufsc.br

14

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.

Probe and reminder query Geographic Area

“SELECT Hotel.nome FROM Hotel WHERE Hotel.diaria < 100 AND ((Hotel.geometria IN QJ) AND (Hotel.geometria NOT IN X))”.

15