US6105019A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Constrained searching of an index
Assignee: Eureka Database Solutions LLC
•
Filing: 1999-07-26
•
Granted: 2000-08-15
•
Expires: 2019-07-26
Abstract
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.
Inventors
- 👤 Michael Burrows
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 12:41
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/31; G06F16/316; G06F16/328; G06F16/319; G06F16/33; G06F16/3331; G06F16/334; G06F16/3341; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99936; Y10S707/99937; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
159 words
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.
Claim 2
Independent Claim
159 words
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.
Claim 3
Dependent Claim
46 words
The method as defined in claim 1, wherein a first of the plurality of constraints has been determined to advance the search the farthest, further comprising the step of: satisfying the first of the plurality of constraints before satisfying the others of the plurality of constraints.
Claim 4
Dependent Claim
83 words
The method as defined in claim 2, wherein the first index entry and the second index entry each have a plurality of location entries, wherein a particular one of the plurality of location entries in either the first index entry or the second index entry is a current location entry, and wherein the first of the plurality of constraints advances the search the farthest by advancing the current location entry the farthest in either the first index entry or the second index entry.
Claim 5
Dependent Claim
68 words
The method as defined in claim 3, wherein the plurality of constraints are invoked by at least one index stream reader object, wherein each index stream reader object maintains an estimated overshoot value, and wherein the estimated overshoot value is an estimate of how fast the corresponding index stream reader object is advancing through the location entries of either the first index entry or the second index entry.
Claim 6
Dependent Claim
72 words
The method as defined in claim 4, wherein the first of the plurality of constraints advances the current location entry the farthest in either the first index entry or the second index entry when the sum of a target value of the first of the plurality of constraints and the estimated overshoot value of the index stream reader object that invoked the first of the plurality of constraints is at a maximum.
Claim 7
Dependent Claim
70 words
The method as defined in claim 5, wherein each constraint is expressed as C|P(a)≦C|P(b)±K, wherein: | stands for logical OR; C(a) is a current location entry of the first index entry; P(a) is a previous location entry of the first index entry; C(b) is a current location entry of the second index entry; P(b) is a previous location entry of the second index entry; and K is a predetermined constant.
Claim 8
Dependent Claim
26 words
The method as defined in claim 6, wherein the target value of the first of the plurality of constraints is defined as the value of C|P(a)-K.
Claim 9
Dependent Claim
204 words
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.
Claim 10
Dependent Claim
204 words
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.
Claim 11
Dependent Claim
59 words
The article of manufacture as defined in claim 8, wherein a first of the plurality of constraints has been determined to advance the search the farthest, and wherein the instructions further cause the one or more processors to operate so as to: satisfy the first of the plurality of constraints before satisfying the others of the plurality of constraints.
Claim 12
Dependent Claim
85 words
The article of manufacture as defined in claim 9, wherein the first index entry and the second index entry each have a plurality of location entries, wherein a particular one of the plurality of location entries in either the first index entry or the second index entry is a current location entry, and wherein the first of the plurality of constraints advances the search the farthest by advancing the current location entry the farthest in either the first index entry or the second index entry.
Claim 13
Dependent Claim
70 words
The article of manufacture as defined in claim 10, wherein the plurality of constraints are invoked by at least one index stream reader object, wherein each index stream reader object maintains an estimated overshoot value, and wherein the estimated overshoot value is an estimate of how fast the corresponding index stream reader object is advancing through the location entries of either the first index entry or the second index entry.
Claim 14
Dependent Claim
74 words
The article of manufacture as defined in claim 11, wherein the first of the plurality of constraints advances the current location entry the farthest in either the first index entry or the second index entry when the sum of a target value of the first of the plurality of constraints and the estimated overshoot value of the index stream reader object that invoked the first of the plurality of constraints is at a maximum.
Claim 15
Dependent Claim
72 words
The article of manufacture as defined in claim 12, wherein each constraint is expressed as C|P(a)≦C|P(b)±K, wherein: | stands for logical OR; C(a) is a current location entry of the first index entry; P(a) is a previous location entry of the first index entry; C(b) is a current location entry of the second index entry; P(b) is a previous location entry of the second index entry; and K is a predetermined constant.
Claim 16
Dependent Claim
28 words
The article of manufacture as defined in claim 13, wherein the target value of the first of the plurality of constraints is defined as the value of C|P(a)-K.
Claim 17
Independent Claim
185 words
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.
Claim 18
Independent Claim
185 words
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.
Claim 19
Dependent Claim
49 words
The system as defined in claim 15, wherein a first of the plurality of constraints has been determined to advance the search the farthest, the at least one processor further configured to: satisfy the first of the plurality of constraints before satisfying the others of the plurality of constraints.
Claim 20
Dependent Claim
83 words
The system as defined in claim 16, wherein the first index entry and the second index entry each have a plurality of location entries, wherein a particular one of the plurality of location entries in either the first index entry or the second index entry is a current location entry, and wherein the first of the plurality of constraints advances the search the farthest by advancing the current location entry the farthest in either the first index entry or the second index entry.
Claim 21
Dependent Claim
68 words
The system as defined in claim 17, wherein the plurality of constraints are invoked by at least one index stream reader object, wherein each index stream reader object maintains an estimated overshoot value, and wherein the estimated overshoot value is an estimate of how fast the corresponding index stream reader object is advancing through the location entries of either the first index entry or the second index entry.
Claim 22
Dependent Claim
72 words
The system as defined in claim 18, wherein the first of the plurality of constraints advances the current location entry the farthest in either the first index entry or the second index entry when the sum of a target value of the first of the plurality of constraints and the estimated overshoot value of the index stream reader object that invoked the first of the plurality of constraints is at a maximum.
Claim 23
Dependent Claim
71 words
The system as defined in claim 19, wherein each constraint is expressed as C|P(a)≦C|P(b)±K, wherein: | stands for logical OR; (a C(a) is a current location entry of the first index entry; P(a) is a previous location entry of the first index entry; C(b) is a current location entry of the second index entry; P(b) is a previous location entry of the second index entry; and K is a predetermined constant.
Claim 24
Dependent Claim
26 words
The system as defined in claim 20, wherein the target value of the first of the plurality of constraints is defined as the value of C|P(a)-K.
References Cited (Backward Citations)
US4554631A
Cited
US4719642A
Cited
US5235578A
Cited
US5594899A
Cited
US5274805A
Cited
US5652882A
Cited
US5440730A
Cited
US5440744A
Cited
US5280610A
Cited
US5414838A
Cited
US5652880A
Cited
US5264848A
Cited
US5270712A
Cited
US5581758A
Cited
US5467134A
Cited
US5551027A
Cited
US5550965A
Cited
US5664172A
Cited
US5485611A
Cited
US5893087A
Cited
US5640558A
Cited
US5678041A
Cited
US5649186A
Cited
US5668988A
Cited
US5640553A
Cited
US5745890A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-08-15 | 2004-02-14 | 2004-08-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-08-15 | 2008-02-14 | 2008-08-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-08-15 | 2012-02-14 | 2012-08-15 | $7700.00 | Window Closed / Lapsed |