Providing search results based on a compositional query

Patent metadata

Field	Value
Publication number	US-11762933-B2
Application number	US-202017105991-A
Country	US
Kind code	B2
Filing date	Nov 27, 2020
Priority date	Dec 12, 2012
Publication date	Sep 19, 2023
Grant date	Sep 19, 2023

Abstract

A technique for providing search results may include determining a first entity type, a second entity type, and a relationship type based on a compositional query. The technique may also include identifying nodes of a knowledge graph corresponding to entity references of the first entity type and entity references of the second entity type. The technique may also include determining from the knowledge graph an attribute value corresponding to the relationship type for each entity reference of the first entity type and for each entity reference of the second entity type. The technique may also include comparing the attribute value of each entity reference of the first entity type with the attribute value of each entity reference of the second entity type. The technique may also include determining one or more resultant entity references from the entity references of the first entity type based on the comparing.

First claim

The invention claimed is:

1. A method implemented by one or more processors, the method comprising:
receiving a single compositional query from a user, the single compositional query including a first entity reference, a second entity reference and a distance indication, determining a first entity type corresponding with the first entity reference, a second entity type corresponding with the second entity reference, and a distance criterion corresponding with the distance indication;
identifying, from a data structure based on the single compositional query, a plurality of first candidate entity references of the first entity type;
identifying, from the data structure based on the single compositional query, a plurality of second candidate entity references of the second entity type;
determining, from the data structure based on the single compositional query, respective attribute values corresponding to a distance relationship for each of the plurality of first candidate entity references and each of the plurality of second candidate entity references;
comparing the respective attribute values corresponding to the distance relationship for each of the plurality of first candidate entity references and each of the plurality of second candidate entity references to the distance criterion;
determining, based on the comparing, two or more first resultant entity references, of the first entity type, and two or more second resultant entity references, of the second entity type; and
causing to be displayed, responsive to receiving the single compositional query and as annotations on a map of a graphical user interface:
the two or more first resultant entity references,
the two or more second resultant entity references, and
a user-adjustable graphical element that can be interacted with to adjust the distance criterion.

2. The method of claim 1 , wherein each of the respective attribute values comprise a location, and wherein the comparing comprises determining a corresponding distance between each of the plurality of first candidate entity references and each of the plurality of second candidate entity references.

3. The method of claim 2 , wherein determining the two or more first resultant entity references comprises determining the two or more first resultant entity references based on the corresponding distances of the two or more first resultant entity references satisfying the distance criterion determined based on the distance relationship.

4. The method of claim 1 , wherein the distance relationship is an implicit term and further comprising determining the distance criterion based on the distance criterion being predefined for the implicit term.

5. The method of claim 1 , further comprising:
in response to user interaction with the user-adjustable graphical element to broaden the distance criterion to a broadened distance criterion:
causing to be added, as an additional annotation on the map of the graphical user interface, at least one additional of the two or more first resultant entity references that satisfies the broadened distance criterion but that fails to satisfy the distance criterion.

6. The method of claim 1 , further comprising:
in response to user interaction with the user-adjustable graphical element to narrow the distance criterion to a narrowed distance criterion:
causing to be removed, from the map of the graphical user interface, at least one of the two or more first resultant entity references that fails to satisfy the narrowed distance criterion.

7. The method of claim 1 , wherein the data structure comprises a knowledge graph.

8. The method of claim 1 , wherein the data structure includes a pre-generated table that is indexed by entity reference and entity type.

9. A system comprising:
at least one processor;
a display device; and
memory storing instructions that, when executed by the at least one processor, cause the system to perform operations including:
receiving a single compositional query from a user, the single compositional query including a first entity reference, a second entity reference and a distance indication, determining a first entity type corresponding with the first entity reference, a second entity type corresponding with the second entity reference, and a distance criterion corresponding with the distance indication;
identifying, from a data structure based on the single compositional query, a plurality of first candidate entity references of the first entity type;
identifying, from the data structure based on the single compositional query, a plurality of second candidate entity references of the second entity type;
determining, from the data structure based on the single compositional query, respective attribute values corresponding to a distance relationship for each of the plurality of first candidate entity references and each of the plurality of second candidate entity references;
comparing the respective attribute values corresponding to the distance relationship for each of the plurality of first candidate entity references and each of the plurality of second candidate entity references to the distance criterion;
determining, based on the comparing, two or more first resultant entity references, of the first entity type, and two or more second resultant entity references, of the second entity type; and
causing to be displayed by the display device, responsive to the single compositional query and as annotations on a map of a graphical user interface:
the two or more first resultant entity references,
the two or more second resultant entity references, and
a user-adjustable graphical element that can be interacted with to adjust the distance criterion.

10. The system of claim 9 , wherein each of the respective attribute values comprise a location, and wherein the comparing comprises determining a corresponding distance between each of the plurality of first candidate entity references and each of the plurality of second candidate entity references.

11. The system of claim 10 , wherein determining the two or more first resultant entity references comprises determining the two or more first resultant entity references based on the corresponding distances of the two or more first resultant entity references satisfying the distance criterion determined based on the distance relationship.

12. The system of claim 9 , wherein:
the distance relationship is an implicit term; and
the instructions, when executed by the at least one processor, further cause the system to perform operations including:
determining the distance criterion based on the distance criterion being predefined for the implicit term.

13. The system of claim 9 , wherein the instructions, when executed by the at least one processor, further cause the system to perform operations including:
in response to user interaction with the user-adjustable graphical element to broaden the distance criterion to a broadened distance criterion:
causing to be added, as an additional annotation on the map of the graphical user interface, at least one additional of the two or more first resultant entity references that satisfies the broadened distance criterion but that fails to satisfy the distance criterion.

14. The system of claim 9 , wherein the instructions, when executed by the at least one processor, cause further cause the system to perform operations including:
in response to user interaction with the user-adjustable graphical element to narrow the distance criterion to a narrowed distance criterion:
causing to be removed, from the map of the graphical user interface, at least one of th

Assignees

• Google Llc

Inventors

• Lou Jinyu
• Chai Ying
• Ding Chen
• Chen Lijie
• Hu Liang
• Liu Kejia
• Pan Weibin
• Huang Yanlai
• Huynh David Francois

Classifications

• G06F16/9537 Primary

  Spatial or temporal dependent retrieval, e.g. spatiotemporal queries · CPC title

• G06F16/288

  Entity relationship models · CPC title

• G06F16/248

  Presentation of query results · CPC title

• G06F16/284

  Relational databases · CPC title