Patent ID: 7487141
Filing Date: 2009-02-03
Classification: G06F,Y10S

Abstract:
1. A method for indexing documents in a collection of documents using skip entries, each document comprising one or more index terms, the method comprising: determining a first value x representative of a first location for inserting a first skip entry in an inverted index, such that x is determined as an integer corresponding to a quantity of documents including at least a majority of the index terms, wherein the first value x representing the first location for inserting the first skip entry is not the first posting of the inverted index, wherein x is an integer in a first range of 256 to 512; determining a second value y, where y does not exceed x, the second value y determined as an integer and representative of a second location for inserting a second skip entry in the inverted index, wherein y does not equal x, such that the first and second skip entries are provided at different intervals, wherein y is an integer in a second range of 128 to 256; generating the inverted index for the collection of documents, the inverted index including an inverted list for each of the index terms, each inverted list including at least one posting and, if the number of postings exceeds x, further including the first skip entry inserted after the Xth posting and one or more second skip entries inserted thereafter at intervals of every yth posting; wherein: the at least one posting includes a document identifier identifying a document in the collection of documents; the first and second skip entries including a document identifier that is included in a boundary posting of a block of postings immediately adjacent to the skip entry in the inverted list, where a block of postings includes postings having document identifiers ranging from a lower to an upper value and where a boundary posting is a posting having a document identifier of either the lower or the upper value.