US 2015/0317334 A1Published application

Sparse datatable data structure

AssigneeMicrosoft Corporation

InventorsSudarshan Raghunathan, Samuel I. Weiss

Life of this patent

Estimating the term…

Loading patent…

Abstract

A sparse dataset structure is created by creating column vectors for one or more columns in a dataset that have at least one significant value. Each column vector includes data values for columns of the dataset. Each column vector that is a sparse column vector includes a look-up index array and a value array. Entries in the look-up index array represent columns. The value array includes values for a row in a column. Each entry in the value array points to a row entry in the look-up index array. A side structure includes a row index and a column index. The row index includes a location for an entry for each row where entries point to a location in the column index that identifies a column that has a first significant entry for a row. Alternatively a sparse dataset could be constructed with sparse rows.

Claims42

Dependent claims

In a computing environment a method of creating a representation of a data table having one or more sparse first dimension spaces, the method comprising:

creating a sparse dataset structure by creating a first dimension space vector for each first dimension space in a dataset that has at least one significant value, each first dimension space vector comprising data values for first dimension spaces of the dataset, the sparse data structure comprising one or more sparse first dimension space vectors for sparse first dimension spaces in the dataset, and wherein for each first dimension space vector that is a sparse first dimension space vector, the first dimension space vector includes:
a look-up index array where entries in the look-up index array represent second dimension spaces in the dataset;
and
a value array where each entry in the value array comprises a value of an entry of a second dimension space in the first dimension space vector, and wherein each entry in the value array corresponds to a second dimension space entry in the look-up index array;
creating a side structure, wherein the side structure comprises a second dimension space index and a first dimension space index, wherein the second dimension space index comprises a location for each second dimension space in the dataset where a location can have an entry for a corresponding second dimension space and where an entry for a given second dimension space points to a location in the first dimension space index that has an entry that identifies a first dimension space that has a first significant entry for the given second dimension space, and wherein the first dimension space index comprises an entry for each significant entry in the sparse dataset organized by second dimension spaces.

2 more elements

In a computing environment a method of retrieving a second dimension space from a sparse dataset structure, the method comprising:

accessing a side structure of a sparse dataset to identify second dimension space entries for a second dimension space, wherein the sparse dataset comprises a first dimension space vector for each first dimension space in a dataset that has at least one significant value, each first dimension space vector comprising data values for first dimension spaces of the dataset, the sparse data structure comprising one or more sparse first dimension space vectors for sparse first dimension spaces in the dataset, and wherein for each first dimension space vector that is a sparse first dimension space vector, the first dimension space vector includes:
a look-up index array where entries in the look-up index array represent second dimension spaces in the dataset;
and
a value array where each entry in the value array comprises a value of an entry of a second dimension space in the first dimension space vector, and wherein each entry in the value array corresponds to a second dimension space entry in the look-up index array;
wherein the side structure comprises a second dimension space index and a first dimension space index, wherein the second dimension space index comprises a location for each second dimension space in the dataset where a location can have an entry for a corresponding second dimension space and where an entry for a given second dimension space points to a location in the first dimension space index that has an entry that identifies a first dimension space that has a first significant entry for the given second dimension space, and wherein the first dimension space index comprises an entry for each significant entry in the sparse dataset organized by second dimension spaces;
and
wherein accessing the side structure comprises:
accessing an entry in the first dimension space index for the first significant entry in the sparse dataset for the second dimension space;
and
accessing subsequent entries in the first dimension space index for the second dimension space;
and
using the first entry and the subsequent entries, obtaining data values for the second dimension space from one or more of the sparse first dimension space vectors.

9 more elements

A physical computer readable storage medium comprising computer executable instructions that when executed by one or more processors causes the following to be performed:

creating a sparse dataset structure by creating a first dimension space vector for each first dimension space in a dataset that has at least one significant value, each first dimension space vector comprising data values for first dimension spaces of the dataset, the sparse data structure comprising one or more sparse first dimension space vectors for sparse first dimension spaces in the dataset, and wherein for each first dimension space vector that is a sparse first dimension space vector, the first dimension space vector includes:
a look-up index array where entries in the look-up index array represent second dimension spaces in the dataset;
and
a value array where each entry in the value array comprises a value of an entry of a second dimension space in the first dimension space vector, and wherein each entry in the value array corresponds to a second dimension space entry in the look-up index array;
creating a side structure, wherein the side structure comprises a second dimension space index and a first dimension space index, wherein the second dimension space index comprises a location for each second dimension space in the dataset where a location can have an entry for a corresponding second dimension space and where an entry for a given second dimension space points to a location in the first dimension space index that has an entry that identifies a first dimension space that has a first significant entry for the given second dimension space, and wherein the first dimension space index comprises an entry for each significant entry in the sparse dataset organized by second dimension spaces.

2 more elements

A physical computer readable storage medium comprising computer executable instructions that when executed by one or more processors causes the following to be performed:

accessing a side structure of a sparse dataset to identify second dimension space entries for a second dimension space, wherein the sparse dataset comprises a first dimension space vector for each first dimension space in a dataset that has at least one significant value, each first dimension space vector comprising data values for first dimension spaces of the dataset, the sparse data structure comprising one or more sparse first dimension space vectors for sparse first dimension spaces in the dataset, and wherein for each first dimension space vector that is a sparse first dimension space vector, the first dimension space vector includes:
a look-up index array where entries in the look-up index array represent second dimension spaces in the dataset;
and
a value array where each entry in the value array comprises a value of an entry of a second dimension space in the first dimension space vector, and wherein each entry in the value array corresponds to a second dimension space entry in the look-up index array;
wherein the side structure comprises a second dimension space index and a first dimension space index, wherein the second dimension space index comprises a location for each second dimension space in the dataset where a location can have an entry for a corresponding second dimension space and where an entry for a given second dimension space points to a location in the first dimension space index that has an entry that identifies a first dimension space that has a first significant entry for the given second dimension space, and wherein the first dimension space index comprises an entry for each significant entry in the sparse dataset organized by second dimension spaces;
and
wherein accessing the side structure comprises:
accessing an entry in the first dimension space index for the first significant entry in the sparse dataset for the second dimension space;
and
accessing subsequent entries in the first dimension space index for the second dimension space;
and
using the first entry and the subsequent entries, obtaining data values for the second dimension space from one or more of the sparse first dimension space vectors.

9 more elements

In a computing environment a system for creating a representation of a data table having one or more sparse first dimension spaces, the system comprising:

one or more processors;
one or more computer readable media comprising computer executable instructions that when executed by one or more processors causes the following to be performed:
creating a sparse dataset structure by creating a first dimension space vector for each first dimension space in a dataset that has at least one significant value, each first dimension space vector comprising data values for first dimension spaces of the dataset, the sparse data structure comprising one or more sparse first dimension space vectors for sparse first dimension spaces in the dataset, and wherein for each first dimension space vector that is a sparse first dimension space vector, the first dimension space vector includes:
a look-up index array where entries in the look-up index array represent second dimension spaces in the dataset;
and
a value array where each entry in the value array comprises a value of an entry of a second dimension space in the first dimension space vector, and wherein each entry in the value array corresponds to a second dimension space entry in the look-up index array;
creating a side structure, wherein the side structure comprises a second dimension space index and a first dimension space index, wherein the second dimension space index comprises a location for each second dimension space in the dataset where a location can have an entry for a corresponding second dimension space and where an entry for a given second dimension space points to a location in the first dimension space index that has an entry that identifies a first dimension space that has a first significant entry for the given second dimension space, and wherein the first dimension space index comprises an entry for each significant entry in the sparse dataset organized by second dimension spaces.

4 more elements

In a computing environment a system for retrieving a second dimension space from a sparse dataset structure, the system comprising:

one or more processors;
one or more computer readable media comprising computer executable instructions that when executed by one or more processors causes the following to be performed:
accessing a side structure of a sparse dataset to identify second dimension space entries for a second dimension space, wherein the sparse dataset comprises a first dimension space vector for each first dimension space in a dataset that has at least one significant value, each first dimension space vector comprising data values for first dimension spaces of the dataset, the sparse data structure comprising one or more sparse first dimension space vectors for sparse first dimension spaces in the dataset, and wherein for each first dimension space vector that is a sparse first dimension space vector, the first dimension space vector includes:
a look-up index array where entries in the look-up index array represent second dimension spaces in the dataset;
and
a value array where each entry in the value array comprises a value of an entry of a second dimension space in the first dimension space vector, and wherein each entry in the value array corresponds to a second dimension space entry in the look-up index array;
wherein the side structure comprises a second dimension space index and a first dimension space index, wherein the second dimension space index comprises a location for each second dimension space in the dataset where a location can have an entry for a corresponding second dimension space and where an entry for a given second dimension space points to a location in the first dimension space index that has an entry that identifies a first dimension space that has a first significant entry for the given second dimension space, and wherein the first dimension space index comprises an entry for each significant entry in the sparse dataset organized by second dimension spaces;
and
wherein accessing the side structure comprises:
accessing an entry in the first dimension space index for the first significant entry in the sparse dataset for the second dimension space;
and
accessing subsequent entries in the first dimension space index for the second dimension space;
and
using the first entry and the subsequent entries, obtaining data values for the second dimension space from one or more of the sparse first dimension space vectors.

11 more elements

Dependencies are inferred from the claim text.