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.
Claims20
A method performed by an information retrieval system, the method comprising:
- generating an inverted index for a corpus of documents by creating, for each of at least some terms included in the corpus, a positional posting data structure, wherein the positional posting data structure encodes a corresponding term pair for said each term using a corresponding numeric value, and wherein each corresponding term pair includes a corresponding document identifier and corresponding positional information of an occurrence of said each term within the documents;
- determining, for each document and term pair for a given term, a count of occurrences of the given term within the document;
- based on the determined count, selectively encoding the positional posting data structure such that:
- when the count satisfies a first condition, multiple occurrences of the given term within the document are collectively represented by a first numeric value associated with the document identifier, and
- when the count satisfies a second condition different from the first condition, individual occurrences of the given term within the document are each represented by respective numeric values associated with the document identifier;
- and
- storing the selectively encoded positional posting data structure in a memory to facilitate use in term-based query evaluation.
A computer 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 computer system to:
- generate an inverted index for a corpus of documents by creating, for each of at least some terms included in the corpus, a positional posting data structure, wherein the positional posting data structure encodes a corresponding term pair for said each term using a corresponding numeric value, and wherein each corresponding term pair includes a corresponding document identifier and corresponding positional information of an occurrence of said each term within the documents;
- determine, for each document and term pair for a given term, a count of occurrences of the given term within the document;
- based on the determined count, selectively encode the positional posting data structure such that:
- when the count satisfies a first condition, multiple occurrences of the given term within the document are collectively represented by a first numeric value associated with the document identifier, and
- when the count satisfies a second condition different from the first condition, individual occurrences of the given term within the document are each represented by respective numeric values associated with the document identifier;
- and
- store the selectively encoded positional posting data structure in a memory to facilitate use in term-based query evaluation.
One or more hardware storage devices that store instructions that are executable by one or more processors to cause the one or more processors to:
- generate an inverted index for a corpus of documents by creating, for each of at least some terms included in the corpus, a positional posting data structure, wherein the positional posting data structure encodes a corresponding term pair for said each term using a corresponding numeric value, and wherein each corresponding term pair includes a corresponding document identifier and corresponding positional information of an occurrence of said each term within the documents;
- determine, for each document and term pair for a given term, a count of occurrences of the given term within the document;
- based on the determined count, selectively encode the positional posting data structure such that:
- when the count satisfies a first condition, multiple occurrences of the given term within the document are collectively represented by a first numeric value associated with the document identifier, and
- when the count satisfies a second condition different from the first condition, individual occurrences of the given term within the document are each represented by respective numeric values associated with the document identifier;
- and
- store the selectively encoded positional posting data structure in a memory to facilitate use in term-based query evaluation.
Dependencies are inferred from the claim text.