Search around visual queries

• US 9,798,768 B2
• Filed: 09/10/2012
• Issued: 10/24/2017
• Est. Priority Date: 09/10/2012
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Potter, Jordan, Ackner, Nir, Cohen, David
• Primary Examiner(s): Moser, Bruce
• Application Number:
  US13/608,864
• Publication Number:
  US 20140074888A1
• Time in Patent Office: 1,870 Days
• CPC Class Codes: G06F 16/2423 Interactive query statement specification based on a database schema
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/7335 Graphical querying, e.g. query-by-region, query-by-sketch, query-by-trajectory, GUIs for designating a person/face/object as a query predicate end-user interface involving hot spots associated with the video H04N21/4725; end-user interface for selecting a Region of Interest H04N21/4728
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9038 Presentation of query results

Abstract

A method and apparatus for a data analysis system for analyzing data object collections is provided. The data analysis system includes one or more graphical user interfaces comprising various interface elements that enable users to create visual queries. A visual query is constructed as a graph representing a pattern of interest in a collection of data objects. A visual query may include one or more graph elements and property information associated with the specified graph elements. After a user has constructed a visual query, the system may transform the visual query into a query template. A query engine may then execute the query template to search a data object collection for data object results corresponding to the specified pattern. The search for instances of a specified pattern in a collection of data objects is referred herein to as a “search around.”

Claims

1. A method comprising:

displaying on a client computing device, via a graphical user interface provided by an application server, a graph comprising one or more graph nodes and one or more graph edges;

receiving input from the client computing device via the graphical user interface indicating a selection of the graph,

wherein each graph node of the one or more graph nodes represents a data object type, and wherein each graph edge of the one or more graph edges represents a data object link;

receiving, via the graphical user interface, a selection of the one or more graph edges;

displaying, via the graphical user interface, an interface element which enables input of a link strength value which represents a condition on a number of occurrences of a relationship between two or more graph nodes;

receiving, via the interface element of the graphical user interface, input specifying a particular link strength value;

based at least on the two or more graph nodes, the one or more graph edges, and the particular link strength value, the application server transforming the graph into a query template;

wherein the query template represents one or more database queries which, when executed by the application server, returns a result set from a database, wherein each result in said result set includes a first data object, comprising one or more first data object properties and a first data object type, corresponding to a first corresponding data object type of the one or more graph nodes of the graph, and a second data object, comprising one or more second data object properties and a second data object type, corresponding to a second corresponding data object type of the two or more graph nodes of the graph, wherein the first data object and the second data object satisfy the condition on the number of occurrences of the relationship between the first data object and the second data object represented by the particular link strength value;

wherein a data object represents a collection of information as part of a data object model.

2. The method of claim 1, further comprising:

receiving input via the graphical user interface to add to the graph one or more of;

a first graph node, and a first graph edge;

re-transforming the graph based at least on the one or more added first graph nodes and first graph edges.

3. The method of claim 1, further comprising:

receiving input via the graphical user interface to add an association between one or more of the one or more graph nodes and a particular data object type;

re-transforming the graph based at least on the one or more of the one or more graph nodes.

4. The method of claim 1, further comprising:

receiving input via the graphical user interface to add an association between one or more of the one or more graph edges and one or more of;

a link type or a property match;

re-transforming the graph based at least on the one or more of the one or more graph edges.

5. The method of claim 1, further comprising:

receiving input via the graphical user interface to add an association between one or more of the one or more graph nodes and one or more data object properties;

re-transforming the graph based at least on the one or more data object properties.

6. The method of claim 1, further comprising:

receiving input via the graphical user interface to add a branching condition associated with one or more of the one or more data objects, wherein the branching condition represents one of;

a logical AND condition, and a logical OR condition;

re-transforming the graph based at least on the branching condition.

7. The method of claim 1, further comprising:

receiving input via the graphical user interface indicating that one or more of the one or more graph edges is one of;

a required graph edge, and an optional graph edge;

re-transforming the graph based at least on the one or more of the one or more graph edges.

8. The method of claim 1, wherein the transforming includes traversing the graph and identifying, for each graph element of the graph, one or more of:

a particular data object type, a particular data object link type, or one or more particular property values.

9. The method of claim 1, wherein the graph includes one or more blank graph elements, wherein each of the one or more blank graph elements is associated with a value to be supplied by a user when the query template is executed.

10. The method of claim 1, wherein the query template is an Extensible Markup Language (XML) file and includes one or more XML elements corresponding to one or more graph elements of the graph.

11. A non-transitory computer-readable medium storing one or more sequences of instructions, which when executed by one or more processors, cause the one or more processors to carry out the steps of:

displaying on a client computing device, via a graphical user interface provided by an application server, a graph comprising one or more graph nodes and one or more graph edges;

receiving input from the client computing device via the graphical user interface indicating a selection of the graph;

wherein each graph node of the one or more graph nodes represents a data object type, and wherein each graph edge of the one or more graph edges represents a data object link;

receiving, via the graphical user interface, a selection of the one or more graph edges;

displaying, via the graphical user interface, an interface element which enables input of a link strength value which represents a condition on a number of occurrences of a relationship between two or more graph nodes;

receiving, via the interface element of the graphical user interface, input specifying a particular link strength value;

based at least on the two or more graph nodes, the one or more graph edges, and the particular link strength value, the application server transforming the graph into a query template;

wherein the query template represents one or more database queries which, when executed by the application server, returns a result set from a database, wherein each result in said result set includes a first data object, comprising one or more first data object properties and a first data object type, corresponding to a first corresponding data object type of the one or more graph nodes of the graph, and a second data object, comprising one or more second data object properties and a second data object type, corresponding to a second corresponding data object type of the two or more graph nodes of the graph, wherein the first data object and the second data object satisfy the condition on the number of occurrences of the relationship between the first data object and the second data object represented by the particular link strength value;

wherein a data object represents a collection of information as part of a data object model.

12. The non-transitory computer readable medium of claim 11, wherein the one or more sequences of instructions, when executed by the one or more processors, further cause the one or more processors to carry out the steps of:

receiving input via the graphical user interface to add to the graph one or more of;

a first graph node, and a first graph edge;

re-transforming the graph based at least on the one or more added first graph nodes and first graph edges.

13. The non-transitory computer readable medium of claim 11, wherein the one or more sequences of instructions, when executed by the one or more processors, further cause the one or more processors to carry out the steps of:

receiving input via the graphical user interface to add association between one or more of the one or more graph nodes and a particular data object type;

re-transforming the graph based at least on the one or more of the one or more graph nodes.

14. The non-transitory computer readable medium of claim 11, wherein the one or more sequences of instructions, when executed by the one or more processors, further cause the one or more processors to carry out the steps of:

receiving input via the graphical user interface to add an association between one or more of the one or more graph edges and one or more of;

a link type or a property match;

re-transforming the graph based at least on the one or more of the one or more graph edges.

15. The non-transitory computer readable medium of claim 11, wherein the one or more sequences of instructions, when executed by the one or more processors, further cause the one or more processors to carry out the steps of:

receiving input via the graphical user interface indicating an association between one or more of the one or more graph nodes and one or more data object properties;

re-transforming the graph based at least on the one or more data object properties.

16. The non-transitory computer readable medium of claim 11, wherein the one or more sequences of instructions, when executed by the one or more processors, further cause the one or more processors to carry out the steps of:

receiving input via the graphical user interface to add a branching condition associated with one or more of the one or more data objects, wherein the branching condition represents one of;

a logical AND condition, and a logical OR condition;

re-transforming the graph based at least on the branching condition.

17. The non-transitory computer readable medium of claim 11, wherein the one or more sequences of instructions, when executed by the one or more processors, further cause the one or more processors to carry out the steps of:

receiving input via the graphical user interface indicating that one or more of the one or more graph edges is one of;

a required graph edge, and an optional graph edge;

re-transforming the graph based at least on the one or more of the one or more graph edges.

18. The non-transitory computer readable medium of claim 11, wherein the transforming includes traversing the graph and identifying, for each graph element of the graph, one or more of:

a particular data object type, a particular data object link type, or one or more particular property values.

19. The non-transitory computer readable medium of claim 11, wherein the graph includes one or more blank graph elements, wherein each of the one or more blank graph elements is associated with a value to be supplied by a user when the query template is executed.

20. The non-transitory computer readable medium of claim 11, wherein the query template is an Extensible Markup Language (XML) file and includes one or more XML elements corresponding to one or more graph elements of the graph.