Selection of a set of optimal n-grams for indexing string data in a DBMS system under space constraints introduced by the system

• US 20060101000A1
• Filed: 11/05/2004
• Published: 05/11/2006
• Est. Priority Date: 11/05/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mehrotra, Sharad, Hacigumus, Vahit Hakan, Iyer, Balakrishna Raghavendra
• Granted Patent: US 7,478,081 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The present invention provides a computer-readable medium and system for selecting a set of n-grams for indexing string data in a DBMS system. Aspects of the invention include providing a set of candidate in grams, each n-gram comprising a sequence of characters; identifying sample queries having character strings containing the candidate n-grams; and based on the set of candidate n-grams, the sample queries, database records, and an n-gram space constraint, automatically selecting, given the space constraint, a minimal set of an n-grams from the set of candidate n-grams that minimizes the number of false hits for the set of sample queries had the sample queries been executed against the database records.

Claims

1. A method for selecting a set of n-grams for indexing string data in a DBMS system, comprising:

providing a set of candidate n-grams, each n-gram comprising a sequence of characters;

identifying sample queries having character strings containing the candidate n-grams; and

based on the set of candidate n-grams, the sample queries, database records, and an n-gram space constraints, automatically selecting, given the space constraint, a minimal set of n-grams from the set of candidate n-grams that minimizes the number of false hits for the set of sample queries had the sample queries been executed against the database records.

2. The method of claim 1 further including:

generating an index based on the minimal set of selected n-grams that indexes string data contained in the database records.

3. The method of claim 2 further including:

using the index by the DBMS to service incoming queries submitted by users to speed data access.

4. The method of claim 1 wherein the n-gram selection is a problem that is NP-hard, the method further including:

formulating the n-gram selection as a graph model, and solving the problem using an optimization approximation algorithm.

5. The method of claim 4 further including:

providing the approximation algorithm with a provable ratio bound of an optimal solution to the n-gram solution problem.

6. The method of claim 4 further including:

implementing the approximation algorithm as a utility of the DBMS.

7. The method of claim 1 wherein the DBMS is a SQL DBMS, the identifying step further including:

identifying SQL “

LIKE”

queries containing the candidate n-grams.

8. A method for selecting a set of n-grams for indexing string data in a DBMS system, wherein, the DBMS system includes a set of candidate n-grams, a set of sample queries, and a set of database records, the method comprising:

a) determine for each sample query, which n-grams in the candidate set are substring of the query, and in response, forming a connection between the sample query and the n-gram;

b) determine for each record, which n-grams do not exist as a substring of the record, and in response forming a connection between the record and the n-gram;

c) receiving an input space constraint, k;

d) calculating the benefit of each n-gram in the candidate set, where the benefit of each n-gram is computed as a number of previously uncovered connections between the queries and the records that are made through the n-gram, wherein a connection made through an n-gram between a query and a record comprises a query-record pair;

e) identifying the n-gram with the highest computed benefit, removing the n-gram from the candidate n-gram set, and storing the n-gram in a selected n-gram set;

f) recomputing the benefits of remaining n-grams in the candidate set by performing steps d) and f) k times, thereby resulting in the selected n-gram set having k n-grams, such that the number of record-query pairs connected through the best n-grams is maximum over all possible sets of best n-gram sets.

9. The method of claim 8 further comprising:

implementing the approximation algorithm as a utility of the DBMS.

10. The method of claim 9 further including:

generating an index based on the selected gram set that indexes string data contained in the database records.

11. The method of claim 10 further including:

using the index by the DBMS to service incoming queries submitted by users to speed data access, whereby the index created from the selected gram set minimizes false hits because the selected gram set maximizes reachability among unique record-query pairs and maximizes rejections.

12. The method of claim 9 wherein the approximation algorithm provides a near optimal solution to an NP hard n-gram selection problem, the method further comprising:

providing the approximation algorithm with a definable ratio bound of the optimal solution.

13. The method of claim 12 wherein the ratio bound is:

$\frac{<br><br>C^{\mathrm{\prime <br><br>}}<br><br>}{<br><br>C^{*}<br><br>}><br><br>1-\frac{1}{\mathrm{e<br><br>}}$

where |C*| is a number of points covered by an optimum solution C* and |C′

| is a number of points covered by the near optimal solution produced by the approximation algorithm.

14. The method of claim 9 wherein the DBMS is a relational database system.

15. An optimal n-gram indexing relational database management system (DBMS) capable of being executed in a computer system, comprising:

a set of sample queries;

a plurality of database records;

means for selecting an optimal set of n-grams from a set of candidate n-grams, the selecting means functional for,

receiving as input a space constraint, k, for limiting the optimal set of n-grams; and

automatically selecting a set of n-grams of size k from the set of candidate n-grams that minimizes the number of false hits for the set of sample queries had the sample queries been executed against the database records.

16. The system of claim 15 wherein the n-gram selection problem is NP-hard, the selection means includeing an optimization approximation algorithm that models the n-gram selection problem as a graph and provides a near optimal solution.

17. The system of claim 16 wherein the approximation algorithm outputs the selected set of n-grams of size k, wherein the selected set of n-grams is a subset of the set of candidate n-grams, such that a number of record-query pairs connected through the n-grams in the selected set is maximum over all possible sets of n-grams in the selected set.

18. The system of claim 16 wherein the approximation algorithm has a provable ratio bound of the optimal solution to the n-gram solution problem.

19. The system of claim 18 wherein the ratio bound is:

$\frac{<br><br>C^{\mathrm{\prime <br><br>}}<br><br>}{<br><br>C^{*}<br><br>}><br><br>1-\frac{1}{\mathrm{e<br><br>}}$

where |C*| is a number of points covered by an optimum solution C* and |C′

| is a number of points covered by the near optimal solution produced by the approximation algorithm.

20. The system of claim 16 wherein the approximation algorithm is implemented as a utility of the DBMS.

21. The system of claim 16 wherein the selection means further includes an index generator for generating an index based on the minimal set of selected that indexes string data contained in the database records.

22. The system of claim 21 wherein the index is used by the DBMS to service incoming queries submitted by users to speed data access.

23. The system of claim 15 wherein the DBMS is a SQL DBMS, the identifying step further including:

identifying SQL “

LIKE”

queries containing the candidate n-grams.

24. A computer-readable medium containing program instructions for selecting a set of n-grams for indexing string data in a DBMS system, the program instructions for:

providing a set of candidate n-grams, each n-gram comprising a sequence of characters;

identifying sample queries having character strings containing the candidate n-grams; and

based on the set of candidate n-grams, the sample queries, database records, and an n-gram space constraints, automatically selecting, given the space constraint, a minimal set of n-grams from the set of candidate n-grams that minimizes the number of false hits for the set of sample queries had the sample queries been executed against the database records.

25. The computer-readable medium of claim 24 further including:

generating an index based on the minimal set of selected n-grams that indexes string data contained in the database records.

26. The computer-readable medium of claim 24 further including:

using the index by the DBMS to service incoming queries submitted by users to speed data access.

27. The computer-readable medium of claim 24 wherein the n-gram selection is a problem that is NP-hard, the computer-readable medium further including:

formulating the n-gram selection as a graph model, and solving the problem using an optimization approximation algorithm.

28. The computer-readable medium of claim 24 further including:

providing the approximation algorithm with a provable ratio bound of an optimal solution to the n-gram solution problem.

29. The computer-readable medium of claim 24 further including:

implementing the approximation algorithm as a utility of the DBMS.

30. The computer-readable medium of claim 24 wherein the DBMS is a SQL DBMS, the identifying step further including:

identifying SQL “

LIKE”

queries containing the candidate n-grams.