Search suggestions of related entities based on co-occurrence and/or fuzzy-score matching

• US 9,613,166 B2
• Filed: 10/22/2015
• Issued: 04/04/2017
• 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, Boddhu, Sanjay
• Primary Examiner(s): MORRISON, JAY A
• Application Number:
  US14/920,580
• Publication Number:
  US 20160042001A1
• Time in Patent Office: 530 Days
• Field of Search: None
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• 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/90328 using search space presentation or visualization, e.g. category or range presentation and selection
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06N 7/02 using fuzzy logic computing arrangements based on biological models G06N3/00; computing arrangements using knowledge-based models G06N5/00

Abstract

A method for generating search suggestions of related entities based on co-occurrence and/or fuzzy score matching is disclosed. The method may be employed in a search system that may include a client/server type architecture. The search system may include a user interface for a search engine in communication with one or more server devices over a network connection. The server device may include an entity extraction module, a fuzzy-score matching module, and an entity co-occurrence knowledge base database. In one embodiment, the search system may process a partial search query from a user and present search suggestions to complete the partial query. In another embodiment, the complete search query may be used as a new search query. The search system may process the new search query, run an entity extraction, find related entities from the entity co-occurrence knowledge base, and present said related entities in a drop down list.

Claims

1. A method comprising:

in real-time, as search query data is requested by a client;

extracting, by a server, a first entity from a partial search query parameter, wherein the partial search query parameter comprises an incomplete search query parameter, wherein the extracting is based on a comparison of the partial search query parameter against an instance of co-occurrence of the first entity in a data corpus and an identification of an entity type corresponding to the first entity, wherein the instance of co-occurrence of the first entity is stored in an entity co-occurrence database, wherein the server comprises a main memory storing an in-memory database which comprises the entity co-occurrence database,

selecting, by the server, a fuzzy matching process which is able to search the entity co-occurrence database and identify a record associated with the partial search query parameter, wherein the fuzzy matching process corresponds to the entity type and returns a confidence score and a ranking based on the confidence score,

searching, by the server, the entity co-occurrence database via the fuzzy matching process,

forming, by the server, based on the searching, a first suggested search query parameter based on the record;

sending, by the server, the first suggested search query parameter to the client;

receiving, by the server, a selection from the client, wherein the selection selects the first suggested search query parameter;

forming, by the server, a completed search query parameter based on the selection;

extracting, by the server, a second entity from the completed search query parameter;

identifying, by the server, a third entity in the entity co-occurrence database, wherein the third entity is related to the second entity; and

sending, by the server, a second suggested search query parameter to the client, wherein the second suggested search query parameter is based on the third entity.

2. The method of claim 1, further comprising:

extracting, by the server, a feature from the data corpus; and

assigning, by the server, the confidence score to the feature, wherein the confidence score indicates a level of certainty of the feature being extracted with a correct attribute.

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

4. The method of claim 1, wherein the record comprises a conceptual feature.

5. The method of claim 1, wherein the first suggested search query parameter comprises a plurality of first suggested search query parameters, wherein the method further comprising:

sorting, by the server, the first suggested search query parameters in a descending order based on a proximity of a match to the partial search query parameter.

6. The method of claim 4, wherein the sending of the first suggested search query parameter to the client is such that the first suggested search query parameter is presented on the client in a drop down list.

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

8. The method of claim 1, wherein the entity co-occurrence database includes an entity-to-entity index.

9. The method of claim 1, wherein the entity co-occurrence database includes an entity-to-topic index.

10. The method of claim 1, wherein the entity co-occurrence database includes an entity-to-facts index.

11. A system comprising:

a server configured to;

in real-time, as search query data is requested by a client;

extract a first entity from a partial search query parameter, wherein the partial search query parameter comprises an incomplete search query parameter, wherein the extraction is based on a comparison of the partial search query parameter against an instance of co-occurrence of the first entity in a data corpus and an identification of an entity type corresponding to the first entity, wherein the instance of co-occurrence of the first entity is stored in an entity co-occurrence database, wherein the server comprises a main memory storing an in-memory database which comprises the entity co-occurrence database,

select a fuzzy matching process which is able to search the entity co-occurrence database and identify a record associated with the partial search query parameter, wherein the fuzzy matching process corresponds to the entity type and returns a confidence score and a ranking based on the confidence score,

search the entity co-occurrence database via the fuzzy matching process,

form, based on the search, a first suggested search query parameter based on the record;

send the first suggested search query parameter to the client;

receive a selection from the client, wherein the selection selects the first suggested search query parameter;

form a completed search query parameter based on the selection;

extract a second entity from the completed search query parameter;

identify a third entity in the entity co-occurrence database, wherein the third entity is related to the second entity; and

send a second suggested search query parameter to the client, wherein the second suggested search query parameter is based on the third entity.

12. The system of claim 11, wherein the server is configured to:

extract a feature from the data corpus; and

assign the confidence score to the feature, wherein the confidence score indicates a level of certainty of the feature being extracted with a correct attribute.

13. The system of claim 11, wherein the server is configured to perform the search before the search query data is finalized.

14. The system of claim 11, wherein the record comprises a conceptual feature.

15. The system of claim 11, wherein the first suggested search query parameter comprises a plurality of first suggested search query parameters, wherein the server is configured to:

sort the first suggested search query parameters in a descending order based on a proximity of a match to the partial search query parameter.

16. The system of claim 14, wherein the server is configured to send the first suggested search query parameter to the client such that the first suggested search query parameter is presented on the client in a drop down list.

17. The system of claim 11, wherein the entity co-occurrence database is indexed.

18. The system of claim 11, wherein the entity co-occurrence database includes an entity-to-entity index.

19. The system of claim 11, wherein the entity co-occurrence database includes an entity-to-topic index.

20. The system of claim 11, wherein the entity co-occurrence database includes an entity-to-facts index.