Cognitive memory encoding networks for fast semantic indexing storage and retrieval

• US 9,158,847 B1
• Filed: 07/19/2012
• Issued: 10/13/2015
• Est. Priority Date: 07/19/2011
• Status: Active Grant

• Current Assignee: QlikTech International AB (Qlik Technologies)
• Original Assignee: Kyndi, Inc
• Inventors: Majumdar, Arun
• Primary Examiner(s): Nguyen, Loan T
• Application Number:
  US13/553,662
• Time in Patent Office: 1,181 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06N 3/02 Neural networks

Abstract

The invention provides a fast approximate as well as exact hierarchical network storage and retrieval system and method for encoding and indexing graphs or networks into a data structure called the Cognitive Signature for property based, analog based or structure or sub-structure based search. The system and method produce a Cognitive Memory from a multiplicity of stored Cognitive Signatures and are ideally suited to store and index all or parts of massive data sets, linguistic graphs, protein graphs, chemical graphs, graphs of biochemical pathways, image or picture graphs as well as dynamical graphs such as traffic graphs or flows and motion picture sequences of graphs. The system and method have the advantage that properties of the Cognitive Signature of the graph can be used in correlations to the properties of the underlying data making the system ideal for semantic indexing of massive scale graph data sets.

Claims

1. A non-transitory computer readable medium including therein a data structure, which is a Cognitive Signature, comprising:

a field to identify a contraction level of a plurality of contraction levels of a network;

a field entry for a Globally Unique Identity Designation (GUID);

a field T of an ordered list of first vectors, each first vector corresponding to the contraction level of the network;

a field G of a list of second vectors, each second vector corresponding to the contraction level of the network;

a field F to contain a Bloom Filter as a binary vector comprised of values of each of the first vectors in field T and the second vectors in field G, the binary vector being computed based on a first threshold vector corresponding to field T and a second threshold vector corresponding to field G;

a field to contain a set of symbols S that label the network;

a field for a Discrete Unlabeled Network Representation Code (DUNRC);

a field for a Discrete Colored Network Representation Code (DCNRC);

a field for contraction tree operator expressions to identify whether the network was contracted by a contraction rule; and

a field for a pointer to a next Cognitive Signature at an incremented level of contraction.

2. The non-transitory computer readable medium of claim 1, wherein the Cognitive Signature is produced each time the network is processed and each time the network is contracted.

3. The non-transitory computer readable medium of claim 2, wherein each of the Cognitive signatures, ending in a Cognitive Signature in which the pointer to the next Cognitive signature is null, is collectively a Cognitive Memory.

4. The non-transitory computer readable medium of claim 3, wherein the network is encoded in a vector space and as numerical codes that enables the network to be reconstructed.

5. The non-transitory computer readable medium of claim 3, wherein a plurality of networks are stored in a plurality of Cognitive Memories.

7. The non-transitory computer readable medium of claim 5, wherein the plurality of Cognitive Memories exceeds the plurality of contraction levels by one.

8. The non-transitory computer readable medium of claim 1, wherein the DUNRC is computed based on a plurality of codes obtained from an upper triangular portion of a connectivity matrix of the network.

9. The non-transitory computer readable medium of claim 8, wherein the DUNRC is computed by calculating a factoradic code of a concatenation of the plurality of codes.

10. The non-transitory computer readable medium of claim 1, wherein the DCNRC includes computing an intermediate weighing matrix whose components are computed based on a predetermined weighing function of nodes of the network.

11. The non-transitory computer readable medium of claim 10, wherein the predetermined weighing function is a reciprocal square root of a product of weights of a node pair that are connected to each other.

6. A method of creating a data structure, which is a Cognitive Signature, using a computer having a microprocessor for each step, the method comprising:

inputting a network;

generating a Globally Unique Identity Designation (GUID);

identifying a contraction level of a plurality of contraction levels of the network;

generating an ordered list of first vectors in a field T, each first vector corresponding to the contraction level of the network;

generating a list of second vectors in a field G, each second vector corresponding to the contraction level of the network;

computing a Bloom Filter as a binary vector comprised of values of each of the first vectors in field T and the second vectors in field G based on a first threshold vector corresponding to field T and second threshold vector corresponding to field G;

labeling the network with a set of symbols S;

generating a Discrete Unlabeled Network Representation Code (DUNRC) and generating a Discrete Colored Network Representation Code (DCNRC);

executing contraction tree operator expressions to identify whether the network was contracted by a contraction rule; and

generating a pointer to a next Cognitive Signature at an incremented level of contraction.

12. The method of claim 6, wherein a plurality of networks are stored in a plurality of Cognitive Memories, the plurality of Cognitive Memories exceeding the plurality of contraction levels by one.

13. The method of claim 6, wherein the step of generating the DUNRC further comprises:

computing the DUNRC based on a plurality of codes obtained from an upper triangular portion of a connectivity matrix of the network.

14. The method of claim 13, further comprising:

computing the DUNRC by calculating a factoradic code of a concatenation of the plurality of codes.

15. The method of claim 6, wherein the step of generating the DCNRC further comprises:

computing an intermediate weighing matrix, whose components are computed based on a predetermined weighing function of nodes of the network.

16. The method of claim 15, wherein the predetermined weighing function is a reciprocal square root of a product of weights of a node pair that are connected to each other.