Search suggestions using fuzzy-score matching and entity co-occurrence

• US 9,507,834 B2
• Filed: 11/24/2015
• Issued: 11/29/2016
• Est. Priority Date: 12/02/2013
• Status: Active Grant

• Current Assignee: Finch Computing LLC (Qbase, LLC)
• Original Assignee: Qbase, LLC
• Inventors: Lightner, Scott, Weckesser, Franz, Dave, Rakesh, Boddhu, Sanjay, Becknell, Joseph
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US14/950,874
• Publication Number:
  US 20160078099A1
• Time in Patent Office: 371 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method for generating search suggestions by using fuzzy-score matching and entity co-occurrence in a knowledge base is disclosed. Embodiments of the method may be employed in any search system that may include an entity extraction computer module that may perform partial entity extractions from provided search queries, a fuzzy-score matching computer module that may generate algorithms based on the type of entity extracted and perform a search against an entity co-occurrence knowledge base. The entity co-occurrence knowledge base, which may include a repository where entities may be indexed as entities to entities, entities to topics, or entities to facts among others, may return fast and accurate suggestions to the user to complete the search query. The suggestions may include alternates to the partial query provided by the user that may enhance and save time when performing searches.

Claims

1. A method comprising:

comparing, by a first server, a search query against a first collection of data storing an instance of co-occurrence of an entity in a second collection of data, wherein the search query is received from a client;

identifying, by the first server, a type of entity corresponding to the entity based on the comparing;

extracting, by the first server in real-time, the entity from the search query based on the identifying;

selecting, by a second server in real-time, a fuzzy matching technique corresponding to the type of the entity, wherein at least one of the first server or the second server comprises a main memory hosting a database storing the first collection of data, wherein the database stores at least one of an entity-to-entity index, an entity-to-topic index, or an entity-to-fact index;

searching, by the second server in real-time, the first collection of data via the fuzzy matching technique;

identifying, by the second server, data associated with the search query based on the searching;

generating, by the second server, a plurality of suggested search queries from the data based on the identifying;

outputting, by the second server, the suggested search queries to the client such that the suggested search queries are sorted based on match proximity to the search query.

2. The method of claim 1, wherein the searching is before the search query is finalized.

3. The method of claim 1, wherein the searching is after the search query is finalized.

4. The method of claim 1, wherein the data includes a conceptual feature.

5. The method of claim 1, wherein the suggested search queries are sorted via a drop-down list.

6. The method of claim 1, wherein the first collection of data is indexed.

7. The method of claim 1, wherein the suggested search queries are sorted in a descending order.

8. The method of claim 1, wherein the extracting, the selecting, and the outputting are in real-time as the search query is received from the client.

9. The method of claim 1, further comprising:

assigning, by the first server, a score to the entity, wherein the score is indicative of a level of certainty of the extracting being correct.

10. The method of claim 1, wherein the search query is misspelled.

11. A system comprising:

a first server configured to;

compare a search query against a first collection of data storing an instance of co-occurrence of an entity in a second collection of data, wherein the search query is received from a client,

identify a type of entity corresponding to the entity based on the comparing, extract in real-time, the entity from the search query based on the identifying;

a second server configured to;

select in real-time, a fuzzy matching technique corresponding to the type of the entity,

search the first collection of data via the fuzzy matching technique,

identify data associated with the search query based on the searching,

generate a plurality of suggested search queries from the data based on the identifying,

output the suggested search queries to the client such that the suggested search queries are sorted based on match proximity to the search query,

wherein at least one of the first server or the second server comprises a main memory hosting a database storing the first collection of data, wherein the database stores at least one of an entity-to-entity index, an entity-to-topic index, or an entity-to-fact index.

12. The system of claim 11, wherein the second server configured to search before the search query is finalized.

13. The system of claim 11, wherein the second server configured to search after the search query is finalized.

14. The system of claim 11, wherein the data includes a conceptual feature.

15. The system of claim 11, wherein the suggested search queries are sorted via a drop-down list.

16. The system of claim 11, wherein the first collection of data is indexed.

17. The system of claim 11, wherein the suggested search queries are sorted in a descending order.

18. The system of claim 11, wherein at least one of the first server or the second server is configured to extract, to select, and to output in real-time as the search query is received from the client.

19. The system of claim 11, wherein the first server configured to:

assign a score to the entity, wherein the score is indicative of a level of certainty of the extracting being correct.

20. The system of claim 11, wherein the search query is misspelled.