7. A method for selecting a set of n-grams for indexing string data in a database management system (DBMS), wherein the DBMS includes a set of candidate n-grams, a set of sample queries, a set of database records, and an input space constraint ‘k’ related to resources allocated to the DBMS, the method comprising: a) determining for each sample query from the set of sample queries, which n-grams in the candidate set are a substring of the sample query, and in response, forming a connection between the sample query and the n-gram; b) determining for each database record from the set of database records, which n-grams do not exist as a substring of the database record, and in response forming a connection between the database record and the n-gram; c) receiving the input space constraint ‘k’ the input space constraint ‘k’ directly related to resources allocated to the DBMS; d) calculating a benefit of each n-gram in the candidate set, wherein the benefit of each n-gram is computed as a number of previously uncovered connections between the queries and the database records that are made through the n-gram, wherein a connection made through an n-gram between a query and a database record comprises a query-record pair; e) identifying the n-gram with the highest computed benefit, and storing the identified 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 (e) ‘k’ times, thereby resulting in the selected n-gram set having ‘k’ n-grams, such that the number of query-record pairs connected through best n-grams is a maximum over all possible sets of best n-gram sets; g) generating an index, based on the selected n-gram set; h) using the generated index by the DBMS to service incoming queries, whereby the generated index created from the selected n-gram set minimizes false hits because the selected n-gram set maximizes reachability among unique query-record pairs and maximizes rejections.
7. A method for selecting a set of n-grams for indexing string data in a database management system (DBMS), wherein the DBMS includes a set of candidate n-grams, a set of sample queries, a set of database records, and an input space constraint ‘k’ related to resources allocated to the DBMS, the method comprising: a) determining for each sample query from the set of sample queries, which n-grams in the candidate set are a substring of the sample query, and in response, forming a connection between the sample query and the n-gram; b) determining for each database record from the set of database records, which n-grams do not exist as a substring of the database record, and in response forming a connection between the database record and the n-gram; c) receiving the input space constraint ‘k’ the input space constraint ‘k’ directly related to resources allocated to the DBMS; d) calculating a benefit of each n-gram in the candidate set, wherein the benefit of each n-gram is computed as a number of previously uncovered connections between the queries and the database records that are made through the n-gram, wherein a connection made through an n-gram between a query and a database record comprises a query-record pair; e) identifying the n-gram with the highest computed benefit, and storing the identified 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 (e) ‘k’ times, thereby resulting in the selected n-gram set having ‘k’ n-grams, such that the number of query-record pairs connected through best n-grams is a maximum over all possible sets of best n-gram sets; g) generating an index, based on the selected n-gram set; h) using the generated index by the DBMS to service incoming queries, whereby the generated index created from the selected n-gram set minimizes false hits because the selected n-gram set maximizes reachability among unique query-record pairs and maximizes rejections. 8. The method of claim 7 further comprising: implementing an approximation algorithm as a utility of the DBMS.