Browse Prior Art Database

A Method for Geographic Location Context Indexing and Querying

IP.com Disclosure Number: IPCOM000016596D
Original Publication Date: 2003-Jul-02
Included in the Prior Art Database: 2003-Jul-02
Document File: 5 page(s) / 511K

Publishing Venue

IBM

Abstract

It is a method for geographic location context indexing and querying, which aims to serve large-scale concurrent users and provide wide scope location context service. Geographic location context is the information relevant to a given position or region. It includes two basic operations: one is indexing, which publishes context information into systems; the other is querying, which searches needed context information stored in systems. The essence of this invention is the representation of geographic space with a hierarchy of self computable grids with squares of increasing size. The entire geographic space is partitioned into hierarchical squares and each square is uniquely labeled by its location information. This representation significantly reduces the spatial cost of indexing and temporal cost of querying.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 5

A Method for Geographic Location Context Indexing and Querying

The advantages to solve the problem can be generialized into following terms:
1) Represent geographic space with a hierarchy of grids with squares of increasing size.
2) Represent geographic location context by several multi-level self computable grids.
3) Querying process without context can easily locate particular grids.
4) Querying process with context can only locate a small set of particular grids.

(a) Representation of geographic space

Figure 1: the representation scheme

Figure 1 shows the partition scheme following these rules:
(1) the entire space is defined as 0-order region;
(2) each n-order region can be partitioned into 2*2 (n+1)-order regions, where n>0.

The maximum number of n is denoted as nmax , which is decided by users, systems or the locating accuracy of Location Service Provider such as GPS.

The approach to label the regions is defined as follows.
(1) The region address of 0-order region in null.

1

[This page contains 1 picture or other non-text object]

Page 2 of 5

(2) If n > 0, the region address of n-order region is the concatenation of (n-1)-order region address and (i, j), (i, j) represents the position of this n-order region in the (n-1)-order region with the upper left corner as the origin point.

In figure 1, the region address of R0 is null; the region address of R1 is (0,1); the region address of R2 is (1,0)(0,1); the region address of R3 is (1,1)(0,1)(0,0); the region address of R4 is (0,1)(0,1)(1,1)(1,0).

(b) Indexing Scheme

Indexing unit accomplishes the index operation of the system. Given a position or region value, indexing unit puts the corresponding context information into the system.

Define position and region value as index value. The index value is generated as follows.
(1) The initial index value is null.
(2) Check top down to find weather the space covers one or more regions. If the geographic space covers one or more current n-order regions, concatenate the index value with the region addresses; if the space does not cover any current order regions, the index value is concatenated with "null".
(3) The delimiter of different order region addresses is ";", and the delimiter of the same order region address is "+", if the same order region address have the same (n-1)-order region address, pick the (n-1)-order region address as prefix and concatenate it with the left parts by delimiter "[" and the right parts by by delimiter "]".

Figure2: the indexing scheme

Figure 2 shows indexing scheme and information storage of a space. The shade

2

[This page contains 1 picture or other non-text object]

Page 3 of 5

regions store information of the geographic space. If the space covers four n-order regions having the same (n-1)-order region address, the identical information of the four regions is stored in the corresponding (n-1)-order region.

The index v...