Patent ID: 7949657
Filing Date: 2011-05-24
Classification: G06F

Abstract:
1. A machine-implemented method for creating at least one data structure for determining whether a query for at least one document of a plurality of documents including a group of words is likely to produce a non-zero search result, the machine-implemented method comprising: obtaining a list of distinct words from the plurality of documents; assigning a rank to each of the distinct words based on a frequency of use within the plurality of documents; extracting a list of word groups from the list of distinct words, each of the word groups being present in any one of the plurality of documents; distributing the word groups into a plurality of word grouping collections based on respective ranks assigned to each word of the word groups; determining a density level percentage of each of the plurality of word grouping collections by calculating a percentage of possible word groups of the respective ones of the plurality of word grouping collections that are present in any one document of the plurality of documents according to:  where NWG is a number of word groups of a fixed word length included in a respective one of the plurality of word grouping collections and present in any one document of the plurality of documents, and AWG is a number of all possible word groups of the fixed length distributed to the respective one of the plurality of word grouping collections; assigning a density level category to each of the word grouping collections based on the corresponding density level percentage; storing, with respect to at least some of the word grouping collections, occurrence information into a respective one of the at least one data structure, the occurrence information indicating a likelihood that ones of the word groupings are included in any one of the plurality of documents, a type of the respective one of the at least one data structure being based, at least in part, on the density level category assigned to the respective word grouping collection, after performing the storing, if specific occurrence information corresponding to a specific word grouping indicates that the specific word grouping is not included in any document of the plurality of documents, then the specific word grouping is not included, with certainty, in any document of the plurality of documents, such that a search of at least one index, with respect to the plurality of documents, in an attempt to find ones of the plurality of documents having all words of the specific word grouping is avoided after referencing the specific occurrence information, wherein the machine-implemented method is performed by a processing device.