Method of retrieving entities

• US 20040019592A1
• Filed: 05/30/2003
• Published: 01/29/2004
• Est. Priority Date: 12/15/2000
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Crabtree, Ian B.
• Granted Patent: US 7,277,886 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

The present invention relates to a method of retrieving points that can be plotted in a predetermined area, where the locations of the points are indexed in an index that comprises regional data. The regional data defines a plurality of regions, and each region encompasses one or more of the points. In addition, the index comprises linking data, which, for each region, identifies the point or points encompassed by that region. The method comprises the steps of:

(i) reviewing the regional data in the index to identify regions that are wholly contained by the predetermined area; and

(ii) reviewing the linking data to retrieve points encompassed by the identified regions.

Claims

1. A method of retrieving one or more points that are contained within a predetermined area, comprising the steps of:

(i) retrieving data identifying a region, the region encompassing one or more points and being associated with linking data which, for each region, identifies the point or points encompassed by that region;

(ii) performing a process in respect of the region, the process comprising the steps of;

comparing extents of the region with extents of the predetermined area in order to establish whether the region overlaps with the predetermined area;

if there is overlap, retrieving data identifying sub-regions of the region and identifying any such sub-regions whose extents are wholly within the predetermined area;

(iii) for each sub-region, repeating the process until all sub-regions thereof falling wholly within the predetermined area are identified, and

(iv) accessing linking data corresponding to the identified sub-regions so as to retrieve points encompassed by the sub-regions.

2. A method according to claim 1, wherein the plurality of points is pre-stored as a list of points in accordance with relationships between sub-regions, and the linking data includes a value indicating the position of a first of the corresponding encompassed points in the list of points, and wherein the accessing step (iv) comprises, for each of the identified sub-regions:

retrieving an identifier representative of the number of encompassed points and retrieving a position value associated with the identified sub-region; and

accessing the list of points and retrieving the number of encompassed points from a position in the list given by the position value.

3. A method according to claim 1 or claim 2, in which the data identifying the region and sub-regions and corresponding linking data are stored in an index.

4. A method according to any one of the preceding claims, in which the predetermined area corresponds to range information.

5. A method according to claim 4, in which the range information includes any one of geographical range information, operating hours information, delivery time information, and/or medical information.

6. A computer program, or a suite or computer programs, comprising a set of instructions to cause a computer, or a suite of computers, to perform the method according to claims 1 to 5.

7. A computer data signal embodied in a carrier wave and representing sequences of instructions which, when executed by a processor cause the processor to perform the method according to claims 1 to 5.

8. A retrieval method comprising the steps of sending a retrieval request, the retrieval request comprising a signal indicative of an area within which points are to be retrieved and a trigger signal, the trigger signal invoking the method according to any one of claims 1 to 5.

9. Apparatus for retrieving one or more points that are contained by a predetermined area, the apparatus comprising input means arranged to receive a retrieval request, the retrieval request comprising a signal indicative of the predetermined area;

storage means arranged to store

data indicative of one or more regions, each region encompassing one or more points;

linking data associated with the regions, wherein each item of linking data identifies the point or points encompassed by a respective region; and

data identifying the points;

retrieving means arranged to access the store and retrieve one or more points corresponding to the predetermined area; and

output means arranged to output the one or more retrieved points, the apparatus being arranged, in response to receipt of a retrieval request, such that the retrieving means retrieves a region from the store and performs a process in respect of the retrieved region, the process comprising the steps of;

comparing extents of the region with extents of the predetermined area in order to establish whether the region overlaps with the predetermined area;

if there is overlap, retrieving data identifying sub-regions of the region and identifying any such sub-regions whose extents are wholly within the predetermined area;

the retrieving means then, for each sub-region, repeats the process until all sub-regions thereof falling wholly within the predetermined area are identified, accesses linking data corresponding to the identified sub-regions and retrieves points encompassed by the sub-regions, whereupon the output means outputs the retrieved points.

10. Server apparatus for retrieving one or more points that are contained by a predetermined area, the server apparatus comprising:

input means arranged to receive a retrieval request, the retrieval request comprising a signal indicative of the predetermined area;

accessing means arranged to access a store in respect of the predetermined area; and

receiving means arranged to receive data from the store;

the store comprising data indicative of one or more regions, each region encompassing one or more points;

the store further comprising linking data associated with the regions, which linking data identifies the point or points encompassed by that region;

the store being in operative association with query means for querying the store, the query means being arranged to identify one or more regions that are contained by the predetermined area, access linking data corresponding thereto and transmit the accessed linking data to the server apparatus.