US 12,585,675 B2Granted

Hybrid positional posting lists

AssigneeMicrosoft Technology Licensing, LLC

InventorAlexander Ulrich Neubeck

Life of this patent

Estimating the term…

Abstract

An information retrieval system uses an inverted indexing system composed of hybrid positional posting lists. A hybrid positional posting list includes a number of postings, where each posting contains a single numeric value to represent both the document containing a term and the location of the term in the document. When the number of postings for a document exceeds a threshold, a single-valued posting represents all the locations of a term in a document and the locations within the document. When the number of postings for a document is less than a threshold, each location of a term and the associated document is represented by a single-valued posting. In this manner, the storage requirements for the inverted indexing system are reduced and the processing speed increased.

Claims16

Dependent claims

A system comprising:

one or more processors;
and
one or more hardware storage devices that store instructions that are executable by the one or more processors to cause the system to:
access a first document of that is included among a plurality of documents of an information retrieval system, the information retrieval system uses an inverted index table to map tokens that are included in the plurality of documents, wherein:
the inverted index table comprises a hybrid positional posting list for the tokens included in the plurality of documents,
the hybrid positional posting list comprises a plurality of postings,
a posting of the plurality of postings for a select token comprises a single numeric value that identifies a document identifier and a positional identifier,
the single numeric value is mapped to the document identifier and the positional identifier using a bitrank vector and a global position block,
the document identifier identifies a select document of the plurality of documents comprising the select token,
the positional identifier identifies a special position reference or a global position of the select token relative to the plurality of documents, and
the special position reference for the select document identifies all of the positions of the plurality of tokens in the select document;
tokenize the first document into a plurality of tokens, wherein each token of the plurality of tokens is associated with a corresponding local position in the first document;
map local positions of the plurality of tokens in the first document to corresponding global positions, which are global across all the documents in the plurality of documents, wherein said mapping is based on the global position block for the first document;
when a number of the local positions in the first document exceeds a first threshold:
generate a first posting for a first token comprising the special position reference for the first document;
and
insert the first posting into a hybrid positional posting list for the first token in the inverted index table;
and
when the number of local positions in the first document does not exceed the first threshold, generate a second posting for the first token comprising a second single numeric value to represent both the first document and a select global position of the first token at a select location in the first document.

16 more elements

A computer-implemented method comprising:

obtaining a search query including at least one token and at least one operation;
accessing an inverted index table for an information retrieval system hosting a plurality of documents, the inverted index table comprising a plurality of hybrid positional posting lists, wherein:
a hybrid positional posting list comprises a plurality of postings, and
a posting of the plurality of postings comprises a single numeric value that identifies a specific document of the plurality of documents including a select token and global positions of the select token within the plurality of documents;
searching for a first hybrid positional posting list for a first token, wherein the first hybrid positional posting list comprises a first posting comprising a first single numeric value for the first token;
mapping the first single numeric value of the first posting into a document identifier and a positional identifier, wherein the single numeric value is mapped to the document identifier and the positional identifier using a bitrank vector and a global position block, wherein the document identifier identifies a first document comprising the first token, and wherein the position identifier identifies a position of the first token in the first document;
and
performing at least one operation using the document identifier and the first positional identifier associated with the at least one token.

5 more elements

A computer-implemented method comprising:

accessing an inverted index table for a plurality of repositories of an information retrieval system, wherein:
the inverted index table includes a hybrid positional posting list for a repository property,
the repository property is a characteristic of a repository of the plurality of repositories,
a hybrid positional posting list includes at least one posting for the repository property,
the at least one posting for the repository property comprises a single numeric value that comprises a document identifier and a positional identifier,
the single numeric value is mapped to the document identifier and the positional identifier using a bitrank vector and a global position block,
the document identifier identifies a document stored in one of the plurality of repositories having the repository property, and
the positional identifier identifies a select repository storing the document having the repository property from a position in a list of associated repositories for the document;
obtaining a first document stored in a first repository of the plurality of repositories, wherein the first document contains a first list of associated repositories storing the first document;
obtaining a first repository property associated with the first repository;
mapping the first repository property into a respective global position within the first list of associated repositories storing the first document;
generating a first posting for the first repository property, the first posting comprising the single numeric value, which is mapped to the document identifier and the positional identifier, wherein the document identifier identifies the first document and the positional identifier identifies a position in the list of associated repositories storing the first document having the repository property;
and
inserting the first posting for the first repository property into the hybrid positional posting list of the inverted index table.

11 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

A system comprising:

one or more processors;
and
one or more hardware storage devices that store instructions that are executable by the one or more processors to cause the system to:
access a first document of that is included among a plurality of documents of an information retrieval system, the information retrieval system uses an inverted index table to map tokens that are included in the plurality of documents, wherein:
the inverted index table comprises a hybrid positional posting list for the tokens included in the plurality of documents,
the hybrid positional posting list comprises a plurality of postings,
a posting of the plurality of postings for a select token comprises a single numeric value that identifies a document identifier and a positional identifier,
the single numeric value is mapped to the document identifier and the positional identifier using a bitrank vector and a global position block,
the document identifier identifies a select document of the plurality of documents comprising the select token,
the positional identifier identifies a special position reference or a global position of the select token relative to the plurality of documents, and
the special position reference for the select document identifies all of the positions of the plurality of tokens in the select document;
tokenize the first document into a plurality of tokens, wherein each token of the plurality of tokens is associated with a corresponding local position in the first document;
map local positions of the plurality of tokens in the first document to corresponding global positions, which are global across all the documents in the plurality of documents, wherein said mapping is based on the global position block for the first document;
when a number of the local positions in the first document exceeds a first threshold:
generate a first posting for a first token comprising the special position reference for the first document;
and
insert the first posting into a hybrid positional posting list for the first token in the inverted index table;
and
when the number of local positions in the first document does not exceed the first threshold, generate a second posting for the first token comprising a second single numeric value to represent both the first document and a select global position of the first token at a select location in the first document.

16 more elements