Method, system and program for managing geographic data stored in a database

• US 7,539,666 B2
• Filed: 04/06/2004
• Issued: 05/26/2009
• Est. Priority Date: 04/06/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ashworth, Mark A., Mariconda, Joe
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): LIN, SHEW FEN
• Application Number:
  US10/819,458
• Publication Number:
  US 20050223044A1
• Time in Patent Office: 1,876 Days
• Field of Search: 707 1- 10, 707/102, 707/104, 707/200, 707/100, 701/208
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method, a data processing system and an article of manufacture for managing geographic identifiers stored in a database is described herein. The geographic identifiers each identify a respective geographic feature displayed on a surface map space partitioned by a mosaic of non-rectilinear shaped cells. The data processing system includes an accessing module for accessing a geographic look-up table and an index for the geographic look-up table, the geographic look-up table and the index being stored in the database, an identification module for identifying, from the index, stored row identifiers associated with a subset of the mosaic of non-rectilinear shaped cells, and a retrieving module for retrieving, from the geographic look-up table, stored geographic identifiers associated with the identified stored row identifiers.

Claims

1. A method of directing a data processing system to manage geographic identifiers stored in a database, the geographic identifiers each identifying a respective geographic feature displayed on a surface map space partitioned by a mosaic of non-rectilinear shaped cells, the method comprising:

accessing a geographic look-up table associating a unique row identifier with each geographical feature;

for each row in the geographic look-up table, performing;

determining at least one non-rectilinear shaped cell that intersects the geographical feature associated with the row identifier in the row by determining at least one non-rectilinear shaped cell that intersects a bound box of the geographical feature;

for each of the determined at least one non-rectilinear shaped cell, generating an entry in an index identifying the row identifier of the geographical feature and the determined non-rectilinear shaped cell intersecting the geographical feature, wherein the index is a non-unique B-tree index, wherein the index associates the row identifiers of the geographical features with cell identifiers of non-rectilinear shaped cells that intersect the bound box including the geographical feature, and wherein an index key of the index comprises the identifier of the non-rectilinear shaped cell and a data value of the index comprises the row identifier of the geographical feature; and

wherein the index associates the row identifiers of the geographical features with cell identifiers of non-rectilinear shaped cells that include the geographical feature, wherein there are multiple entries in the index for one row identifier intersecting multiple non-rectilinear shaped cells, wherein the multiple entries indicate the non-rectilinear shaped cells intersecting the geographical feature identified by the row identifier, and wherein the geographic look-up table and the index are stored in the database;

receiving a search region;

determining the non-rectilinear shaped cells that intersect the search region;

searching, by the data processing system, the index to determine the row identifiers associated with the cell identifiers of the determined non-rectilinear shaped cells included in the search region; and

producing the determined row identifiers identifying the geographical features included in the search region.

2. The method of claim 1 further comprising:

populating the geographic look-up table; and

populating the index.

3. The method of claim 1 wherein the surface map is spherically shaped, and wherein the spherically shaped surface map is partitioned by the mosaic of non-rectilinear cells.

4. The method of claim 1 wherein the mosaic of non-rectilinear shaped cells is shaped into a mosaic of Voronoi cells wherein each Voronoi cell is bounded by a neighboring Voronoi cell.

5. The method of claim 1 wherein the geographic feature represents a street.

6. The method of claim 1, wherein in the index, a subset of the mosaic associated with one stored row identifier associated, in the geographic look-up table, with a geographic identifier for a geographic feature located in a plurality of non-rectilinear shaped cells, indicates a plurality of non-rectilinear shaped cells including the geographic feature.

7. The method of claim 1, further comprising:

identifying a bounding region including the search region, wherein the determined non-rectilinear shaped cells intersect the bounding region including the search region.

8. The method of claim 7, wherein the bounding region comprises a circle or bound box.

9. The method of claim 1, wherein each index entry is comprised of a tuple, wherein a first part of the tuple indicates the non-rectilinear shaped cell and a second part of the tuple comprises the row identifier of the geographical feature.

10. A data processing system for managing geographic identifiers stored in a database, the geographic identifiers each identifying a respective geographic feature displayed on a surface map space partitioned by a mosaic of non-rectilinear shaped cells, the method comprising:

a central processing unit;

a computer usable memory including code executed by the central processing unit to perform operations, the operations comprising;

accessing a geographic look-up table in the computer usable memory associating a unique row identifier with each geographical feature;

for each row in the geographic look-up table, performing;

determining at least one non-rectilinear shaped cell that intersects the geographical feature associated with the row identifier in the row by determining at least one non-rectilinear shaped cell that intersects a bound box of the geographical feature;

for each of the determined at least one non-rectilinear shaped cell, generating an entry in an index in the computer usable memory identifying the row identifier of the geographical feature and the determined non-rectilinear shaped cell intersecting the geographical feature, wherein the index is a non-unique B-tree index, wherein the index associates the row identifiers of the geographical features with cell identifiers of non-rectilinear shaped cells that intersect the bound box including the geographical feature, and wherein an index key of the index comprises the identifier of the non-rectilinear shaped cell and a data value of the index comprises the row identifier of the geographical feature; and

wherein the index associates the row identifiers of the geographical features with cell identifiers of non-rectilinear shaped cells that include the geographical feature, wherein there are multiple entries in the index for one row identifier intersecting multiple non-rectilinear shaped cells, wherein the multiple entries indicate the non-rectilinear shaped cells intersecting the geographical feature identified by the row identifier, and wherein the geographic look-up table and the index are stored in the database;

receiving a search region;

determining the non-rectilinear shaped cells that intersect the search region;

searching the index to determine the row identifiers associated with the cell identifiers of the determined non-rectilinear shaped cells included in the search region; and

producing the determined row identifiers identifying the geographical features included in the search region.

11. The data processing system of claim 10 wherein the operations further comprise:

populating the geographic look-up table; and

populating the index.

12. The data processing system of claim 10 wherein the surface map is spherically shaped, and wherein the spherically shaped surface map is partitioned by the mosaic of non-rectilinear cells.

13. The data processing system of claim 10 wherein the mosaic of non-rectilinear shaped cells is shaped into a mosaic of Voronoi cells wherein each Voronoi cell is bounded by a neighboring Voronoi cell.

14. The data processing system of claim 10 wherein the geographic feature represents a street.

15. The data processing system of claim 10, wherein in the index, a subset of the mosaic associated with one stored row identifier associated, in the geographic look-up table, with a geographic identifier for a geographic feature located in a plurality of non-rectilinear shaped cells, indicates a plurality of non-rectilinear shaped cells including the geographic feature.

16. The data processing system of claim 10, further comprising:

identifying a bounding region including the search region, wherein the determined non-rectilinear shaped cells intersect the bounding region including the search region.

17. The data processing system of claim 16, wherein the bounding region comprises a circle or bound box.

18. The data processing system of claim 10, wherein each index entry is comprised of a tuple, wherein a first part of the tuple indicates the non-rectilinear shaped cell and a second part of the tuple comprises the row identifier of the geographical feature.

19. An article of manufacture having a computer usable memory embodying one or more computer usable instructions executable by a data processing system, the computer usable instructions for directing the data processing system to manage geographic identifiers stored in a database, the geographic identifiers each identifying a respective geographic feature displayed on a surface map space partitioned by a mosaic of non-rectilinear shaped cells, wherein the executed computer usable instructions perform operations, the operations comprising:

accessing a geographic look-up table associating a unique row identifier with each geographical feature;

for each row in the geographic look-up table, performing;

determining at least one non-rectilinear shaped cell that intersects the geographical feature associated with the row identifier in the row by determining at least one non-rectilinear shaped cell that intersects a bound box of the geographical feature;

for each of the determined at least one non-rectilinear shaped cell, generating an entry in an index identifying the row identifier of the geographical feature and the determined non-rectilinear shaped cell intersecting the geographical feature, wherein the index is a non-unique B-tree index, wherein the index associates the row identifiers of the geographical features with cell identifiers of non-rectilinear shaped cells that intersect the bound box including the geographical feature, and wherein an index key of the index comprises the identifier of the non-rectilinear shaped cell and a data value of the index comprises the row identifier of the geographical feature; and

wherein the index associates the row identifiers of the geographical features with cell identifiers of non-rectilinear shaped cells that include the geographical feature, wherein there are multiple entries in the index for one row identifier intersecting multiple non-rectilinear shaped cells, wherein the multiple entries indicate the non-rectilinear shaped cells intersecting the geographical feature identified by the row identifier, and wherein the geographic look-up table and the index are stored in the database;

receiving a search region;

determining the non-rectilinear shaped cells that intersect the search region;

searching the index to determine the row identifiers associated with the cell identifiers of the determined non-rectilinear shaped cells included in the search region; and

producing the determined row identifiers identifying the geographical features included in the search region.

20. The article of manufacture of claim 19 wherein the operations farther comprise:

populating the geographic look-up table; and

populating the index.

21. The article of manufacture of claim 19 wherein the surface map is spherically shaped, and wherein the spherically shaped surface map is partitioned by the mosaic of non-rectilinear cells.

22. The article of manufacture of claim 19 wherein the mosaic of non-rectilinear shaped cells is shaped into a mosaic of Voronoi cells wherein each Voronoi cell is bounded by a neighboring Voronoi cell.

23. The article of manufacture of claim 19 wherein the geographic feature represents a street.

24. The article of manufacture of claim 19 wherein in the index, a subset of the mosaic associated with one stored row identifier associated, in the geographic look-up table, with a geographic identifier for a geographic feature located in a plurality of non-rectilinear shaped cells, indicates a plurality of non-rectilinear shaped cells including the geographic feature.

25. The article of manufacture of claim 19 further comprising:

identifying a bounding region including the search region, wherein the determined non-rectilinear shaped cells intersect the bounding region including the search region.

26. The article of manufacture of claim 25 wherein the bounding region comprises a circle or bound box.

27. The article of manufacture of claim 19 wherein each index entry is comprised of a tuple, wherein a first part of the tuple indicates the non-rectilinear shaped cell and a second part of the tuple comprises the row identifier of the geographical feature.