US 11,144,522 B2Granted

Data storage using vectors of vectors

AssigneeKinaxis Inc.

InventorsRobert Nigel Walker, Marin Creanga, Dylan Ellicott

Life of this patent

Estimating the term…

Loading patent…

Abstract

The systems and methods described here can reduce the storage space required (memory and/or disk) to store certain types of data, provide efficient (fast) creation, modification and retrieval of such data, and support such data within the framework of a multi-version database. In some embodiments, the systems and methods can store each field of a set of records as a vector of values, e.g., a data vector. A set of records can be represented using a vector hash vector, or “vhash” vector, wherein each element of the vhash vector contains a unique identifier of a data vector, based on a cryptographic hash of the data vector. A header table can store associations between labels and “vhash” vectors that pertain to those labels. Identical data vectors can be re-used between different record sets or vhash vectors needing that vector, thus saving space.

Claims30

Dependent claims

A data storage and retrieval system for a computer memory, the system comprising:

at least one processor for configuring the computer memory to store data in accordance with a first header table, a first Vhash vector, a first set of two or more data vectors, a second header table, a second Vhash vector and a second set of two or more data vectors;
wherein:
each of:
the first Vhash vector, the two or more data vectors from the first set, the second Vhash vector, and the two or data vectors from the second set are each assigned a respective unique identifier that is a content-based hash;
the first header table includes an association between a first key label and a first Vhash Vector Hash, the first Vhash Vector Hash being a unique memory location reference associated with the first Vhash vector;
each element of the first Vhash vector is configured to store a unique memory location reference associated with a corresponding data vector of the first set of data vectors;
each element of each data vector of the first set of data vectors is configured to store a payload of data corresponding to a field associated with the first key label;
each data vector of the first set of data vectors has an identical number of elements;
the second header table includes an association between a second key label and a second Vhash Vector Hash, the second Vhash Vector Hash being a unique memory location reference associated with the second Vhash vector;
each element of the second Vhash vector is configured to store a unique memory location reference associated with a corresponding data vector of the second set of data vectors;
each element of each data vector of the second set of data vectors is configured to store a payload of data corresponding to a field associated with the second key label;
each data vector of the second set of data vectors has an identical number of elements as each data vector of the first set of data vectors;
and
the first set of data vectors and the second set of data vectors have at least one data vector in common;
and
the first Vhash vector and the second Vhash vector each have at least one element configured to store a unique memory location reference in common, the at least one element configured to store a unique memory location reference in common in the first Vhash vector and the second Vhash vector is associated with the at least one data vector in common.

13 more elements

A method of storing and retrieving data in a computer memory, the method comprising:

configuring, by a processor, the computer memory to store data in accordance with a first header table, a first Vhash vector, a first set of two or more data vectors, a second header table, a second Vhash vector and a second set of two or more data vectors;
wherein:
each of:
the first Vhash vector, the two or more data vectors from the first set, the second Vhash vector, and the two or data vectors from the second set are each assigned a respective unique identifier that is a content-based hash;
the first header table includes an association between a first key label and a first Vhash Vector Hash, the first Vhash Vector Hash being a unique memory location reference associated with the first Vhash vector;
each element of the first Vhash vector is configured to store a unique memory location reference associated with a corresponding data vector of the first set of data vectors;
each element of each data vector is configured to store a payload of data corresponding to a field associated with the first key label;
each data vector of the first set of data vectors has an identical number of elements;
the second header table includes an association between a second key label and a second Vhash Vector Hash, the second Vhash Vector Hash being a unique memory location reference associated with the second Vhash vector;
each element of the second Vhash vector is configured to store a unique memory location reference associated with a corresponding data vector of the second set of data vectors;
each element of each data vector of the second set of data vectors is configured to store a payload of data corresponding to a field associated with the second key label;
each data vector of the second set of data vectors has an identical number of elements as each data vector of the first set of data vectors;
the first set of data vectors and the second set of data vectors have at least one data vector in common;
and
the first Vhash vector and the second Vhash vector each have at least one element configured to store a unique memory location reference in common, the at least one element configured to store a unique memory location reference in common in the first Vhash vector and the second Vhash vector is associated with the at least one data vector in common.

12 more elements

A computer memory comprising:

a first header table, a first Vhash vector, a first set of two or more data vectors, a second header table, a second Vhash vector and a second set of two or more data vectors,
wherein:
each of:
the first Vhash vector, the two or more data vectors from the first set, the second Vhash vector, and the two or data vectors from the second set are each assigned a respective unique identifier that is a content-based hash;
the first header table includes an association between a first key label and a first Vhash Vector Hash, the first Vhash Vector Hash being a unique memory location reference associated with the first Vhash vector;
each element of the first Vhash vector is configured to store a unique memory location reference associated with a corresponding data vector of the first set of data vectors;
each element of each data vector of the first set of data vectors is configured to store a payload of data corresponding to a field associated with the first key label;
each data vector of the first set of data vectors has an identical number of elements;
the second header table includes an association between a second key label and a second Vhash Vector Hash, the second Vhash Vector Hash being a unique memory location reference associated with the second Vhash vector;
each element of the second Vhash vector is configured to store a unique memory location reference associated with a corresponding data vector of the second set of data vectors;
each element of each data vector of the second set of data vectors is configured to store a payload of data corresponding to a field associated with the second key label;
each data vector of the second set of data vectors has an identical number of elements as each data vector of the first set of data vectors;
the first set of data vectors and the second set of data vectors have at least one data vector in common;
and
the first Vhash vector and the second Vhash vector each have at least one element configured to store a unique memory location reference in common, the at least one element configured to store a unique memory location reference in common in the first Vhash vector and the second Vhash vector is associated with the at least one data vector in common.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/391,900Filed 23 Apr 2019 · continuation in part
Priority: 27 Oct 2014
Published: US 2019/0251069 A115 Aug 2019
Granted: 12 Oct 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification9 codes

G06F 16/2237
Indexing structures: vectors, bitmaps or matrices
H04L 9/0643
The encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions;…
G06F 16/2255
Indexing structures: hash tables
G06F 16/2282
Indexing; Data structures therefor; Storage structures: tablespace storage structures; Management thereof

Family

Application62/068,938Us provisional application · filed 27 Oct 2014
Application14/924,115Parent of this continuation-in-part · filed 27 Oct 2015
US 2019/0251069 A1Pre-grant publication · published 15 Aug 2019
US 11,138,233 B2Related patent
US 2016/0117378 A1Published application
US 11,144,522 B2This patent

From the US filing history. Foreign family members aren’t listed.