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

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.

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.