Constrained searching of an index
First Claim
1. A method for searching an index of stored information, the index including a plurality of index entries, each of the plurality of index entries including a word entry representing a unique indexable portion of the stored information, and one or more location entries representing each occurrence of the unique indexable portion of the stored information, the method comprising the steps of:
- identifying a first word entry of a first index entry as corresponding to a first term of a query;
identifying a second word entry of a second index entry as corresponding to a second term of the query; and
searching the first index entry and the second index entry for respective location entries subject to a plurality of constraints, wherein each of the plurality of constraints must be satisfied, and wherein the order in which the plurality of constraints are satisfied is determined by which of the plurality of constraints is able to advance the search the farthest.
11 Assignments
0 Petitions
Accused Products
Abstract
A computer implemented method performs constrained searching of an index of a database. The information of the database is stored as a plurality of records. A unique location is assigned to each indexable portion of information of the database. Index entries are written to a memory where each index entry includes a word entry representing a unique indexable portion of information, and one or more location entries for each occurrence of the unique indexable portion information. The index entries are sorted according to a collating order of the word entries, and sequentially according to the location entries of each index entry. A query is parsed to generate a first term and a second term related by an AND logical operator, the AND operator requires that a first index entry corresponding to the first term and a second index entry corresponding to the second term both have locations in the same record to satisfy a query. The location entries of the first and second index entries are searched subject to one or more constraints which must be satisfied. The constraints are expressed as C(a)≦C(b)+K, where C(a) means a current location of the first index entry, C(b) means a current location of the second index entry, and K is a predetermined constant.
-
Citations
21 Claims
-
1. A method for searching an index of stored information, the index including a plurality of index entries, each of the plurality of index entries including a word entry representing a unique indexable portion of the stored information, and one or more location entries representing each occurrence of the unique indexable portion of the stored information, the method comprising the steps of:
-
identifying a first word entry of a first index entry as corresponding to a first term of a query; identifying a second word entry of a second index entry as corresponding to a second term of the query; and searching the first index entry and the second index entry for respective location entries subject to a plurality of constraints, wherein each of the plurality of constraints must be satisfied, and wherein the order in which the plurality of constraints are satisfied is determined by which of the plurality of constraints is able to advance the search the farthest. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. An article of manufacture for searching an index of stored information, the index including a plurality of index entries, each of the plurality of index entries including a word entry representing a unique indexable portion of the stored information, and one or more location entries representing each occurrence of the unique indexable portion of the stored information, the article of manufacture comprising:
-
at least one processor readable carrier; and instructions contained on the carrier; wherein the instructions are configured to be readable from the at least one carrier by one or more processors and thereby cause the one or more processors to operate so as to; identify a first word entry of a first index entry as corresponding to a first term of a query; identify a second word entry of a second index entry as corresponding to a second term of the query; and search the first index entry and the second index entry for respective location entries subject to a plurality of constraints, wherein each of the plurality of constraints must be satisfied, and wherein the order in which the plurality of constraints are satisfied is determined by which of the plurality of constraints is able to advance the search the farthest. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A system for searching an index of stored information, the index including a plurality of index entries, each of the plurality of index entries including a word entry representing a unique indexable portion of the stored information, and one or more location entries representing each occurrence of the unique indexable portion of the stored information, the system comprising:
-
at least one storage device for storing the index; and at least one processor connected to the at least one storage device, the at least one processor configured to; identify a first word entry of a first index entry as corresponding to a first term of a query; identify a second word entry of a second index entry as corresponding to a second term of the query; and search the first index entry and the second index entry for respective location entries subject to a plurality of constraints, wherein each of the plurality of constraints must be satisfied, and wherein the order in which the plurality of constraints are satisfied is determined by which of the plurality of constraints is able to advance the search the farthest. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
Specification