Reading object queries

• US 9,405,853 B2
• Filed: 06/17/2013
• Issued: 08/02/2016
• Est. Priority Date: 06/17/2013
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Banner, Ron, Golan, Shahar, Barkol, Omer
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US13/919,294
• Publication Number:
  US 20140372413A1
• Time in Patent Office: 1,142 Days
• Field of Search: 707/722
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

Disclosed herein are a system, non-transitory computer readable medium, and method for responding to a query having a plurality of input objects. A subgraph based on a main graph of objects is used to generate a list of objects associating the input objects.

Claims

1. A system comprising:

a processor;

a memory comprising a data structure, the data structure comprising a main graph of interconnected objects comprising a link between each pair of objects that represents a distance measure therebetween; and

a query handler, implemented via the processor, to;

read a query comprising a plurality of input objects;

locate each input object in the main graph;

detect a subgraph in the main graph such that a total distance between each input object and a central object of the detected subgraph is minimized by;

broadcasting a message from each input object located in the main graph,

determining which object in the main graph is a first object to receive each message broadcast by each input object, and

appointing the first object to be the central object of the subgraph; and

generate an ordered list of objects from the main graph that associates the plurality of input objects in the query, the ordered list of objects being based at least partially on the subgraph.

2. The system of claim 1, wherein the distance measure is indicative of a similarity between each pair of objects.

3. The system of claim 1, wherein to detect the subgraph, the query handler is to detect each object positioned on a shortest path between each input object and the central object.

4. The system of claim 3, wherein to detect the subgraph, the query handler is to include in the subgraph each object detected on the shortest path between each input object and the central object.

5. The system of claim 1, wherein to generate the ordered list of objects, the query handler is to employ random walk with restart on the main graph such that nodes containing objects of the subgraph are used as starting nodes.

6. The system of claim 1, wherein the query handle is further to:

determine the central object of the subgraph based on determining a shortest distance between each input object and the central object.

7. A non-transitory computer readable medium having instructions therein which, if executed, cause at least one processor to:

read a query comprising a plurality of input objects;

search for each input object in a main graph comprising a plurality of objects and a distance metric associating each pair of objects therein;

identify a subgraph in the main graph such that a total distance between each input object and a central object of the identified subgraph is minimized by;

broadcasting a message from each input object located in the main graph,

determining which object in the main graph is a first object to receive each message broadcast by each input object, and

appointing the first object to be the central object of the subgraph; and

generate an ordered list of objects from the main graph that associate the plurality of input objects such that the ordered list of objects is based at least partially on the subgraph.

8. The non-transitory computer readable medium of claim 7, wherein the distance metric between each pair of objects indicates a similarity between each pair of objects.

9. The non-transitory computer readable medium of claim 7, wherein the instructions stored therein, if executed, instructs at least one processor to detect each object positioned on a shortest path between each input object and the central object.

10. The non-transitory computer readable medium of claim 9, wherein the instructions stored therein, if executed, instructs at least one processor to include in the subgraph each detected object on the shortest path between each input object and the central object.

11. The non-transitory computer readable medium of claim 7, wherein the instructions therein, if executed, further instruct at least one processor to generate the ordered list of objects using random walk with restart on the main graph such that nodes containing objects of the subgraph are used as starting nodes.

12. A method comprising:

reading, using at least one processor, a query comprising a plurality of input objects;

locating, using at least one processor, each input object in a database comprising a main graph of interconnected objects with a distance metric associating each pair of objects therein;

constructing, using at least one processor, a subgraph of objects from the main graph such that a total distance between each input object and a central object of the constructed subgraph is minimized by;

broadcasting a message from each input object located in the main graph,

determining which object in the main graph is a first object to receive each message broadcast by each input object, and

appointing the first object to be the central object of the subgraph; and

responding, using at least one processor, to the query with a ranked list of objects from the main graph that represent associations between the plurality of input objects, generation of the ranked list of objects to be based at least partially on the subgraph.

13. The method of claim 12, wherein the distance metric between each pair of objects indicates a similarity between each pair of objects.

14. The method of claim 12, wherein constructing the subgraph further comprises detecting, using at least one processor, each object positioned on a shortest path between each input object and the central object.

15. The method of claim 14, wherein constructing the subgraph further comprises including in the subgraph, using at least one processor, each object detected on the shortest path between each input object and the central object.

16. The method of claim 12, wherein generating the ranked list comprises executing, using at least one processor, random walk with restart on the main graph such that nodes containing objects of the subgraph are used as starting nodes.

17. The method of claim 12, further comprising:

determining the central object of the subgraph by determining a shortest distance between each input object and the central object.