Domain based keyword search

• US 9,477,729 B2
• Filed: 05/09/2014
• Issued: 10/25/2016
• Est. Priority Date: 02/20/2004
• Status: Active Grant

• Current Assignee: Informatica LLC (Informatica, Inc. (California))
• Original Assignee: Informatica LLC (Informatica, Inc. (California))
• Inventors: Bhattiprolu, Pradeep, Grondin, Richard
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Hoffler, Raheem
• Application Number:
  US14/274,573
• Publication Number:
  US 20140250119A1
• Time in Patent Office: 900 Days
• Field of Search: None
• US Class Current: 1/1
• 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 by a computer processor, the method comprising:

receiving a request including a search string for searching the database;

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, the plurality of string permutations including two string permutations each comprising different orderings of a same subset of the plurality of keywords;

for each string permutation;

determining a string similarity score between the string permutation and the search string based on which keywords are included in the string permutation and an order of keywords in the string permutation relative to an order of the keywords in the search string;

launching an asynchronous thread for executing a search on the data in the database 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;

determining a result relevance score associated with each search result by combining the string similarity score for the string permutation and a permutation result relevance score included with the search result, the permutation result relevance score measuring relevance between the string permutation and the data relevant to the string permutation; 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, wherein determining the string similarity score comprises:

determining a weight associated with a keyword included in the string permutation based on whether the keyword has a same location in the string permutation as it does in the search string; and

adding the determined weight for the keyword into the string similarity score.

3. 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.

4. The method of claim 3, 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.

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

6. 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.

7. 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.

8. The method of claim 1, wherein launching the asynchronous thread for executing the search comprises:

accessing a virtual table definition that is a view into a data model of the database represented in a domain structure;

translating the string permutation into a set of data model queries for searching the data model using the virtual table definition; and

searching the data stored in the database based on the set of data model queries to produce the plurality of search results.

9. The method of claim 8, wherein the 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.

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;

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, the plurality of string permutations including two string permutations each comprising different orderings of a same subset of the plurality of keywords;

for each string permutation;

determining a string similarity score between the string permutation and the search string based on which keywords are included in the string permutation and an order of keywords in the string permutation relative to an order of the keywords in the search string;

launching an asynchronous thread for executing a search on the data in the database 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;

determining a result relevance score associated with each search result by combining the string similarity score for the string permutation and a permutation result relevance score included with the search result, the permutation result relevance score measuring relevance between the string permutation and the data relevant to the string permutation; 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, wherein determining the string similarity score comprises:

determining a weight associated with a keyword included in the string permutation based on whether the keyword has a same location in the string permutation as it does in the search string; and

adding the determined weight for the keyword into the string similarity score.

12. 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.

13. The computer program product of claim 12, 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.

14. 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.

15. 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.

16. 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.

17. The computer program product of claim 10, wherein launching the asynchronous thread for executing the search comprises:

accessing a virtual table definition that is a view into a data model of the database represented in a domain structure;

translating the string permutation into a set of data model queries for searching the data model using the virtual table definition; and

searching the data stored in the database based on the set of data model queries to produce the plurality of search results.

18. The computer program product of claim 17, wherein the 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.

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 search string for searching the database, the received query comprising a plurality of keywords;

generate 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, the plurality of string permutations including two string permutations each comprising different orderings of a same subset of the plurality of keywords;

for each string permutation;

determine a string similarity score between the string permutation and the search string based on which keywords are included in the string permutation and an order of keywords in the string permutation relative to an order of the keywords in the search string;

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;

determine a result relevance score associated with each search result by combining the string similarity score for the string permutation and a permutation result relevance score included with the search result, the permutation result relevance score measuring relevance between the string permutation and the data relevant to the string permutation; 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 computer system of claim 19, wherein launching the asynchronous thread for executing the search comprises:

accessing a virtual table definition that is a view into a data model of the database represented in a domain structure;

translating the string permutation into a set of data model queries for searching the data model using the virtual table definition; and

searching the one or more compressed tokenized data segments stored in the data model based on the set of data model queries to produce the plurality of search results.