Method for Creating a Scalable Graph Database Using Coordinate Data Elements

• US 20080243908A1
• Filed: 04/14/2008
• Published: 10/02/2008
• Est. Priority Date: 03/29/2007
• Status: Active Grant

• Current Assignee: Franz, Inc. (TallyGo LLC)
• Original Assignee: Franz, Inc. (TallyGo LLC)
• Inventors: Aasman, Jannes, Haflich, Steven M.
• Granted Patent: US 8,244,772 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Embodiments of a method for creating a graph database which is arranged to store data in the form of graph tuples comprising n-parts, are described. In an embodiment, each tuple-part is encoded into a unique part identifier (UPI). A geospatial UPI is defined for two-dimensional data elements that include a plurality of data points defined by respective pairs of an X-ordinate and a Y-ordinate. A two-dimensional data space is divided into a plurality of uniform Y strips of defined widths. The Y-strip width is selected to correspond approximately to an anticipated Y dimension of a typical search region of interest. The geospatial UPI encodes a plurality of coordinate points in a two-dimensional data space into a single datum that includes respective pairs of an X-ordinate and a Y-ordinate. The geospatial UPI comprises a data structure arranged in order of sort priority by the geospatial UPI type code, geospatial subtype, and Y-strip identifier followed by the X-ordinate data and Y-ordinate data. The component fields of the data structure are arranged so that the datum can be sorted linearly as a single unsigned integer, thus facilitating a search over a two dimensional region of the data by allowing a search process to linearly scan a limited identifiable region of each of the several strips overlapping the search region of interest.

Claims

1. A method comprising:

defining a geospatial datatype for encoding a plurality of coordinate points in a two-dimensional data space into a single datum that includes respective pairs of an X-ordinate and a Y-ordinate;

dividing the two-dimensional data space into a plurality of uniform Y strips, each of a defined width;

converting the X-ordinates and Y-ordinates to a normalized number format;

defining a data structure for the datum comprising a strip number followed by X-ordinate data followed by Y-ordinate data for each strip of the plurality of Y strips;

defining a sub-type based on the X-ordinate data, Y-ordinate data and the defined width of a Y strip; and

encoding the sub-type in the data structure, wherein the component fields of the data structure are arranged so that the datum can be sorted linearly as a single unsigned integer.

2. The method of claim 1 wherein the data structure is arranged with the geospatial datatype as the most significant field followed in order of significance by the geospatial subtype, Y-strip identifier, normalized X-ordinate, and normalized Y-ordinate.

3. The method of claim 2 wherein the data structure comprises a unique part identifier for use in a triple store.

4. The method of claim 3, wherein the normalized number format comprises an unsigned 32-bit integer.

5. The method of claim 3 wherein the X-ordinates and Y-ordinates comprise geospatial data in which the X-ordinates and Y-ordinates have similar ordinate measures, or the X-ordinates and Y-ordinates have dissimilar measures.

6. The method of claim 5 wherein the geospatial data comprises geographic location data, and wherein each geospatial datum consists of one spherical coordinate or one Cartesian coordinate.

7. The method of claim 6, wherein the defined width corresponds to an anticipated Y dimension of a typical search region of interest.

8. The method of claim 7, wherein the unique part identifier comprises at least one part of a triple that includes at least three parts.

9. The method of claim 8, wherein the unique part identifier facilitates a search over a two dimensional region of the data by allowing a search process to linearly scan a limited identifiable region of each of the several strips overlapping the search region of interest.

10. The method of claim 9 wherein each part of the triple is encoded with a unique part identifier, the unique part identifier comprising a tag that identifies a datatype for the part, and a code that encodes the data content for the part, wherein the code preserves a relative ranking of the data content for the corresponding datatype within a plurality of triples.

11. The method of claim 10, further comprising storing the tag in a fixed field of the unique part identifier, and wherein the tag comprises a datatype identifier.

12. The method of claim 11 further comprising:

storing each of the plurality of triples in a transaction log; and

sorting each of the plurality of triples based on a part of each triple to create a number of indices, each index of which comprises the plurality of triples sorted according to a particular ordering of the component parts.

13. The method of claim 12 wherein the triples are provided by a data source selected from the group consisting of semantic web data, comma-separated value data, relational database data, and real-time data.

14. A method of encoding geospatial coordinate data consisting of pairs or X-ordinates and Y-ordinates into a single sortable data structure comprising:

defining a first field as a geospatial datatype identifier;

defining a second field as a geospatial subtype identifier;

defining a third field as a Y-strip identifier, the Y-strip identifier identifying a specific Y-strip of a plurality of Y-strips into which a two-dimensional data space the geospatial coordinate data is divided;

defining a fourth field as a normalized X-ordinate value; and

defining a fifth field as a normalized Y-ordinate value.

15. The method of claim 14 wherein the X-ordinates value and Y-ordinates are normalized as 32-bit unsigned integer values.

16. The method of claim 15, wherein Y-strip is of a defined width that corresponds to an anticipated Y dimension of a typical search region of interest.

17. The method of claim 16 wherein the wherein the fields of the data structure are arranged so that the datum can be sorted linearly as a single unsigned integer.

18. The method of claim 17, wherein the data structure comprises a unique part identifier (UPI) that facilitates a search over a two dimensional region of the data by allowing a search process to linearly scan a limited identifiable region of each of the several strips overlapping the search region of interest.

19. The method of claim 18 wherein the X-ordinates and Y-ordinates comprise geospatial data in which the X-ordinates and Y-ordinates have similar ordinate measures.

20. The method of claim 19 wherein the geospatial data comprises geographic location data.

21. The method of claim 20 further comprising:

storing the UPI as part of a triple; and

adding the triple to a data store storing a plurality of triples.

22. The method of claim 21 further comprising:

reading a plurality of geospatial coordinates from a source;

encoding each pair of geospatial coordinates in a respective UPI; and

storing each encoded UPI in the data store.