Identifying relationship instances between entities

Patent metadata

Field	Value
Publication number	US-10540360-B2
Application number	US-201615223271-A
Country	US
Kind code	B2
Filing date	Jul 29, 2016
Priority date	Jul 29, 2016
Publication date	Jan 21, 2020
Grant date	Jan 21, 2020

Abstract

A method, a computing system, and a non-transitory machine readable storage medium containing instructions for identifying relationships between entities are provided. In an example, the method includes receiving a query. The query specifies a first computing entity, a second computing entity, and a window of time. A data structure is queried based on the query to identify a set of relationship instances each corresponding to a relationship between the first computing entity and the second computing entity during the window of time. A representation of the first computing entity, the second computing entity, and the set of relationship instances is provided at a user interface.

First claim

What is claimed is:

1. A method comprising:
receiving a query specifying a first computing entity, a second computing entity, and a window of time;
querying a data structure based on the query to identify a set of relationship instances each corresponding to a relationship between the first computing entity and the second computing entity during the window of time; and
providing a representation of the first computing entity, the second computing entity, and the set of relationship instances at a user interface;
wherein the querying of the data structure comprises:
identifying a start of the window of time in an adjacency list associated with the first computing entity;
identifying, from the start of the window of time, a first entry in the adjacency list that is within the window of time;
determining whether the first entry represents a relationship between the first computing entity and the second computing entity; and

updating, based on determining that the first entry represents the relationship between the first computing entity and the second computing entity, the set of relationship instances.

2. The method of claim 1 , wherein the identifying of the start of the window of time in the adjacency list includes performing a binary search of the adjacency list to identify the start.

3. The method of claim 1 , wherein the querying of the data structure includes: following a previous instance pointer from the first entry to a second entry that represents a relationship between the first computing entity and the second computing entity; determining whether the second entry is within the window of time; and based on determining that the second entry is within the window of time, updating the set of relationship instances based on the second entry.

4. The method of claim 1 , wherein the query is a first query and the window of time is a first window of time, the method comprising:
receiving a second query specifying a relationship instance of the set of relationship instances and a depth;
identifying a second window of time associated with the second query;
identifying a first set of computing entities having a relationship with an entity selected from a group consisting of: the first computing entity and the second computing entity during the second window of time; and
based on the depth, identifying a second set of computing entities having a relationship with an entity of the first set of computing entities during the second window of time.

5. The method of claim 4 ,
wherein the data structure includes a neighbor pointer that links an entry in an adjacency list associated with the first computing entity to an entry in an adjacency list associated with a third computing entity, and
wherein the identifying of the second set of computing entities includes identifying the window of time in the adjacency list associated with the third computing entity using the neighbor pointer.

6. The method of claim 1 , wherein the relationship includes a communication session.

7. The method of claim 1 , wherein the providing of the representation includes providing a time-varying graph representing the first computing entity and the second computing entity as nodes and representing a relationship of the set of relationship instances as an edge.

8. The method of claim 1 comprising selecting an instance of the set of relationship instances to represent a plurality of concurrent relationships based on a skip chain of the data structure.

9. A computing system method comprising:
a relationship data store to store a time-varying data structure;
a query engine communicatively coupled to the relationship data store, wherein the query engine is to:
receive a first query specifying a first computing entity, a second computing entity, and a first window of time;
query the time-varying data structure according to the first query to identify a set of relationship instances between the first computing entity and the second computing entity during the first window of time;
receive a second query specifying a relationship instance of the set of relationship instances, wherein the relationship instance has an associated second window of time; and
query the time-varying data structure according to the second query to identify a first set of computing entities having a relationship with an entity selected from a group consisting of: the first computing entity and the second computing entity during the second window of time;

wherein querying the time-varying data structure according to the first query comprises:
identifying a start of the first window of time in an adjacency list associated with the first computing entity;
identifying, from the start of the first window of time, a first entry in the adjacency list that is within the first window of time;
determining whether the first entry represents a relationship between the first computing entity and the second computing entity; and

updating, based on determining that the first entry represents the relationship between the first computing entity and the second computing entity, the set of relationship instances associated with the first window of time.

10. The computing system of claim 9 ,
wherein the second query specifies a depth, and
wherein the query engine is to, based on the depth, identify a second set of computing entities having a relationship with an entity of the first set of computing entities.

11. The computing system of claim 10 ,
wherein the time-varying data structure includes a neighbor pointer that links an entry in an adjacency list associated with the first computing entity to an entry in an adjacency list associated with a third computing entity of the first set of computing entities, and
wherein the query engine is to identify the second window of time in the adjacency list associated with the third computing entity using the neighbor pointer to identify a second set of computing entities.

12. The computing system of claim 9 comprising a user interface communicatively coupled to the query engine, wherein the user interface is to provide a representation of the set of relationship instances and of the first set of computing entities.

13. The computing system of claim 9 , wherein the representation represents the first computing entity, the second computing entity, and entities of the first set of computing entities as nodes and relationships therebetween as edges.

14. The computing system of claim 9 , wherein a relationship of the set of relationship instances represents a communication session between two computing entities.

15. A non-transitory computer-readable memory resource storing instructions that when executed cause at least one processing resource to:
receive a query for information regarding a relationship between a first computing entity and a second computing entity during a window of time;
query a data structure based on the query to identify a set of relationship instances between the first computing entity and the second computing entity during the window of time; and
provide a representation of the first computing entity and the second computing entity
as nodes and a representation of a relationship instance of the set of relationship instances as an edge extending between the nodes;
wherein the instructions that cause the at least one processing resource to query the data structure comprise instructions that cause the at least one processing resource to:
identify a start of the window of time in an adjacency list associated with the first computing entity;
identify, from the start of the window of time, a first ent

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Nor Igor
• Schein Sagi
• Barkol Omer
• Hayun Eyal

Classifications

• H04L41/22

  comprising specially adapted graphical user interfaces [GUI] · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/2477 Primary

  Temporal data queries · CPC title

• G06F17/40

  Data acquisition and logging (for input to computer G06F3/00) · CPC title

• G06F11/323

  Visualisation of programs or trace data · CPC title