Compactly storing geodetic points
AssigneeInternational Business Machines Corporation
InventorsDakshi Agrawal, Raghu Kiran Ganti, Mudhakar Srivatsa
Life of this patent
Estimating the term…
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.
Claims15
1-7. (canceled)
A computer readable storage medium, 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 points, 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, wherein the reducing comprises applying compression to the strings that exploits at least one common prefix that is shared by at least a first one of the strings and second one of the strings;
- and
- storing the compressed strings.
A computer-implemented system for storing a geometry represented by a plurality of geodetic points, the system comprising:
- an input element configured to receive each of the points;
- an assigning element in operative communication with the input element configured to assign, to each of the points, 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, wherein the reduction comprises applying compression to the strings that exploits at least one common prefix that is shared by at least a first one of the strings and second one of the strings;
- and
- a storing element in operative communication with the reducing element configured to store the compressed strings.
Dependencies are inferred from the claim text.