US 8,615,519 B2 · Method and system for inverted indexing of a dataset

Abstract

Methods and systems for providing an inverted index for a dataset are disclosed. The inverted index includes a position vector, with fields that correspond to values in the indexed dataset. The fields include data to be used in determining where each value appears in the dataset. The position vector is populated differently for different value types. A 1:1 value appears once in the dataset; a 1:n value appears multiple times. For a 1:1 value, the position vector stores information for where that value appears. For a 1:n value, the position vector stores a pointer, e.g. a memory reference, that identifies a list of locations where the value appears. The list can be encoded or otherwise compressed. A set of indicators can be stored for the fields indicating whether the field has 1:n or 1:1 value information. The indicator is used to control interpretation of the information in a field.

Claims20

Dependent claims

A machine-implemented method providing an inverted index of a dataset, comprising:

identifying a 1:1 value to be represented in the inverted index, the 1:1 value being a value that appears once in the dataset;
determining an identifier of the location in the dataset at which the 1:1 value appears;
identifying a 1:n value to be represented in the inverted index, the 1:n value being a value which appears a plurality of times in the dataset;
determining a pointer to a list of locations where the 1:n value appears in the dataset;
forming a position vector comprising fields corresponding to values to be represented in the inverted index, the forming comprising storing the determined identifier of the location for the 1:1 value in the field corresponding to the 1:1 value, and storing the pointer for the 1:n value in the field corresponding to the 1:n value;
and
storing the position vector and the list of locations on a tangible non-transitory machine readable storage medium.

4 more elements

A non-transitory machine readable medium storing machine executable instructions for causing a machine to implement a method of providing an inverted index of a dataset, the method comprising:

identifying a 1:1 value to be represented in the inverted index, the 1:1 value being a value that appears once in the dataset;
determining an identifier of the location in the dataset at which the 1:1 value appears;
identifying a 1:n value to be represented in the inverted index, the 1:n value being a value that appears a plurality of times in the dataset;
determining a pointer to a list of locations where the 1:n value appears in the dataset;
forming a position vector comprising a field for each value appearing in the inverted index, the forming comprising storing the determined identifier of the location for the 1:1 value in the field associated with the 1:1 value, and storing the pointer for the 1:n value in the field associated with the 1:n value;
and
storing the position vector and the list of locations on a tangible machine readable medium.

4 more elements

Dependencies are inferred from the claim text.

Method and system for inverted indexing of a dataset

Life of this patent

Method and system for inverted indexing of a dataset

Life of this patent

Abstract

Claims20