SYSTEMS AND METHODS FOR LARGE-SCALE LINK ANALYSIS

• US 20110131208A1
• Filed: 09/23/2010
• Published: 06/02/2011
• 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: Shainer, Gabby, Goldfarb, Eithan
• Granted Patent: US 9,135,630 B2
• Time in Patent Office: Days
• US Class Current: 707/736
• 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 a single entity record that indicates all the linked entities that have been identified as being related to the entity;

storing in a memory multiple entity records, each corresponding respectively to one of the entities in the group; and

performing, using the link processor, an analytics operation with respect to the entities by querying at least one of the entity records stored in the memory.

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 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 at least a portion of 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.

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

8. The method according to claim 7, 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.

9. 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.

10. 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.

11. The method according to claim 1, and comprising identifying one or more of the entities as targets-of-interest, and performing the analytics operation with respect to the targets-of-interest.

12. 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 entity, to store in the memory multiple entity records, each corresponding respectively to one of the entities in the group, and to perform an analytics operation with respect to the entities by querying at least one of the entity records stored in the memory.

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

14. The apparatus according to claim 12, 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.

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

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

17. The apparatus according to claim 12, wherein the memory comprises at least a Random Access Memory (RAM), and wherein the link processor is configured to store at least a portion of the entity records in an in-memory data structure residing in the RAM, and to perform the analytics operation by querying the in-memory data structure.

18. The apparatus according to claim 17, 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.

19. The apparatus according to claim 18, 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.

20. The apparatus according to claim 12, 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.

21-22. -22. (canceled)