Patent US6401088B1 successfully refreshed from Google Patents.
US6401088B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for substring selectivity estimation
Assignee: AT&T Inc
•
Filing: 1999-12-30
•
Granted: 2002-06-04
•
Expires: 2019-12-30
Abstract
Abstract A method for estimating string-occurrence probability in a database comprises receiving a first probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to the string; obtaining an overall probability of occurrence; receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; obtaining a normalization factor; and dividing the overall probability of occurrence by the normalization factor to obtain the estimate.
Inventors
- 👤 Hosagrahar Visvesvaraya Jagadish
- 👤 Raymond Ng
- 👤 Divesh Srivastava
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 12:46
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/18; G06F16/00; G06F16/20; G06F16/24; G06F16/242; G06F16/2433; G06F16/2448; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; G06F16/24545; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
94 words
A method for determining an estimate for string-occurrence probability in a database for a string, the method comprising: (a) receiving a first probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to the string; (b) obtaining an overall probability of occurrence; (c) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (d) obtaining a normalization factor; and (e) dividing the overall probability of occurrence by the normalization factor to obtain the estimate.
Claim 2
Independent Claim
94 words
A method for determining an estimate for string-occurrence probability in a database for a string, the method comprising: (a) receiving a first probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to the string; (b) obtaining an overall probability of occurrence; (c) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (d) obtaining a normalization factor; and (e) dividing the overall probability of occurrence by the normalization factor to obtain the estimate.
Claim 3
Dependent Claim
19 words
The method of claim 1 , further comprising the step of (f) using the obtained estimate for query-cost determination.
Claim 4
Dependent Claim
38 words
The method of claim 1 , wherein the overall probability of occurrence is obtained by multiplying together every probability of occurrence received in (a), and the normalization factor is obtained by multiplying together the probabilities received in (c).
Claim 5
Dependent Claim
39 words
The method of claim 3 , wherein the database contains a number of strings, and the first probability of occurrence is defined as the number of strings in the database that contain the string, divided by a root count.
Claim 6
Dependent Claim
14 words
The method of claim 3 , wherein the database is a pruned suffix tree.
Claim 7
Dependent Claim
51 words
The method of claim 3 , further comprising the steps of: (f) obtaining an upper limit on the string occurrence probability in a database for the string; and (g) returning, as a new result, the smaller of the upper limit obtained in step (f) and the estimate obtained in step (e).
Claim 8
Dependent Claim
19 words
The method of claim 6 , further comprising the step of: (h) using the new result for query-cost determination.
Claim 9
Dependent Claim
59 words
The method of claim 6 , wherein said obtaining an upper limit on the estimate obtained in step (e) includes: (i) determining a maximal number of occurrences of the string based on the string's constraints; and (ii) dividing the maximal number of occurrences by a root count associated with the database, to produce an upper limit on the estimate.
Claim 10
Dependent Claim
19 words
The method of claim 8 , wherein said determining a maximal number of occurrences includes applying a ConProj operator.
Claim 11
Independent Claim
90 words
A method for determining an estimate for string-occurrence probability in a database for a string, the method comprising: (a) multiplying together every probability of occurrence of each maximal substring from a plurality of maximal substrings to generate a product, each substring in the plurality of maximal substrings belonging to the string; (b) multiplying together every probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings to obtain a normalization factor; and (c) dividing the product by the normalization factor to obtain the estimate.
Claim 12
Independent Claim
90 words
A method for determining an estimate for string-occurrence probability in a database for a string, the method comprising: (a) multiplying together every probability of occurrence of each maximal substring from a plurality of maximal substrings to generate a product, each substring in the plurality of maximal substrings belonging to the string; (b) multiplying together every probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings to obtain a normalization factor; and (c) dividing the product by the normalization factor to obtain the estimate.
Claim 13
Dependent Claim
43 words
The method of claim 10 , wherein the database contains a number of strings and a root count, and wherein the probability of occurrence is defined as the number of strings in the database that contain the string, divided by the root count.
Claim 14
Dependent Claim
14 words
The method of claim 11 , wherein the database is a pruned suffix tree.
Claim 15
Dependent Claim
73 words
The method of claim 11 , further comprising the steps of: (d) determining a maximal number of occurrences of the string based on the string's constraints; (e) dividing the maximal number of occurrences by a root count associated with the database to produce an upper limit on the second estimate; and (f) returning, as a new result, the smaller of the upper limit obtained in (e) and the second estimate obtained in (c).
Claim 16
Dependent Claim
19 words
The method of claim 13 , wherein said determining a maximal number of occurrences includes applying a ConProj operator.
Claim 17
Independent Claim
132 words
A method for estimating the cost of a query to a database that contains a plurality of strings and substrings, the method comprising: (a) receiving a probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to the string; (b) obtaining an overall probability of occurrence by multiplying together every probability of occurrence received in step (a); (c) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (d) obtaining a normalization factor by multiplying together the probabilities received in (c); (e) obtaining a string-occurrence probability for the string in the database by dividing the overall probability of occurrence by the normalization factor; and (f) using the string-occurrence probability for query-cost determination.
Claim 18
Independent Claim
132 words
A method for estimating the cost of a query to a database that contains a plurality of strings and substrings, the method comprising: (a) receiving a probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to the string; (b) obtaining an overall probability of occurrence by multiplying together every probability of occurrence received in step (a); (c) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (d) obtaining a normalization factor by multiplying together the probabilities received in (c); (e) obtaining a string-occurrence probability for the string in the database by dividing the overall probability of occurrence by the normalization factor; and (f) using the string-occurrence probability for query-cost determination.
Claim 19
Independent Claim
159 words
A method for determining the cost of a query to a database that contains a plurality of strings and substrings, the method comprising: (a) receiving a probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to a string; (b) obtaining an overall probability of occurrence by multiplying together every probability of occurrence received in step (a); (c) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (d) obtaining a normalization factor by multiplying together the probabilities received in (c); (e) obtaining a string-occurrence probability for the string in the database by dividing the overall probability of occurrence by the normalization factor; (f) obtaining an upper limit on the string-occurrence probability for the string; and (g) performing query-cost determination with the smaller of the upper limit obtained in step (f) and the string-occurrence probability obtained in step (e).
Claim 20
Independent Claim
159 words
A method for determining the cost of a query to a database that contains a plurality of strings and substrings, the method comprising: (a) receiving a probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to a string; (b) obtaining an overall probability of occurrence by multiplying together every probability of occurrence received in step (a); (c) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (d) obtaining a normalization factor by multiplying together the probabilities received in (c); (e) obtaining a string-occurrence probability for the string in the database by dividing the overall probability of occurrence by the normalization factor; (f) obtaining an upper limit on the string-occurrence probability for the string; and (g) performing query-cost determination with the smaller of the upper limit obtained in step (f) and the string-occurrence probability obtained in step (e).
Claim 21
Dependent Claim
57 words
The method of claim 16 , wherein said obtaining an upper limit on the string-occurrence probability includes: (i) determining a maximal number of occurrences of the string based on the string's constraints; and (ii) dividing the maximal number of occurrences by a root count associated with the database, to produce an upper limit on the string-occurrence probability.
Claim 22
Independent Claim
119 words
An apparatus for estimating string-occurrence probability in a database for a string, the apparatus comprising: (a) a processor; (b) a port coupled to said processor; and (c) a memory coupled to said processor, said memory storing instructions adapted to be executed on said processor, the instructions including: (i) multiplying together every probability of occurrence of each maximal substring from a plurality of maximal substrings to generate a product, each substring in the plurality of maximal substrings belonging to the string; (ii) multiplying together every probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings to obtain a normalization factor; and (iii) dividing the product by the normalization factor to obtain the estimate.
Claim 23
Independent Claim
119 words
An apparatus for estimating string-occurrence probability in a database for a string, the apparatus comprising: (a) a processor; (b) a port coupled to said processor; and (c) a memory coupled to said processor, said memory storing instructions adapted to be executed on said processor, the instructions including: (i) multiplying together every probability of occurrence of each maximal substring from a plurality of maximal substrings to generate a product, each substring in the plurality of maximal substrings belonging to the string; (ii) multiplying together every probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings to obtain a normalization factor; and (iii) dividing the product by the normalization factor to obtain the estimate.
Claim 24
Dependent Claim
43 words
The apparatus of claim 18 , wherein the database contains a number of strings and a root count, and wherein the probability of occurrence is defined as the number of strings in the database that contain the string, divided by the root count.
Claim 25
Dependent Claim
14 words
The apparatus of claim 18 , wherein the database is a pruned suffix tree.
Claim 26
Dependent Claim
84 words
The apparatus of claim 18 , said memory storing further instructions adapted to be executed on said processor, said further instructions comprising: (iv) determining a maximal number of occurrences of the string based on the string's constraints; (v) dividing the maximal number of occurrences by a root count associated with the database to produce an upper limit on the second estimate; and (vi) returning, as a new result, the smaller of the upper limit obtained in (e) and the second estimate obtained in (iii).
Claim 27
Dependent Claim
19 words
The apparatus of claim 21 , wherein said determining a maximal number of occurrences includes applying a ConProj operator.
Claim 28
Independent Claim
156 words
An apparatus for estimating string-occurrence probability in a database for a string, the apparatus comprising: (a) a processor; (b) a port coupled to said processor; and (c) a memory coupled to said processor, said memory storing instructions adapted to be executed on said processor, the instructions including: (i) receiving a probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to the string; (ii) obtaining an overall probability of occurrence by multiplying together every probability of occurrence received in step (i); (iii) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (iv) obtaining a normalization factor by multiplying together the probabilities received in (iii); (v) obtaining a string-occurrence probability for the string in the database by dividing the overall probability of occurrence by the normalization factor; and (vi) using the string-occurrence probability for query-cost determination.
Claim 29
Independent Claim
156 words
An apparatus for estimating string-occurrence probability in a database for a string, the apparatus comprising: (a) a processor; (b) a port coupled to said processor; and (c) a memory coupled to said processor, said memory storing instructions adapted to be executed on said processor, the instructions including: (i) receiving a probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to the string; (ii) obtaining an overall probability of occurrence by multiplying together every probability of occurrence received in step (i); (iii) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (iv) obtaining a normalization factor by multiplying together the probabilities received in (iii); (v) obtaining a string-occurrence probability for the string in the database by dividing the overall probability of occurrence by the normalization factor; and (vi) using the string-occurrence probability for query-cost determination.
Claim 30
Independent Claim
191 words
An apparatus for determining the cost of a query to a database that contains a plurality of strings and substrings, the apparatus comprising: (a) a processor; (b) a port coupled to said processor; and (c) a memory coupled to said processor, said memory storing instructions adapted to be executed on said processor, the instructions including: (i) receiving a probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to a string; (ii) obtaining an overall probability of occurrence by multiplying together every probability of occurrence received in step (i); (iii) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (iv) obtaining a normalization factor by multiplying together the probabilities received in (iii); (v) obtaining a string-occurrence probability for the string in the database by dividing the overall probability of occurrence by the normalization factor; (vi) obtaining an upper limit on the string-occurrence probability for the string; and (vii) performing query-cost determination with the smaller of the upper limit obtained in step (vi) and the string-occurrence probability obtained in step (v).
Claim 31
Independent Claim
191 words
An apparatus for determining the cost of a query to a database that contains a plurality of strings and substrings, the apparatus comprising: (a) a processor; (b) a port coupled to said processor; and (c) a memory coupled to said processor, said memory storing instructions adapted to be executed on said processor, the instructions including: (i) receiving a probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to a string; (ii) obtaining an overall probability of occurrence by multiplying together every probability of occurrence received in step (i); (iii) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (iv) obtaining a normalization factor by multiplying together the probabilities received in (iii); (v) obtaining a string-occurrence probability for the string in the database by dividing the overall probability of occurrence by the normalization factor; (vi) obtaining an upper limit on the string-occurrence probability for the string; and (vii) performing query-cost determination with the smaller of the upper limit obtained in step (vi) and the string-occurrence probability obtained in step (v).
Claim 32
Dependent Claim
57 words
The apparatus of claim 24 , wherein said obtaining an upper limit on the string-occurrence probability includes: (i) determining a maximal number of occurrences of the string based on the string's constraints; and (ii) dividing the maximal number of occurrences by a root count associated with the database, to produce an upper limit on the string-occurrence probability.
Claim 33
Independent Claim
105 words
A medium for determining an estimate for string-occurrence probability in a database for a string, the medium containing instructions adapted to be executed by a processor, the instructions comprising: (a) receiving a first probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to the string; (b) obtaining an overall probability of occurrence; (c) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (d) obtaining a normalization factor; and (e) dividing the overall probability of occurrence by the normalization factor to obtain the estimate.
Claim 34
Independent Claim
105 words
A medium for determining an estimate for string-occurrence probability in a database for a string, the medium containing instructions adapted to be executed by a processor, the instructions comprising: (a) receiving a first probability of occurrence for each maximal substring from a plurality of substrings, each maximal substring in the plurality of substrings belonging to the string; (b) obtaining an overall probability of occurrence; (c) receiving a probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings; (d) obtaining a normalization factor; and (e) dividing the overall probability of occurrence by the normalization factor to obtain the estimate.
Claim 35
Dependent Claim
30 words
The medium of claim 26 , the medium containing further instructions adapted to be executed by a processor, the further instructions comprising: (f) using the obtained estimate for query-cost determination.
Claim 36
Dependent Claim
38 words
The medium of claim 26 , wherein the overall probability of occurrence is obtained by multiplying together every probability of occurrence received in (a), and the normalization factor is obtained by multiplying together the probabilities received in (c).
Claim 37
Dependent Claim
39 words
The medium of claim 28 , wherein the database contains a number of strings, and the first probability of occurrence is defined as the number of strings in the database that contain the string, divided by a root count.
Claim 38
Dependent Claim
51 words
The medium of claim 28 , further comprising the steps of: (f) obtaining an upper limit on the string occurrence probability in a database for the string; and (g) returning, as a new result, the smaller of the upper limit obtained in step (f) and the estimate obtained in step (e).
Claim 39
Dependent Claim
19 words
The medium of claim 30 , further comprising the step of: (h) using the new result for query-cost determination.
Claim 40
Dependent Claim
59 words
The medium of claim 30 , wherein said obtaining an upper limit on the estimate obtained in step (e) includes: (i) determining a maximal number of occurrences of the string based on the string's constraints; and (ii) dividing the maximal number of occurrences by a root count associated with the database, to produce an upper limit on the estimate.
Claim 41
Independent Claim
101 words
A medium for determining an estimate for string-occurrence probability in a database for a string, the medium storing instructions adapted to be executed by a processor, the instructions comprising: (a) multiplying together every probability of occurrence of each maximal substring from a plurality of maximal substrings to generate a product, each substring in the plurality of maximal substrings belonging to the string; (b) multiplying together every probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings to obtain a normalization factor; and (c) dividing the product by the normalization factor to obtain the estimate.
Claim 42
Independent Claim
101 words
A medium for determining an estimate for string-occurrence probability in a database for a string, the medium storing instructions adapted to be executed by a processor, the instructions comprising: (a) multiplying together every probability of occurrence of each maximal substring from a plurality of maximal substrings to generate a product, each substring in the plurality of maximal substrings belonging to the string; (b) multiplying together every probability of occurrence for a maximal overlap of each maximal substring in the plurality of maximal substrings to obtain a normalization factor; and (c) dividing the product by the normalization factor to obtain the estimate.
Claim 43
Dependent Claim
43 words
The medium of claim 33 , wherein the database contains a number of strings and a root count, and wherein the probability of occurrence is defined as the number of strings in the database that contain the string, divided by the root count.
Claim 44
Dependent Claim
73 words
The medium of claim 34 , further comprising the steps of: (d) determining a maximal number of occurrences of the string based on the string's constraints; (e) dividing the maximal number of occurrences by a root count associated with the database to produce an upper limit on the second estimate; and (f) returning, as a new result, the smaller of the upper limit obtained in (e) and the second estimate obtained in (c).
References Cited (Backward Citations)
US4833712A
Cited
US5150430A
Cited
US5392363A
Cited
US5525982A
Cited
US5819265A
Cited
US5832480A
Cited
US6308149B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-06-03 | 2005-12-03 | 2006-06-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-06-03 | 2009-12-03 | 2010-06-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-06-03 | 2013-12-03 | 2014-06-04 | $7700.00 | Window Closed / Lapsed |