GB2402778A

GB2402778A - Method of location finding on a mobile computing device

Info

Publication number: GB2402778A
Application number: GB0412997A
Authority: GB
Inventors: Neil Jefferson Barnes
Original assignee: Symbian Software Ltd
Current assignee: Symbian Software Ltd
Priority date: 2003-06-10
Filing date: 2004-06-10
Publication date: 2004-12-15
Also published as: GB0313377D0; GB0412997D0; WO2004109319A1

Abstract

Location finding on a mobile computing device includes the step of using a database of geographic features that have been spatial tile indexed using an arrangement of tiles, in which each tile can be hierarchically decomposed into lower levels of smaller sub-tiles. To date, the application of spatial tile indexing in the context of resource constrained mobile computing devices has not been recognised. With the present invention, location queries that were computationally very intensive to perform using a conventional approach can now been undertaken much more efficiently. The tiles may have binary values.

Description

METHOD OF LOCATION FINDING ON A MOBILE COMPUTING

DEVICE

BACKGROUND TO THE INVENTION

1. Field of the Invention

This invention relates to a method of location finding on a mobile computing device. A mobile computing device is a portable computing device with resource constraints (e.g. computing power significantly less than a desktop or laptop computer). Examples of mobile computing devices includes smart phones and PDAs.

2. Description of the Prior Art

Mobile computing devices can run personal navigation software and other kinds of location dependent applications; generally, these applications require the device to store digital maps of a region (typically defining roads in a region such as a country as vectors and locations of interest as points coded into a standard format, such as WGC84 - World Geodetic System 1984). The device itself will include software that can analyse the data held in the digital maps. Hence, personal navigation software allows the device (in combination with a location finding system such as GPRS, GPS etc.) to locate the current position of the device and display it on a map and also to locate and display routes to user defined destinations. Lkcwisc, the software can be used to display locations of interest on the map: for example, a user might want to know where the closest petrol station is to his current location.

The device can then search its database storing the location of petrol stations and then display all nearby petrol stations. This kind of search function Is usually performed using some kind of trigonometric function, with the straight line distance between the current location of the user and each petrol station in its entire database being scqucutially calculated; no preferential ordering of the sequence of petrol stations is done, since that implies prior knowledge of which petrol station is closest, which the device does not have. This kind of search can use significant computing cycles and hence power, which are both scarce resources on a mobile computing device.

Spatial tile indexing systems are well known in the field of mainframe databases used to store very large volumes of geographic information. Spatial tile indexing is a technique to reduce the time taken to find geographic features (landmarks, points of interest etc.) within specified criteria of another feature (e.g. distance). It comprises dividing the world into a known number of "tiles" or cells, with each tile being hicrarchcially decomposable into smaller sub-tiles at one level down, and each of those sub-tiles themselves being decomposable into even smaller sub-tiles at a further level down etc.. Then, one determines which tile and sub-tile(s) a landmark is located within and storing the tile identifier(s) along with other attributes of the landmark in a database. The tile identifiers code for the level of decompostion of higher level tiles and sub-tiles, as well as the particular sub-tile at the lowest level of 1 5 decomposition.

When searching for landmarks that meet criteria in relation to another landmark (within a certain distance, for example) the tile identifiers are used as a first pass filter to reduce the set of candidate landmarks that have to be assessed. Reference may be made to US 2002/0035432, which describes spatial indexing linked to the internet, a field generally known as the spatial web. Reference may also be made to products such as Oracle8i (see Oracle8i Spatial: Experiences with Extensible Databases. An Oracle Technical White Paper May 1999).

SUMMARY OF THE PRESENT INVENTION

In an implementation of the present invention, location finding on a mobile computing device includes the step of using a database of geographic features that have been spatial tile indexed using an arrangement of tiles, in which each tile can be hierarchically decomposed into lower levels of smaller sub-tiles.

The prior art shows a strong technical bias towards using spatial tile indexing in the field of large geographic databases (e.g. OraeleSi Spatial) running on computing platforms that are not challenged by the resource constraints of mobile computing devices. Hence, the present invention is based on the insight that spatial tile indexing goes a long way to solving the problem of minimsing computing cycles and hence power consumption in a mobile computing device when performing a search of a geographic features database to locate user defined features that are within user specified criteria of another geographic feature (e.g. petrol stations that are closest to a user's current location). To date, the application of spatial tile indexing in the context of resource constrained mobile computing devices has not been recognised.

With the present invention, location queries that were computationally very intensive to perform using a conventional approach can now been undertaken much more efficiently. Examples include the following: À Buffering: e.g. determining the location of features that are within say 200 metres of a planned route À Locating features that are within a polygon, compound polygon etc; e.g. all museums within a city boundary À Locating features that are within an intersection of lines, polygons, compound polygons etc.; e.g. all car parks outside of a traffic congestion charging zone but in a city centre or within 100 meters of that zone.

The present invention can be deployed as a first pass process to reduce the subsequent time needed to perform a conventional location finding process. It can also be used as the sole location finding process.

In conventional spatial indexing systems, a region is divided into 4 tiles, number 1 through to 4, as shown in Figure 1A. This is hierarchically decomposed, so that tile region '1' is itself split into 4 tiles (known as sub-tiles), numbered 11 - 14, as shown in Figure 1B. At the next level down, tile 11 is itself decomposed into 4 sub-tiles, numbered 111 through to 114, as shown in Figure 1B. With 16 levels of decomposition of this kind, it is possible to map the entire world surface down to approximately IKm tiles.

In an implementation of the present invention, instead of starting tile numbering at 1', we start with a '0'. Hence, the highest tile levels cover tiles O through to 3. This enables more efficient mapping to binary. These tiles can therefore be represented In binary format as 00, 01, 10 and 11 as shown in Figure 2A;. The highest tile can be held in the first two bits (bits 1 and 2) of a binary number. The next level of decomposition can be held in the next two bits (bits 3 and 4) and so on, allowing any tile to be uniquely addressed. Therefore, tile '00'itself can be decomposed into sub-tiles '0000', '0001', '0010' and '0011', as shown in Figure 2B, as can each of the other high level tiles. Each of these sub-tiles can then be decomposed using the same method as shown if Figure 2C. Using the conventional method, a 2 Byte (i.e. 16 bit) number can only hold 10 levels of decomposition. With this approach, 16 levels of decomposition is possible. This is important to a mobile device where storage space is limited. It also allows 'bit comparison' to be utilised which uses less computing time than a normal comparison of two numbers By ordering the tiles or sub-tiles as shown in Figure 2A the bits can be utilised to Indicate which half of the tile the sub-tile or feature is located in. For example the first of the two bits can be used to indicate if the sub-tile or feature is in the left side of the tile above, the second bit to indicate if the sub-tile or feature is in the top half of the tile above. This then allows easier location of the sub-tiles surrounding the current sub-tile and hence reduces the amount of computing time required when searching for features.

AppendLx The following is pseudo-code to determine the level of decomposition required for tile size.

This will give the level of decomposition required for the size of tile required. The method will round down to a smaller tile size rather than round up to a larger tile size.

For example if the projection width is 40070 Km (the circumference of the earth at the equator) and the tile size required is 500 Km then the method will give a level of 8 (which gives a tile size of 313Km) rather than a level of 7 (which gives a tile size of 626Km).

Set T,evel to (I,og2(projection width/required tile size) + 1) If (Level Truncated(Level)) is greater than O Then Increment Level by 1 End If The following is pseudo-code to determine the bitmapped tile identifier given the coordinates of a feature and the level of decomposition This will give the bitmapped identifier of the tile in which the feature is located. The routine will continue decomposing the tile until the required level of decomposition is reached. In the example below the Cartesian coordinates are used to indicate the location of the feature.

Set Y_Max to maximum Y coordinate in the projection Set Y_Min to O Set X_Min to maximum X coordinate in the projection Set X_Max to O Set Bit_Position to 1 Set Level to 1 Do While Level is less than or equal to Required Level If Feature Y Coordinate is less than (Y_Min+(Y_Max-Y_Min) /2) Then Set Tile Identifier indexed by Bit Position to 1 Set Y Max to Y_Max - (Y_Max - Y_Min)/2 Else Set Tile Identifier indexed by Bit Position to O Set Y_Min to Y_Min + (Y_Max - Y_Min)/2 End If if Feature X Coordinate is less than (X_Min+(X_Max-X_Min)/2) Then Set Tile Identifier indexed by Bit Position plus 1 to 1 Set X_Max to X_Max - (X_Max - X_Min) /2 Else Set Tile Idcotifier indexed by Bit Position plus 1 to 0 Set X_Min to X_Min + (X_Max - X_Min)/2 End If Increment Level by 1 Increment Bit Position by 2 End Do

Claims

1. A method of location finding on a mobile computing device comprising the step of using a database of geographic features that have been spatially tile indexed using an arrangement of tiles, in which each tile can be hierarchically decomposed into lower levels of smaller sub-tiles.

2. The method of Claim 1 in which the highest tile levels cover tiles 0 through to 3.

3. The method of Claim 2 in which each of the tiles can be represented as tiles with one of the following binary values: 00, 01, 11 and 10.

4. The method of Claim 3 in which each of the lower level tiles can be decomposed into tiles with one of the following binary values: 00, 01, 11 and 10.

5. The method of Claim 1 comprising the step of determining the location of features that are within a defined buffer zone.

6. The method of Claim 1 comprising the step of finding locations that are within a polygon or compound polygon.

7. The method of Claim 1 comprising the step of funding locations that are within an intersection of lines, polygons or compound polygons.

8. A mobile computing device programmed to perform location funding using a database of geographic features that have been spatially tile indexed using an arrangement of tiles, in which each tile can be hierarchically decomposed into lower levels of smaller sub-tiles.

9. Computer software enabling a mobile computing device to perform location finding using a database of geographic features that have been spatially tile indexed using an arrangement of tiles, in which each tile can be hierarchically decomposed into lower levels of smaller sub-tiles.