Patent US6199062B1 successfully refreshed from Google Patents.
US6199062B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Reverse string indexing in a relational database for wildcard searching
Assignee: International Business Machines Corp
•
Filing: 1998-11-19
•
Granted: 2001-03-06
•
Expires: 2018-11-19
Abstract
Abstract A method of hierarchical LDAP wildcard searching in an LDAP directory service having a relational database management system (DBMS) as a backing store. The relational database normally includes a forward index of the character strings in the database. The method begins by generating a reverse index of the character strings in the relational database. Depending on the position of one or more wildcards in the string, the forward index, the reverse index, or both indices, are used to generate the relational database query.
Inventors
- 👤 Debora Jean Byrne
- 👤 John Mark McConaughy
- 👤 Shaw-Ben Shi
- 👤 Chin-Long Shu
- 👤 Trung Minh Tran
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 23:14
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
74 words
A method for wildcard searching a relational database using hierarchical, filter-based queries, comprising the steps of: generating a reverse index of character strings in the relational database; upon receipt of a hierarchical, filter-based query having a search string with a wildcard, using the reverse index to generate a relational database query if the wildcard is at a given position within the search string; and using the relational database query to access the relational database.
Claim 2
Independent Claim
74 words
A method for wildcard searching a relational database using hierarchical, filter-based queries, comprising the steps of: generating a reverse index of character strings in the relational database; upon receipt of a hierarchical, filter-based query having a search string with a wildcard, using the reverse index to generate a relational database query if the wildcard is at a given position within the search string; and using the relational database query to access the relational database.
Claim 3
Dependent Claim
19 words
The method as described in claim 1 wherein the given position is a leading position in the search string.
Claim 4
Dependent Claim
37 words
The method as described in claim 1 wherein the given position is an intermediate position in the search string and a number of characters trailing the wildcard is greater than a number of characters leading the wildcard.
Claim 5
Dependent Claim
35 words
The method as described in claim 1 further including the step of using a forward index to generate a relational database query if the wildcard is not at a given position within the search string.
Claim 6
Dependent Claim
37 words
The method as described in claim 4 wherein the given position is an intermediate position in the search string and a number of characters trailing the wildcard is less than a number of characters leading the wildcard.
Claim 7
Dependent Claim
22 words
The method as described in claim 1 wherein the reverse index is generated by creating a mirror image of a forward index.
Claim 8
Dependent Claim
21 words
The method as described in claim 1 wherein the filter-based query is a Lightweight Directory Access Protocol (LDAP) directory service query.
Claim 9
Independent Claim
94 words
A method for wildcard searching a relational database using hierarchical, filter-based queries, comprising the steps of: generating a forward index of character strings in the relational database; generating a reverse index by mirroring the forward index; upon receipt of a hierarchical, filter-based query having a search string with at least one wildcard, determining whether the forward index, the reverse index, or both indices, should be used to generate a relational database query; as a result of the determination, generating the relational database query; and using the relational database query to access the relational database.
Claim 10
Independent Claim
94 words
A method for wildcard searching a relational database using hierarchical, filter-based queries, comprising the steps of: generating a forward index of character strings in the relational database; generating a reverse index by mirroring the forward index; upon receipt of a hierarchical, filter-based query having a search string with at least one wildcard, determining whether the forward index, the reverse index, or both indices, should be used to generate a relational database query; as a result of the determination, generating the relational database query; and using the relational database query to access the relational database.
Claim 11
Dependent Claim
23 words
The method as described in claim 8 wherein the reverse index is applied to the search string to generate the relational database query.
Claim 12
Dependent Claim
41 words
The method as described in claim 8 wherein the forward index is applied to a first portion of the search string and the reverse index is applied to a second portion of the search string to generate the relational database query.
Claim 13
Dependent Claim
39 words
The method as described in claim 10 wherein the wildcard is located in an intermediate position within the search string and a number of a number of characters leading the wildcard exceeds the number of characters trailing the wildcard.
Claim 14
Dependent Claim
16 words
The method as described in claim 8 wherein the search string includes two or more wildcards.
Claim 15
Independent Claim
103 words
A method for searching a relational database from a Lightweight Directory Access Protocol (LDAP) directory service generating filter-based queries, the relational database having stored therein a forward index of character strings and a reverse index that is a mirror image of the forward index, the method comprising the steps of: upon receipt of an LDAP query having a search string with a wildcard, using the forward index, the reverse index, or both indices, to generate a relational database query depending on a position of at least one wildcard within the search string; and using the relational database query to access the relational database.
Claim 16
Independent Claim
103 words
A method for searching a relational database from a Lightweight Directory Access Protocol (LDAP) directory service generating filter-based queries, the relational database having stored therein a forward index of character strings and a reverse index that is a mirror image of the forward index, the method comprising the steps of: upon receipt of an LDAP query having a search string with a wildcard, using the forward index, the reverse index, or both indices, to generate a relational database query depending on a position of at least one wildcard within the search string; and using the relational database query to access the relational database.
Claim 17
Dependent Claim
70 words
A computer program product in computer-readable media for searching a relational database using hierarchical, filter-based queries, comprising: means for generating a reverse index of character strings in the relational database; and means responsive to receipt of a hierarchical, filter-based query having a search string with a wildcard for using the reverse index to generate a relational database query if the wildcard is at a given position within the search string.
Claim 18
Dependent Claim
70 words
A computer program product in computer-readable media for searching a relational database using hierarchical, filter-based queries, comprising: means for generating a reverse index of character strings in the relational database; and means responsive to receipt of a hierarchical, filter-based query having a search string with a wildcard for using the reverse index to generate a relational database query if the wildcard is at a given position within the search string.
Claim 19
Dependent Claim
21 words
The computer program product as described in claim 14 wherein the given position is a leading position in the search string.
Claim 20
Dependent Claim
39 words
The computer program product as described in claim 14 wherein the given position is an intermediate position in the search string and a number of characters trailing the wildcard is greater than a number of characters leading the wildcard.
Claim 21
Dependent Claim
23 words
The computer program product as described in claim 14 wherein the filter-based query is a Lightweight Directory Access Protocol (LDAP) directory service query.
Claim 22
Dependent Claim
71 words
A computer program product in computer-readable media for searching a relational database using hierarchical, filter-based queries, comprising: means for generating a reverse index by mirroring a forward index of character strings in the relational database; and means responsive to receipt of a hierarchical, filter-based query having a search string with at least one wildcard, for using the forward index, the reverse index, or both indices, to generate a relational database query.
Claim 23
Dependent Claim
71 words
A computer program product in computer-readable media for searching a relational database using hierarchical, filter-based queries, comprising: means for generating a reverse index by mirroring a forward index of character strings in the relational database; and means responsive to receipt of a hierarchical, filter-based query having a search string with at least one wildcard, for using the forward index, the reverse index, or both indices, to generate a relational database query.
Claim 24
Dependent Claim
95 words
A directory service, comprising: a directory organized as a naming hierarchy having a plurality of entries each represented by a unique identifier; a relational database management system having a backing store for storing directory data; means for searching the directory, comprising: means for generating a reverse index by mirroring a forward index of character strings in the relational database; and means responsive to receipt of a hierarchical, filter-based query having a search string with at least one wildcard, for using the forward index, the reverse index, or both indices, to generate a relational database query.
Claim 25
Dependent Claim
95 words
A directory service, comprising: a directory organized as a naming hierarchy having a plurality of entries each represented by a unique identifier; a relational database management system having a backing store for storing directory data; means for searching the directory, comprising: means for generating a reverse index by mirroring a forward index of character strings in the relational database; and means responsive to receipt of a hierarchical, filter-based query having a search string with at least one wildcard, for using the forward index, the reverse index, or both indices, to generate a relational database query.
Claim 26
Dependent Claim
20 words
The directory service as described in claim 19 wherein the directory is compliant with the Lightweight Directory Access Protocol (LDAP).
Claim 27
Dependent Claim
101 words
In a directory service having a directory organized as a naming hierarchy, the hierarchy including a plurality of entries each represented by a unique identifier, the improvement comprising: a relational database management system having a backing store for storing directory data; means for searching the directory, comprising: means for generating a reverse index by mirroring a forward index of character strings in the relational database; and means responsive to receipt of a hierarchical, filter-based query having a search string with at least one wildcard, for using the forward index, the reverse index, or both indices, to generate a relational database query.
Claim 28
Dependent Claim
101 words
In a directory service having a directory organized as a naming hierarchy, the hierarchy including a plurality of entries each represented by a unique identifier, the improvement comprising: a relational database management system having a backing store for storing directory data; means for searching the directory, comprising: means for generating a reverse index by mirroring a forward index of character strings in the relational database; and means responsive to receipt of a hierarchical, filter-based query having a search string with at least one wildcard, for using the forward index, the reverse index, or both indices, to generate a relational database query.
Claim 29
Dependent Claim
21 words
In the directory service as described in claim 21 wherein the directory is compliant with the Lightweight Directory Access Protocol (LDAP).
Claim 30
Independent Claim
69 words
A method for wildcard searching a database using a database query, comprising the steps of: upon receipt of a query having a search string with a wildcard, processing the search string to force the wildcard into an optimal search position as a function of an algorithm used to search the database; generating a database query from the processed search string; and using the database query to access the database.
Claim 31
Independent Claim
69 words
A method for wildcard searching a database using a database query, comprising the steps of: upon receipt of a query having a search string with a wildcard, processing the search string to force the wildcard into an optimal search position as a function of an algorithm used to search the database; generating a database query from the processed search string; and using the database query to access the database.
References Cited (Backward Citations)
JPS6475242A
Cited
US4914569A
Cited
US5319779A
Cited
JPH04138548A
Cited
US5630114A
Cited
US5586288A
Cited
US5758356A
Cited
US5694593A
Cited
US5701469A
Cited
US5710915A
Cited
JPH09190448A
Cited
WO1998001950A1
Cited
US5956705A
Cited
US6016499A
Cited
US6085188A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-03-05 | 2004-09-04 | 2005-03-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-03-05 | 2008-09-04 | 2009-03-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-03-05 | 2012-09-04 | 2013-03-06 | $7700.00 | Window Closed / Lapsed |