DOMAIN BASED KEYWORD SEARCH

• US 20140250119A1
• Filed: 05/09/2014
• Published: 09/04/2014
• Est. Priority Date: 02/20/2004
• Status: Active Grant

• Current Assignee: Informatica LLC (Informatica, Inc. (California))
• Original Assignee: Informatica Corporation
• Inventors: Bhattiprolu, Pradeep, Grondin, Richard
• Granted Patent: US 9,477,729 B2
• Time in Patent Office: Days
• US Class Current: 707/728
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/256 in federated or virtual databases
• 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
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A database keyword search technique that relies on a domain based storage infrastructure is disclosed. In operation, a keyword search string is processed to generate a set of search string permutations. Each string permutation specifies a different ordering of one or more portions of the search string. A domain based search process is then executed asynchronously for each string permutation. Each execution generates a search result set that identifies rows in the database that include data relevant to the string permutation. The results in each result set are scored and ranked based in part on the similarity between the string permutation and the search string provided by the user. The rankings determine which of the results are to be presented to the user.

Claims

1. A computer-implemented method of performing a keyword search on a database, comprising:

receiving a request including a search string for searching the database, wherein data in the database is represented by one or more tokenized data segments, each tokenized data segment being associated with a different set of columns included in the database and specifying all unique values in the set of columns;

parsing the search string to identify a plurality of keywords included in the search string;

generating a plurality of string permutations based on the received search string, each string permutation being database agnostic and including at least a subset of the plurality of keywords included in the received search string;

for each string permutation;

launching an asynchronous thread for executing a search on the one or more compressed tokenized data segments based on the string permutation;

receiving a plurality of search results when the thread completes execution of the search, each search result identifying a row in the database that includes data relevant to the string permutation,

computing a result relevance score associated with each search result as a measure of relevance between the search result and the received search string, and

collecting the plurality of search results in an ordered queue, the ordering of the search results based on the result relevance score associated with each search result; and

retrieving data from rows in the database identified by a subset of the search results collected in the ordered queue for display in response to the request.

2. The method of claim 1, further comprising, for each string permutation, computing a string similarity score for the string permutation based on the similarity between the string permutation and the search string.

3. The method of claim 2, wherein computing the relevancy score comprises determining a weight associated with each keyword included in the search string.

4. The method of claim 2, wherein computing a result relevance score associated with a search result comprises:

computing a permutation result relevance score for the search result that indicates the relevance between the search result and the string permutation; and

combining the string similarity score and the permutation result relevance score to generate the result relevance score associated with the search result.

5. The method of claim 1, wherein the subset of the search results comprise one or more search results included in a first plurality of search results received when a first thread completes the execution of the search, and the subset of the search results are selected before a second thread has completed the execution of the search.

6. The method of claim 5, wherein one or more search results included in a second plurality of search results received when the second thread completes the execution are selected for display after data from rows identified by the subset of the search results is displayed.

7. The method of claim 1, wherein the subset of the search results comprises a top threshold number of search results in the ordered queue.

8. The method of claim 1, further comprising:

storing the ordered queue in a cache;

receiving a second request comprising the search string for searching the database; and

retrieving data from rows in the database identified by a second subset of the search results collected in the ordered queue for display in response to the request.

9. The method of claim 1, wherein each of the plurality of string permutations is a unique permutation of the plurality of keywords in the search string.

10. A computer program product having a non-transitory computer readable storage medium storing executable code for performing a keyword search on a database, the code when executed performs steps comprising:

receiving a request including a search string for searching the database, wherein data in the database is represented by one or more tokenized data segments, each tokenized data segment being associated with a different set of columns included in the database and specifying all unique values in the set of columns;

parsing the search string to identify a plurality of keywords included in the search string;

generating a plurality of string permutations based on the received search string, each string permutation being database agnostic and including at least a subset of the plurality of keywords included in the received search string;

for each string permutation;

launching an asynchronous thread for executing a search on the one or more compressed tokenized data segments based on the string permutation;

receiving a plurality of search results when the thread completes execution of the search, each search result identifying a row in the database that includes data relevant to the string permutation,

computing a result relevance score associated with each search result as a measure of relevance between the search result and the received search string, and

collecting the plurality of search results in an ordered queue, the ordering of the search results based on the result relevance score associated with each search result; and

retrieving data from rows in the database identified by a subset of the search results collected in the ordered queue for display in response to the request.

11. The computer program product of claim 10, further comprising, for each string permutation, computing a string similarity score for the string permutation based on the similarity between the string permutation and the search string.

12. The computer program product of claim 11, wherein computing the relevancy score comprises determining a weight associated with each keyword included in the search string.

13. The computer program product of claim 11, wherein computing a result relevance score associated with a search result comprises:

computing a permutation result relevance score for the search result that indicates the relevance between the search result and the string permutation; and

combining the string similarity score and the permutation result relevance score to generate the result relevance score associated with the search result.

14. The computer program product of claim 10, wherein the subset of the search results comprise one or more search results included in a first plurality of search results received when a first thread completes the execution of the search, and the subset of the search results are selected before a second thread has completed the execution of the search.

16. The computer program product of claim 10, wherein the subset of the search results comprises a top threshold number of search results in the ordered queue.

17. The computer program product of claim 10, further comprising:

storing the ordered queue in a cache;

receiving a second request comprising the query for searching the database; and

retrieving data from rows in the database identified by a second subset of the search results collected in the ordered queue for display in response to the request.

18. The computer program product of claim 10, wherein each of the plurality of string permutations is a unique permutation of the plurality of keywords in the search string.

15. The computer program product of claim 15, wherein one or more search results included in a second plurality of search results received when the second thread completes the execution are selected for display after data from rows identified by the subset of the search results is displayed.

19. A computer system, comprising:

a database, wherein data in the database is represented by one or more tokenized data segments, each tokenized data segment being associated with a different set of columns included in the database and specifying all unique values in the set of columns; and

a search orchestration engine executing on a computer processor and configured to;

receive a request including a query for searching the database, wherein data in the database is represented by one or more tokenized data segments, each tokenized data segment being associated with a different set of columns included in the database and specifying all unique values in the set of columns, the received query comprising a plurality of keywords;

generate a plurality of string permutations based on the received query, each string permutation being database agnostic and including at least a subset of the plurality of keywords included in the received query;

for each string permutation;

launch an asynchronous thread for executing a search on the one or more compressed tokenized data segments based on the string permutation;

receive a plurality of search results when the thread completes execution of the search, each search result identifying a row in the database that includes data relevant to the string permutation,

compute a result relevance score associated with each search result as a measure of relevance between the search result and the received query, and

collect the plurality of search results in an ordered queue, the ordering of the search results based on the result relevance score associated with each search result; and

retrieve data from rows in the database identified by a subset of the search results collected in the ordered queue for display in response to the request.

20. The system of claim 19, wherein the search orchestration engine is further configured to:

for each string permutation, compute a string similarity score score for the string permutation based on the similarity between the string permutation and the query.

for each search result, compute a permutation result relevance score that indicates the relevance between the search result and the string permutation; and

combine the string similarity score and the permutation result relevance score to generate the result relevance score associated with the search result.