Partitioning of geographic data

• US 10,331,710 B2
• Filed: 02/11/2016
• Issued: 06/25/2019
• Est. Priority Date: 10/01/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Couckuyt, Jeffrey Darren, Schwartz, Joseph, Galuzo, Sergey Y.
• Primary Examiner(s): Nguyen, Kim T
• Application Number:
  US15/042,115
• Publication Number:
  US 20170097942A1
• Time in Patent Office: 1,230 Days
• Field of Search: 707705
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Improving the efficiency of distributed database systems in providing geographically related information is provided by generating a data object identifier (ID) in association with geographical data. A geographical data object is received for storage in the distributed database system. A grid ID is generated based on spatial information contained in the geographical data object, a shardlet ID is generated indicating a shardlet location in a given shard on which the geographical data object is stored, and a sequence ID is generated indicating data placement within the shardlet location. The data object ID is assigned to the geographical data object, the data object ID comprising the grid ID, the shardlet ID, and the sequence ID.

Claims

1. A method for improving efficiency of storage and retrieval of geographic data in a distributed database system by generating a data object identifier (ID), the method comprising:

receiving a geographical data object for storage in the distributed database system, the distributed database system comprising a plurality of shards;

generating a grid ID based on spatial information contained in the geographical data object;

storing the geographical data object in a shard of the plurality of shards based on the grid ID;

generating a shardlet ID indicating a shardlet location in the shard where the geographical data object is stored;

generating a sequence ID indicating data placement of the geographical data object within the shardlet location;

assigning the data object ID to the stored geographical data object, the data object ID comprising the grid ID, the shardlet ID, and the sequence ID; and

in response to receiving a request from a user to access the stored geographical data object, retrieving the stored geographical data object from the distributed database system based on the data object ID.

2. The method of claim 1, wherein the distributed database system comprises a plurality of append-only shards.

3. The method of claim 2, further comprising:

assigning the geographical data object a next available sequential number; and

selecting a shard from the plurality of append-only shards for storage of the geographical data object based on a modulus operation of a number indicating how many shards are in the plurality of append-only shards and the next available sequential number.

4. The method of claim 3, further comprising generating the shardlet ID based on the grid ID to thereby spatially partition geographical data within the selected shard.

5. The method of claim 1, wherein the grid ID is associated with a physical geography of Earth.

6. The method of claim 5, wherein the grid ID corresponds to an area comprising a 0.1 degree by 0.1 degree space on Earth.

7. The method of claim 1, further comprising ordering a plurality of geographical data objects including the geographical data object in the shard where the geographical data object is stored based on respective data object IDs for each of the plurality of geographical data objects.

8. The method of claim 1, further comprising:

mapping between a plurality of shardlet IDs and the plurality of shards; and

storing shardlet mapping information in a central database system residing in the distributed database system.

9. The method of claim 1, wherein the data object ID comprises 64 bits.

10. The method of claim 9, wherein the grid ID comprises 28 bits of the data object ID.

11. The method of claim 9, wherein the shardlet ID comprises 11 bits of the data object ID.

12. The method of claim 9, wherein the sequence ID comprises 27 bits of the data object ID.

13. The method of claim 1, further comprising generating the sequence ID as a next available sequential sequence ID number corresponding to a combination of the grid ID and the shardlet ID.

14. A method for improving efficiency of storage and retrieval of geographic data in a distributed database system by generating a data object identifier (ID), the method comprising:

receiving a search request from a mapping application, wherein the search request defines a geographical area;

translating the geographical area to a plurality of grid IDs; and

retrieving a plurality of geographical data objects from the distributed database system, the distributed database system comprising a plurality of shards in which the plurality of geographical data objects are stored, wherein a retrieved geographical data object is identified by a data object ID comprised in part of a grid ID from the plurality of grid IDs, the data object ID having been generated upon receipt of the geographical data object for storage in the distributed database system by;

generating the grid ID based on spatial information contained in the geographical data object;

storing the geographical data object in a shard of the plurality of shards based on the grid ID;

generating a shardlet ID indicating a shardlet location in the shard where the geographical data object is stored;

generating a sequence ID indicating data placement of the geographical data object within the shardlet location; and

assigning the data object ID to the stored geographical data object, the data object ID comprising the grid ID, the shardlet ID, and the sequence ID.

15. The method of claim 14, further comprising using the data object ID as a primary key for the distributed database system, wherein the distributed database system comprises index organized tables.

16. The method of claim 14, further comprising using the data object ID as a first component of a clustered key for the distributed database system, wherein the distributed database system comprises SQL databases.

17. The method of claim 14, further comprising maintaining the data object ID as a sole data object ID for the geographical data object for a lifetime of the geographical data object.

18. A system for improving efficiency of storage and retrieval of geographic data in a distributed database system by generating a data object identifier (ID), the system comprising:

a plurality of append-only shards, each storing a plurality of geographical data objects;

a central database, storing a mapping of a plurality of shardlet IDs to the plurality of append-only shards where a first geographical data object is stored;

a processor, configured to execute instructions, the instructions comprising;

receiving the first geographical data object for storage in the distributed database system;

generating a grid ID based on spatial information contained in the first geographical data object;

storing the first geographical data object in an append-only shard of the plurality of append-only shards based on the grid ID;

generating a shardlet ID indicating a shardlet location in the append-only shard where the first geographical data object is stored;

generating a sequence ID indicating data placement of the first geographical data object within the shardlet location;

assigning a data object ID to the stored first geographical data object, the data object ID comprising the grid ID, the shardlet ID, and the sequence ID; and

in response to receiving a request from a user to access the stored first geographical data object, retrieving the stored first geographical data object from the distributed database system based on the data object ID.

19. The distributed database system of claim 18, wherein the plurality of append-only shards are located remotely from one another.