US 8,914,380 B2Granted

Search index format optimizations

AssigneeMicrosoft Corporation

InventorsChadd Creighton Merrigan, Mihai Petriuc, Raif Khassanov, Artsiom Ivanovich Kokhan

Life of this patent

Estimating the term…

Loading patent…

Abstract

A search index structure which extends a typical composite index by incorporating an index which is optimized for fast retrieval from storage and which eliminates data which is specific to phrase searching. Other data is represented in a manner which allows it to be calculated rather than stored. Associating variable length entries with logical categories allows their length to be inferred from the category rather than stored. Using delta values between document IDs rather than the ID itself generates a compact, dense symbol set which is efficiently compressed by Huffman encoding or a similar compression method. Using an upper threshold to remove large, and thus rare, delta values from the symbol set prior to encoding further improves the encoding performance.

Claims20

Dependent claims

A method of searching a plurality of documents within a search domain, the method comprising:

determining the plurality of documents within the search domain contain a keyword;
determining a keyword occurrence count entry corresponding to the number of times the keyword occurs in each document of the plurality of documents;
providing a compressed document ID delta list having a series of document ID delta entries, one for each of the plurality of documents that contains the keyword;
providing an occurrence count list having a series of keyword occurrence count entries, one for each of the plurality of documents that contains the keyword;
associating each keyword occurrence count entry with one of a finite set of categories, wherein each category has an occurrence entry size, wherein each keyword occurrence count entry is of a size substantially equal to the occurrence entry size for the associated category, wherein each category comprises a category base value, and wherein each of the series of document ID delta entries is represented by a symbol that is a sum of a category base value for the associated category and an associated document ID delta entry;
providing an encoding table for compressing the document ID delta list, the encoding table having a code corresponding to each symbol, wherein a code ordering corresponds to an order of symbols in the finite set of categories, and wherein each symbol is calculated based on the code ordering;
providing a decoding table based on the encoding table for decompressing the document ID delta list;
and
searching the plurality of documents by using at least one of the encoding table and the decoding information.

6 more elements

A computing system for performing a method of searching for a keyword occurring in a plurality of documents within a search domain, the method comprising:

using an index to identify those documents containing the keyword, the index having an encoded document ID delta list, the document ID delta list having a plurality of entries, each entry using a symbol to represent a document ID delta value for each of the plurality of documents in the search domain that contains the keyword;
associating each of the symbols in the document ID delta list with one of a finite set of categories and with an order within each of the finite set of categories, wherein each category comprises a category base value and each symbol in the document ID delta list is a sum of the category base value and the document ID delta value that the symbol represents;
encoding the document ID delta list using an encoding table, a code ordering in the encoding table corresponding to an order of symbols in the finite set of categories, wherein each symbol corresponds to a code in the encoding table, and wherein each symbol is calculated based on the code ordering;
and
decoding the document ID delta list using a decoding table that is based on the encoding table.

2 more elements

A computer storage medium storing instructions for performing a method of searching for a keyword occurring in a plurality of documents within a search domain, the method comprising:

using an index to identify those documents containing the keyword, the index having an encoded document ID delta list, the encoded document ID delta list having a plurality of entries, each entry using a symbol to represent a document ID delta value for each of the plurality of documents in the search domain that contains the keyword;
associating each of the symbols in the encoded document ID delta list with one of a finite set of categories and with an order within each of the finite set of categories, wherein each category comprises a category base value and each symbol in the encoded document ID delta list is a sum of the category base value and the document ID delta value that the symbol represents;
encoding the document ID delta list using an encoding table, a code ordering in the encoding table corresponding to an order of symbols in the finite set of categories, wherein each symbol corresponds to a code in the encoding table, and wherein each symbol is calculated based on the code ordering;
and
decoding the document ID delta list using a decoding table based on the encoding table.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/424,137Filed 19 Mar 2012 · continuation
Priority: 13 Jun 2008
Published: US 2012/0179668 A112 Jul 2012
Granted: 16 Dec 2014
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 16/2272
Indexing structures: management thereof
G06F 16/285
Relational databases: clustering or classification
G06F 16/316
Indexing; Data structures therefor; Storage structures: indexing structures
G06F 16/93
Details of database functions independent of the retrieved data types: document management systems

Family

Application12/139,213Parent of this continuation · filed 13 Jun 2008
US 2012/0179668 A1Pre-grant publication · published 12 Jul 2012
US 8,166,041 B2Parent of this continuation
US 2009/0313238 A1Published application
US 8,914,380 B2This patent

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