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

• US 9,208,204 B2
• Filed: 12/02/2014
• Issued: 12/08/2015
• 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/558,036
• Publication Number:
  US 20150154265A1
• 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:

receiving, by an entity extraction computer, a user input of search query parameters from a user interface, wherein the user interface is presented on a user computer;

extracting, by the entity extraction computer, in real-time, as search query data is requested by the user computer, one or more entities from the search query parameters by comparing the search query parameters with an entity co-occurrence database having instances of co-occurrence of the one or more entities in an electronic data corpus and identifying at least one entity type corresponding to the one or more entities in the search query parameters;

selecting, by a fuzzy-score matching computer, in real-time, as the search query data is requested by the user computer, a fuzzy matching algorithm for searching the entity co-occurrence database to identify one or more records associated with the search query parameters, wherein the fuzzy matching algorithm corresponds to the at least one identified entity type, wherein at least one of the entity extraction computer or the fuzzy-score matching computer comprises a main memory which hosts an in-memory database comprising the entity co-occurrence database, wherein the in-memory database comprises a plurality of records indexed as structured data, wherein the structured data comprises at least one of an entity-to-entity index, an entity-to-topic index, or an entity-to-fact index;

searching, by the fuzzy-score matching computer, in real-time, as the search query data is requested by the user computer, the entity co-occurrence database using the selected fuzzy matching algorithm and forming one or more suggested search query parameters from the one or more records based on the search, wherein the one or more suggested search query parameters includes a plurality of suggested search query parameters;

presenting, by the fuzzy-score matching computer, the one or more suggested search query parameters to the user interface; and

sorting, by the fuzzy-score matching computer, the plurality of suggested search query parameters in a descending order based on a proximity of a match to the search query parameters in the user input.

2. The method of claim 1 further comprising searching, by the fuzzy-score matching computer, the entity co-occurrence database using the selected fuzzy matching algorithm before the user input is finalized.

3. The method of claim 1 wherein the one or more records associated with the search query parameters include conceptual features.

4. The method of claim 1, wherein the fuzzy-score matching computer presents the sorted plurality of suggested search query parameters in a drop down list via the user interface.

5. The method of claim 1 wherein the entity co-occurrence database is indexed.

6. A system comprising:

one or more server computers having one or more processors executing computer readable instructions for a plurality of computer modules including;

an entity extraction module configured to receive a user input of search query parameters from a user interface, wherein the user interface is presented on a user computer, wherein the entity extraction module being further configured to;

extract one or more entities, in real-time, as search query data is requested by the user computer, from the search query parameters by comparing the search query parameters with an entity co-occurrence database having instances of co-occurrence of the one or more entities in an electronic data corpus and identifying at least one entity type corresponding to the one or more entities in the search query parameters, wherein the one or more server computers comprises a main memory which hosts an in-memory database comprising the entity co-occurrence database, wherein the in-memory database comprises a plurality of records indexed as structured data, wherein the structured data comprises at least one of an entity-to-entity index, an entity-to-topic index, or an entity-to-fact index; and

a fuzzy-score matching module configured to select in real-time, as the search query data is requested by the user computer, a fuzzy matching algorithm for searching the entity co-occurrence database to identify one or more records associated with the search query parameters, wherein the fuzzy matching algorithm corresponds to the at least one identified entity type, the fuzzy-score matching module being further configured to;

search in real-time, as the search query data is requested by the user computer, the entity co-occurrence database using the selected fuzzy matching algorithm and form one or more suggested search query parameters from the one or more records based on the search, and present the one or more suggested search query parameters to the user interface, wherein the one or more suggested search query parameters includes a plurality of suggested search query parameters, wherein the fuzzy-score matching module is configured to sort the plurality of suggested search query parameters in a descending order based on a proximity of a match to the search query parameters in the user input.

7. The system of claim 6 wherein the fuzzy-score matching module is further configured to search the entity co-occurrence database using the selected fuzzy matching algorithm before the user input is finalized.

8. The system of claim 6 wherein the one or more records associated with the search query parameters include conceptual features.

9. The system of claim 6, wherein the fuzzy-score matching module is configured to present the sorted plurality of suggested search query parameters in a drop down list via the user interface.

10. The system of claim 6 wherein the entity co-occurrence database is indexed.