Compactly storing geodetic points

• US 9,602,129 B2
• Filed: 03/15/2013
• Issued: 03/21/2017
• Est. Priority Date: 03/15/2013
• Status: Expired due to Fees

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Srivatsa, Mudhaker, Agrawal, Dakshi, Ganti, Raghu Kiran
• Primary Examiner(s): Rostami, Mohammad S
• Application Number:
  US13/839,985
• Publication Number:
  US 20140279970A1
• Time in Patent Office: 1,467 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/6011 Encoder aspects

Abstract

Mechanisms are provided for the compact storage of geographical geometries as a collection of points, where individual points are encoded as binary/ternary strings (with the property that points closer to each other share a longer binary/ternary prefix) and the geometry is encoded by compressing the binary/ternary representation of common-prefix points. Mechanisms are also provided for the representation of a geometry using a ternary string that allows efficient storage of arbitrary shapes (e.g., long line segments, oblong polygons) as opposed to binary representations that are more efficient when the geometries are square or nearly square shaped.

Claims

1. A computer readable storage device, tangibly embodying a program of instructions executable by the computer for storing a geometry represented by a plurality of geodetic points, the program of instructions, when executing, performing the following steps:

assigning, to each of the plurality of points of the geometry, a respective string, wherein each string has characters that are selected from the group of binary characters and ternary characters, and wherein each string has a prefix portion and a non-prefix portion;

reducing an amount of storage required to store the assigned strings associated with the geometry, wherein the reducing comprises applying compression to the strings associated with the geometry that exploits at least one common prefix that is shared by at least a first one of the strings associated with the geometry and a second one of the strings associated with the geometry; and

storing the compressed strings associated with the geometry;

wherein the geometry comprises at least one of a line segment and a polygon;

wherein a length of the strings varies based upon an amount of geographic precision to be provided by the strings; and

wherein a length of bit representation in the strings of latitude differs from a length of bit representation in the strings of longitude.

2. The computer readable storage device of claim 1, wherein all of the characters of each string are binary characters.

3. The computer readable storage device of claim 1, wherein all of the characters of each string are ternary characters.

4. The computer readable storage device of claim 1, wherein at least one of the strings has at least one binary character and at least one ternary character.

5. The computer readable storage device of claim 1, wherein the compression comprises one of:

(a) LZW encoding; and

(b) Huffman Coding.

11. The computer readable storage device of claim 1, wherein the geometry comprises an oblong geometry.

13. The computer readable storage device of claim 1, wherein the length of bit representation in the strings of latitude is larger than the length of bit representation in the strings of longitude such that less precision is provided for the longitude than for the latitude.

6. A computer-implemented system for storing a geometry represented by a plurality of geodetic points, the system comprising:

a processor; and

a memory storing computer readable instructions that, when executed by the processor, implement;

an input element configured to receive each of the plurality of points of the geometry;

an assigning element in operative communication with the input element configured to assign, to each of the plurality of points of the geometry, a respective string, wherein each string has characters that are selected from the group of binary characters and ternary characters, and wherein each string has a prefix portion and a non-prefix portion;

a reducing element in operative communication with the assigning element configured to reduce an amount of storage required to store the assigned strings associated with the geometry, wherein the reduction comprises applying compression to the strings associated with the geometry that exploits at least one common prefix that is shared by at least a first one of the strings associated with the geometry and a second one of the strings of the geometry; and

a storing element in operative communication with the reducing element configured to store the compressed strings associated with the geometry;

wherein the geometry comprises at least one of a line segment and a polygon;

wherein a length of the strings varies based upon an amount of geographic precision to be provided by the strings; and

wherein a length of bit representation in the strings of latitude differs from a length of bit representation in the strings of longitude.

7. The system of claim 6, wherein all of the characters of each string are binary characters.

8. The system of claim 6, wherein all of the characters of each string are ternary characters.

9. The system of claim 6, wherein at least one of the strings has at least one binary character and at least one ternary character.

10. The system of claim 6, wherein the compression comprises one of:

(a) LZW encoding; and

(b) Huffman Coding.

12. The system of claim 6, wherein the geometry comprises an oblong geometry.

14. The system of claim 6, wherein the length of bit representation in the strings of latitude is larger than the length of bit representation in the strings of longitude such that less precision is provided for the longitude than for the latitude.