Systems and methods for large-scale link analysis

• US 9,135,630 B2
• Filed: 09/23/2010
• Issued: 09/15/2015
• Est. Priority Date: 09/23/2009
• Status: Active Grant

• Current Assignee: Cognyte Technologies Israel Ltd. (Cognyte Software Ltd.)
• Original Assignee: Verint Systems Limited (Verint Systems Incorporated)
• Inventors: Goldfarb, Eithan, Shainer, Gabby
• Primary Examiner(s): Fleurantin, Jean B
• Assistant Examiner(s): ASPINWALL, EVAN S
• Application Number:
  US12/888,445
• Publication Number:
  US 20110131208A1
• Time in Patent Office: 1,818 Days
• Field of Search: 707/722, 707/736, 707/748, 707/752, 707/756, 707/758, 707/769, 707/802, 707/E17.044, 707/776
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Systems and methods for accepting relationship indications based on interaction among entities, where each relationship indication specifies that a respective pair of the entities may be related. A single entity record may be constructed that indicates all the linked entities that have been identified as being related to the entity. The entities may include an individual, a set of individuals, a communication terminal, a plurality of communication terminals, an organization, an e-mail address, a Web-site, a bank account and a home address. An analytics operation may performed, such as identifying a shortest sequence of interrelated entities that relate a first entity with a second entity, and acting upon the identified sequence.

Claims

1. A method, comprising:

accepting a plurality of relationship indications based on interaction among entities, each relationship indication specifying that a respective pair of the entities are related;

using a link processor, identifying for each entity among a group of the entities, based on the relationship indications, one or more linked entities that are related to the entity, and constructing for each entity in the group, a single-entity record that indicates all the linked entities that have been identified as being related to the respective entity;

storing in a memory, multiple single-entity records in a data structure, each single-entity record corresponding respectively to only one of the entities in the group;

identifying one or more of the entities as targets-of-interest; and

performing, using the link processor, an analytics operation with respect to the targets-of-interest by querying at least one of the entity records stored in the memory, the analytics operation comprising determining relationship distances between entities by executing a sequence of queries to the data structure where each query returns the entire set of entities that are linked to the queried entity;

wherein storing the entity records comprises storing the entity records in an in-memory data structure residing in Random Access Memory (RAM), and wherein performing the analytics operation comprises querying the in-memory data structure.

2. The method according to claim 1, wherein the interaction comprises communication among the entities over a communication network.

3. The method according to claim 1, wherein the entities comprise at least one entity type selected from a group of types consisting of an individual, a set of individuals, a communication terminal, a plurality of communication terminals, an organization, an e-mail address, a Web-site, a bank account and a home address.

4. The method according to claim 1, wherein constructing the single-entity record comprises storing in the single-entity record respective attributes, which characterize respective relationships between the linked entities and the respective entity.

5. The method according to claim 4, wherein the attributes indicate respective confidence levels of the relationships.

6. The method according to claim 1, wherein storing the entity records comprises storing another portion of the entity records on a magnetic storage device.

7. The method according to claim 6, wherein performing the analytics operation comprises querying at least a first entity record stored in the in-memory data structure and at least a second entity record stored on the magnetic storage device.

8. The method according to claim 1, wherein performing the analytics operation comprises identifying a shortest sequence of interrelated entities that relate a first entity with a second entity, and acting upon the identified sequence.

9. The method according to claim 1, wherein performing the analytics operation comprises querying the entity records with a query formulated in a graph query language.

10. Apparatus, comprising:

a memory; and

a link processor, which is configured to accept a plurality of relationship indications based on interaction among entities, each relationship indication specifying that a respective pair of the entities are related, to identify for each entity among a group of the entities, based on the relationship indications, one or more linked entities that are related to the entity, to construct for each entity in the group, a single-entity record that indicates all the linked entities that have been identified as being related to the respective entity, to store in the memory multiple single-entity records in a data structure, each single-entity record corresponding respectively to only one of the entities in the group, identify one or more of the entities as targets-of-interest, and to perform an analytics operation with respect to the targets-of-interest by querying at least one of the entity records stored in the memory, the analytics operation comprising determining relationship distances between entities by executing a sequence of queries to the data structure where each query returns the entire set of entities that are linked to the queried entity;

wherein storing the entity records comprises storing the entity records in an in-memory data structure residing in Random Access Memory (RAM), and wherein performing the analytics operation comprises querying the in-memory data structure.

11. The apparatus according to claim 10, wherein the interaction comprises communication among the entities over a communication network.

12. The apparatus according to claim 10, wherein the entities comprise at least one entity type selected from a group of types consisting of an individual, a set of individuals, a communication terminal, a plurality of communication terminals, an organization, an e-mail address, a Web-site, a bank account and a home address.

13. The apparatus according to claim 10, wherein the link processor is configured to store in the single single-entity record respective attributes, which characterize respective relationships between the linked entities and the entity.

14. The apparatus according to claim 13, wherein the attributes indicate respective confidence levels of the relationships.

15. The apparatus according to claim 10, wherein the memory further comprises a magnetic storage device, and wherein the link processor is configured to store another portion of the entity records on the magnetic storage device.

16. The apparatus according to claim 15, wherein the link processor is configured to perform the analytics operation by querying at least a first entity record stored in the in-memory data structure and at least a second entity record stored on the magnetic storage device.

17. The apparatus according to claim 10, wherein the link processor is configured to identify a shortest sequence of interrelated entities that relate a first entity with a second entity, and to act upon the identified sequence.