DOC PREVIEW
USC CSCI 599 - c-4

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Location-based Spatial Queries Jun Zhang§ Manli Zhu§ Dimitris Papadias§ Yufei Tao† Dik Lun Lee§ §Department of Computer Science Hong Kong University of Science and Technology Clear Water Bay, Hong Kong { zhangjun, cszhuml, dimitris, dlee}@cs.ust.hk †Department of Computer Science Carnegie Mellon University Pittsburgh, USA [email protected] Abstract In this paper we propose an approach that enables mobile clients to determine the validity of previous queries based on their current locations. In order to make this possible, the server returns in addition to the query result, a validity region around the client's location within which the result remains the same. We focus on two of the most common spatial query types, namely nearest neighbor and window queries, define the validity region in each case and propose the corresponding query processing algorithms. In addition, we provide analytical models for estimating the expected size of the validity region. Our techniques can significantly reduce the number of queries issued to the server, while introducing minimal computational and network overhead compared to traditional spatial queries. 1. INTRODUCTION Spatial databases have been extensively studied during the last two decades and several spatial access methods (SAMs) have been proposed [GG98]. Among the most popular ones is the R-tree and its variations, notably the R*-tree [BKSS90]. R-trees can be viewed as multi-dimensional extensions of B-trees. Figure 1 shows an exemplary R-tree for a set of points {a, b, c,…} assuming a capacity of three entries per node. Points that are close in space (e.g., a, b, c) are clustered in the same leaf node (E4) represented as a minimum bounding rectangle (MBR). Nodes are then recursively grouped together following the same principle until the top level, which consists of a single root. abcdefhgE1E2E3E4E5E6E7E8RootE9iE1E2E4E5E8E2046810246810x axisy axisbEfomitted1E2edcagE3E5E6E4E78contentsE9iquerywindowq Fig. 1: An R-tree example R-trees (like most SAMs) were motivated by the need to efficiently process window queries, which retrieve all the objects that intersect a window (shaded area in Figure 1). The R-tree answers a window query q as follows. The root is first retrieved and the entries inside it are compared with q. The ones (e.g., E1, E2) that intersect q may contain qualifying points and are recursively searched until the leaf (data point) level. Entries not intersecting the query window (e.g., E3) are not visited. Another important type of spatial information processing is the nearest neighbor query, which retrieves the data point that is closest to a query point. Roussopoulos et al., [RKV95] propose a branch-and-bound algorithm that searches the R-tree in a depth-first manner. Specifically, starting from the root, all entries are sorted according to their minimum distance (mindist) from the query point, and the entry with the smallest value is visited first. The process is repeated recursively until the leaf level where the first potential nearest neighbor is found. During backtracking to the upper levels, the algorithm only visits entries whose mindist is smaller than the distance of the nearest neighbor already found. In the example of Figure 2, the algorithm first visits the root entry E1 (since it has the minimum mindist), and then E4, where the first candidate object (a) is retrieved. When backtracking to the previous level, entries E5 and E6 are excluded, since their mindist is greater than (or equal to) the distance of a. Then E2 and E8 are accessed, where the actual nearest neighbor (point h) is found. Samet and Hjaltason [HS99] develop an improved algorithm, which only visits nodes that may contain the actual nearest neighbor (i.e., in the previous example the algorithm would find point h, without first retrieving a). Both algorithms can be easily applied for the retrieval of k > 1 nearest neighbors. E2046810246810x axisy axisbEf1E2edcagE3E5E6E4E78E9iquery pointmindist( )E2h= mindist( )E8mindist( )E4= mindist( )amindist( )E1 Fig. 2: Nearest neighbor example The traditional scenario in spatial databases assumes that (i) queries are static and (ii) each query returns a single output and terminates. Consider now an alternative situation where a user with a location-aware mobile device poses a continuous query with respect to his/her current position (e.g., he wants to know the closest restaurant as he moves along). The query is sent to the server, where it is processed and the result is returned to the client via the underlying wireless networks. Due to the mobility of the user, the result may be invalidated immediately as the user's position changes. The conventional approach to attain up-to-date information is to pose a new query to the server after a position update, which could lead to high network overhead and extra processing effort. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. ACM SIGMOD'2003, June 9-12, San Diego, California, USA. Copyright 2003 ACM 1-58113-634-X/03/06...$5.00. 443443Assume in Figure 3 that the user (at position q) issues a nearest neighbor query returning point o. The motivation of this work is that while the user remains in a certain area around the initial position, called the validity region (shaded area), the result remains the same. In addition to the query result, the server has to return the validity region of the query, according to which the mobile client is able to determine whether a new query should be issued by verifying whether it is still inside the validity region. Given that the mobile clients have limited storage and processing capabilities compared to the server, it pays off to perform additional processing on the server side (for the initial query) in order to reduce the number of subsequent queries. Furthermore, the representation of the validity region should be compact in order to reduce the network cost, the storage requirements and the computation that must be performed at the client side. validityregionqo Fig. 3: Validity region In this paper, we study the problem of determining


View Full Document

USC CSCI 599 - c-4

Documents in this Course
Week8_1

Week8_1

22 pages

Week2_b

Week2_b

10 pages

LECT6BW

LECT6BW

20 pages

LECT6BW

LECT6BW

20 pages

5

5

44 pages

12

12

15 pages

16

16

20 pages

Nima

Nima

8 pages

Week1

Week1

38 pages

Week11_c

Week11_c

30 pages

afsin

afsin

5 pages

October5b

October5b

43 pages

Week11_2

Week11_2

20 pages

final

final

2 pages

0420

0420

3 pages

Week9_b

Week9_b

20 pages

S7Kriegel

S7Kriegel

21 pages

Week4_2

Week4_2

16 pages

sandpres

sandpres

21 pages

Week6_1

Week6_1

20 pages

4

4

33 pages

Week10_c

Week10_c

13 pages

fft

fft

18 pages

LECT7BW

LECT7BW

19 pages

24

24

15 pages

14

14

35 pages

Week9_c

Week9_c

24 pages

Week11_67

Week11_67

22 pages

Week1

Week1

37 pages

LECT3BW

LECT3BW

28 pages

Week8_c2

Week8_c2

19 pages

Week5_1

Week5_1

19 pages

LECT5BW

LECT5BW

24 pages

Week10_b

Week10_b

16 pages

Week11_1

Week11_1

43 pages

Week7_2

Week7_2

15 pages

Week5_b

Week5_b

19 pages

Week11_a

Week11_a

29 pages

LECT14BW

LECT14BW

24 pages

T7kriegel

T7kriegel

21 pages

0413

0413

2 pages

3

3

23 pages

C2-TSE

C2-TSE

16 pages

10_19_99

10_19_99

12 pages

s1and2-v2

s1and2-v2

37 pages

Week10_3

Week10_3

23 pages

jalal

jalal

6 pages

1

1

25 pages

T3Querys

T3Querys

47 pages

CS17

CS17

15 pages

porkaew

porkaew

20 pages

LECT4BW

LECT4BW

21 pages

Week10_1

Week10_1

25 pages

wavelet

wavelet

17 pages

October5a

October5a

22 pages

p289-korn

p289-korn

12 pages

2

2

33 pages

rose

rose

36 pages

9_7_99

9_7_99

18 pages

Week10_2

Week10_2

28 pages

Week7_3

Week7_3

37 pages

Load more
Download c-4
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view c-4 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view c-4 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?