Data Partitioning Systems

• US 20080228783A1
• Filed: 03/14/2007
• Published: 09/18/2008
• Est. Priority Date: 03/14/2007
• Status: Abandoned Application

• Current Assignee: 1Spatial Group Limited (1Spatial Plc)
• Original Assignee: 1Spatial Group Limited (1Spatial Plc)
• Inventors: Moffat, Dawn
• Application Number:
  US11/686,069
• Publication Number:
  US 20080228783A1
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

This invention generally relates to methods, systems, data structures and computer program code for managing spatial data, in particular very large volumes of data such as map data for a region or country. Thus we describe a method of partitioning a database of spatial data, the database including a plurality of spatial feature objections, the method comprising: reading data from said database grid cell-by-grid cell, a said grid cell comprising a cell of a grid spatially subdividing a region of spatial coverage of said database, each said grid cell including spatial feature objects; and determining a set of spatial partitions for said database, each grid cell being allocated to a said partition, responsive to a number of said spatial feature objects in each said grid cell.

Claims

1. A method of partitioning a database of spatial data, the database including a plurality of spatial feature objections, the method comprising:

reading data from said database grid cell-by-grid cell, a said grid cell comprising a cell of a grid spatially subdividing a region of spatial coverage of said database, each said grid cell including spatial feature objects; and

determining a set of spatial partitions for said database, each grid cell being allocated to a said partition, responsive to a number of said spatial feature objects in each said grid cell.

2. A method as claimed in claim 1 wherein said spatial feature objects comprise topographical data objects including at least a first type of object and a second type of object;

and wherein said determining comprises determining a first set of partitions responsive to a number of said first type of object in each cell and determining a second set of partitions responsive to a number of said second type of object in each cell.

3. A method as claimed in claim 2 wherein said first type of object comprises a line object and said second type of object comprises an area object.

4. A method as claimed in claim 1 wherein said determining comprises reading data for each said grid cell in turn from said database and adding said number of spatial feature objects for a grid cell to a running total for a partition until a partition size is reached, to determine a said spatial partition.

5. A method as claimed in claim 4 wherein said determining further comprises determining spatial boundary data for a said partition from spatial data defining one or more grid cells having objects contributing to said running total for the partition.

6. A method as claimed in claim 4 wherein said determining comprises populating a data structure comprising data defining for each said grid cell, coordinates of the cell, a count of a number of said feature objects in the cell, and a partition identifier for the cell to identify a partition within which the cell is located.

7. A method as claimed in claim 1 further comprising creating and storing data associating each said spatial feature object with a said partition.

8. A method as claimed in claim 1 further comprising creating a data structure defining a spatial boundary of each said partition.

9. A method as claimed in claim 1 further comprising dividing stored spatial data for said objects into a plurality of files at the operating system level, one for each said partition.

10. A method as claimed in claim 1 further comprising determining said grid.

11. A method as claimed in claim 1 wherein there is at least one million said objects, at least 10 million or at least 100 million said objects.

12. A carrier carrying processor control code to, when running, implement the method of claim 1.

13. A data processing system or database Including the code of claim 12.

14. A method of managing data in a database of spatial data, the database including a plurality of spatial feature objects, the method comprising:

aggregating a group of grid cells, a said grid cell comprising a cell of a grid spatially subdividing a region of spatial coverage of said database, into a single geometric object;

storing data for said geometric object in said database; and

repeating said aggregating to define a plurality of said geometric objects each comprising a group of a plurality of grid cells.

19. A method of searching the database of claim 14, the method comprising:

inputting a search request relating to a spatially defined area;

identifying one or more of said partitions to which said search request relates;

searching said identified partitions.

20. A carrier carrying processor control code to, when running, implement the method of claim 19.

15. A database of spatial data for a region, the database having at least one data structure comprising a set of topological objects and including a plurality of spatial partitions of said region;

wherein each said object has associated data identifying a said partition within which the object is spatially located.

16. A database as claimed in claim 15 having two said data structures, a first comprising a set of topological objects of a first type and a second comprising a set of topological objects of a second type, each having a separate said spatial partition.

17. A database as claimed in claim 15 further comprising a partition data structure including spatial data defining a spatial boundary of each said partition.

18. A database as claimed in claim 15 wherein each said partition includes the same number of said topological objects to within a tolerance of ±

50%.

21. A data processing system for partitioning a database of spatial data, the database including a plurality of spatial feature objections, the system comprising:

a system to read data from said database grid cell-by-grid cell, a said grid cell comprising a cell of a grid spatially subdividing a region of spatial coverage of said database, each said grid cell including spatial feature objects; and

a system to determine a set of spatial partitions for said database, each grid cell being allocated to a said partition, responsive to a number of said spatial feature objects in each said grid cell;

wherein said spatial feature objects comprise topographical data objects including at least a first type of object and a second type of object; and

wherein said system to determine said set of spatial partitions is configured to determine a first set of partitions responsive to a number of said first type of object in each cell and to determine a second set of partitions responsive to a number of said second type of object in each cell.