US 12,504,910 B1Granted

Optimized data structure, and method of generating same, for efficient storage of data in, and retrieval from, a computer memory

AssigneeChicago Mercantile Exchange Inc.

InventorsAjay Sunderajan Madhavan, Jayanth Pridhvi Raj Recherla, Balaji Rengachari

Life of this patent

Estimating the term…

Loading patent…

Abstract

The disclosed embodiments relate to systems and methods for generating a compact in memory key-value data structure/database which may or may not be hierarchical, i.e., include nested key-value data structures, which can be utilized for other applications. The key-value data to be encoded and stored in the generated database may be extracted from another database, such as a relational database, or other source. It will be appreciated that the disclosed embodiments may be used to encode and store any data, not just key-value data sets, which would benefit from the compact long-aligned form generated thereby. The resultant compact data structure may be efficiently accessed to directly retrieve particular data or search for particular data and such access may be enabled using a defined notation/syntax and/or one or more intermediary processes or programs.

Claims37

Dependent claims

A computer implemented method for storing data in a memory, the method comprising:

receiving, by a processor characterized by a minimum number of bits that must be operated on in a single operation, electronic data indicative of each symbol of an ordered plurality of symbol sequences, each symbol sequence comprising a sequence of symbols selected from a set of symbols;
for each symbol of each symbol sequence in the order in which the symbol sequence appears in the ordered plurality of symbol sequences, converting, by the processor, the data indicative thereof to a minimal representation which includes a minimum number of bits necessary to uniquely represent the symbol among the set of symbols;
arranging, by the processor for each symbol sequence, the minimal representation of each symbol thereof into one or more groups in the order in which the symbol sequence appears in the ordered plurality of symbol sequences, each group characterized by a size no larger than the minimum number of bits that must be operated on in a single operation;
and
storing, by the processor in the memory, each of the groups of minimal representations of each symbol of each symbol sequence in the order in which the symbol sequence appears in the ordered plurality of symbol sequences in contiguous memory locations with respect to the others of the groups of minimal representations of each symbol of each symbol sequence.

2 more elements

A system for storing data in a memory, the system comprising:

a data receiver, coupled with a processor characterized by a minimum number of bits that must be operated on in a single operation, operative to receive electronic data indicative of each symbol of an ordered plurality of symbol sequences, each symbol sequence comprising a sequence of symbols selected from a set of symbols;
an encoder coupled with the data receiver and operative to, for each symbol of each symbol sequence in the order in which the symbol sequence appears in the ordered plurality of symbol sequences, convert the data indicative thereof to a minimal representation which includes a minimum number of bits necessary to uniquely represent the symbol among the set of symbols;
a data arranger coupled with the encoder and operative to arrange, for each symbol sequence, the minimal representation of each symbol thereof into one or more groups in the order in which the symbol sequence appears in the ordered plurality of symbol sequences, each group characterized by a size no larger than the minimum number of bits that must be operated on in a single operation;
and
a data writer coupled with the data arranger and operative to store, in the memory, each of the groups of minimal representations of each symbol of each symbol sequence in the order in which the symbol sequence appears in the ordered plurality of symbol sequences in contiguous memory locations with respect to the others of the groups of minimal representations of each symbol of each symbol sequence.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application: 17/503,925Filed 18 Oct 2021
Granted: 23 Dec 2025
Term ends: Not estimatedThe source records don’t support an estimate.

Classification14 codes

G06F 3/0655
Making use of a particular technique: vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more…
G06F 3/0604
Specifically adapted to achieve a particular effect: improving or facilitating administration, e.g. storage management
G06F 3/0638
Making use of a particular technique: organizing or formatting or addressing of data
G06F 3/0679
Single storage device: non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]