WEIGHTED SUBSYMBOLIC DATA ENCODING

• US 20160171041A1
• Filed: 12/10/2015
• Published: 06/16/2016
• Est. Priority Date: 12/10/2014
• Status: Active Grant

• Current Assignee: QlikTech International AB (Qlik Technologies)
• Original Assignee: Kyndi, Inc
• Inventors: MAJUMDAR, Arun
• Granted Patent: US 10,120,933 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Described herein is a method and system of geometrically encoding data including partitioning data into a plurality of semantic classes based on a dissimilarity metric, generating a subspace formed by first and second data elements, the first and second data elements being included in first and second numbers of partitioned semantic classes, encoding the first data element with respect to the second data element such that the generated subspace formed by the first data element and the second data element is orthogonal, computing a weight distribution of the first data element with respect to the second data element, the weight distribution being performed for each of the first number of semantic classes and the second number of semantic classes, and determining a dominant semantic class corresponding to an ordered sequence of the first data element and the second data element, the dominant semantic class having a maximum weight distribution.

Claims

1. A method of geometrically encoding data, the method being performed by circuitry included in a computing device, the method comprising:

generating, based on a plurality of semantic classes, a subspace formed by a first data element and a second data element, the first data element being included in a first number of semantic classes, and the second data element being included in a second number of semantic classes;

encoding by circuitry, the first data element with respect to the second data element such that the generated subspace formed by the first data element and the second data element is orthogonal, the encoding being performed by computing one of a left contraction and a right contraction of a first set that includes the first data element with respect to a second set that includes the second data element;

computing by circuitry, a weight distribution of the first data element with respect to the second data element, the weight distribution being performed for each of the first number of semantic classes with respect to the second number of semantic classes; and

determining a dominant semantic class corresponding to an ordered sequence of the first data element and the second data element, the dominant semantic class having a maximum weight distribution.

2. The method of claim 1, further comprising:

partitioning data into a plurality of semantic classes based on a dissimilarity metric.

3. The method of claim 2, wherein the partitioning further comprises:

computing the dissimilarity metric by determining a semantic distance between the first data element and the second data element, the semantic distance being induced based on a fixed distance between a top layer and a bottom layer of an ontology of the data.

4. The method of claim 1, wherein the encoding is performed for each semantic class of the first number of semantic classes relative to each semantic class of the second number of semantic classes, and wherein each semantic class of the second number of semantic classes is different than each semantic class of the first number of semantic classes.

5. The method of claim 1, wherein the encoding further comprises:

computing a first metric corresponding to the first data element being a successor of the second data element, the first metric being computed as a scalar multiple of one of the left contraction operation and the right contraction operation.

6. The method of claim 1, wherein the weight distribution of the first data element with respect to the second data element is computed as a scalar multiple of one of the left contraction operation and the right contraction operation of each of the first number of semantic classes with respect to each of the second number of semantic classes.

7. The method of claim 6, wherein the weight distribution associated with one of the left contraction operation and the right contraction operation of each of the first number of semantic classes with respect to each of the second number of semantic classes is one of a Jaccard metric, Dice coefficient metric, Hamming Distance metric, Manhattan metric, and a Cosine metric.

8. The method of claim 1, wherein the weight distribution of the first data element with respect to the second data element is based on a number of elements included in each semantic class.

9. The method of claim 2, wherein the partitioning further comprising:

generating a plurality of data clusters, each data cluster including at least one semantic class, and wherein substantially similar data elements are assigned to a data cluster.

10. The method of claim 1, wherein a number of semantic classes is one or more of data clusters, parts of speech, a language synonym set, and an ontology.

11. The method of claim 1, wherein the determining further comprises:

repeating the encoding and the computing, for the second data element being a successor of the first data element.

12. The method of claim 1, wherein the data is one of language data, medical data, and image data.

13. The method of claim 9, wherein each semantic class belonging to the data cluster corresponds to a blade in a heterogeneous space formed by the plurality of data clusters.

14. The method of claim 1, wherein each of the semantic class is assigned a unique metric, the unique metric being utilized in the computation of one of the left contraction and a right contraction operations.

15. A device for geometrically encoding data, the device comprising:

circuitry configured to

generate, based on a plurality of semantic classes, a subspace formed by a first data element and a second data element, the first data element being included in a first number of semantic classes, and the second data element being included in a second number of semantic classes;

encode the first data element with respect to the second data element such that the generated subspace formed by the first data element and the second data element is orthogonal, the encoding being performed by computing one of a left contraction and a right contraction of a first set that includes the first data element with respect to a second set that includes the second data element;

compute a weight distribution of the first data element with respect to the second data element, the weight distribution being performed for each of the first number of semantic classes with respect to the second number of semantic classes; and

determine a dominant semantic class corresponding to an ordered sequence of the first data element and the second data element, the dominant semantic class having a maximum weight distribution.

16. The device of claim 15, wherein the circuitry is further configured to partition data into a plurality of semantic classes based on a dissimilarity metric.

17. The device of claim 16, wherein the circuitry is further configured to compute the dissimilarity metric by determining a semantic distance between the first data element and the second data element, the semantic distance being induced based on a fixed distance between a top layer and a bottom layer of an ontology of the data.

18. The device of claim 15, wherein the circuitry is further configured to encode first data element by being configured to perform encoding for each semantic class of the first number of semantic classes relative to each semantic class of the second number of semantic classes, and wherein each semantic class of the second number of semantic classes is different than each semantic class of the first number of semantic classes.

19. The device of claim 15, wherein the circuitry is further configured to encode first data element by being configured to compute a first metric corresponding to the first data element being a successor of the second data element, the first metric being computed as a scalar multiple of one of the left contraction operation and the right contraction operation.

20. The device of claim 15, wherein the weight distribution of the first data element with respect to the second data element is computed as a scalar multiple of one of the left contraction operation and the right contraction operation of each of the first number of semantic classes with respect to each of the second number of semantic classes.

21. The device of claim 20, wherein the weight distribution associated with one of the left contraction operation and the right contraction operation of each of the first number of semantic classes with respect to each of the second number of semantic classes is one of a Jaccard metric, Dice coefficient metric, Hamming Distance metric, Manhattan metric, and a Cosine metric.

22. The device of claim 15, wherein the weight distribution of the first data element with respect to the second data element is based on a number of elements included in each semantic class.

23. The device of claim 16, wherein the circuitry is configured to partition the data by generating a plurality of data clusters, each data cluster including at least one semantic class, and wherein substantially similar data elements are assigned to a data cluster.

24. The device of claim 15, wherein a number of semantic classes is one or more of data clusters, parts of speech, a language synonym set, and an ontology.

25. The device of claim 15, wherein the circuitry is further configured to repeat the encoding and the computing, for the second data element being a successor of the first data element.

26. The device of claim 16, wherein the data is one of language data, medical data, and image data.

27. The device of claim 15, wherein each semantic class belonging to the data cluster corresponds to a blade in a heterogeneous space formed by the plurality of data clusters.

28. The device of claim 15, wherein each of the semantic class is assigned a unique metric, the unique metric being utilized in the computation of one of the left contraction and a right contraction operations.

29. A non-transitory computer-readable medium including computer program instructions, which when executed by a computer, cause the computer to perform a method, the method comprising:

generating, based on a plurality of partitioned semantic classes, a subspace formed by a first data element and a second data element, the first data element being included in a first number of partitioned semantic classes, and the second data element being included in a second number of partitioned semantic classes;

encoding by circuitry, the first data element with respect to the second data element such that the generated subspace formed by the first data element and the second data element is orthogonal, the encoding being performed by computing one of a left contraction and a right contraction of a first set that includes the first data element with respect to a second set that includes the second data element;

computing by circuitry, a weight distribution of the first data element with respect to the second data element, the weight distribution being performed for each of the first number of semantic classes with respect to the second number of semantic classes; and

determining a dominant semantic class corresponding to an ordered sequence of the first data element and the second data element, the dominant semantic class having a maximum weight distribution.

30. The non-transitory computer readable medium of claim 29, the method further comprising:

partitioning data into a plurality of semantic classes based on a dissimilarity metric.

31. The non-transitory computer readable medium of claim 29, wherein the partitioning further comprises:

computing the dissimilarity metric by determining a semantic distance between the first data element and the second data element, the semantic distance being induced based on a fixed distance between a top layer and a bottom layer of an ontology of the data.

32. The non-transitory computer readable medium of claim 29, wherein the encoding is performed for each semantic class of the first number of semantic classes relative to each semantic class of the second number of semantic classes, and wherein each semantic class of the second number of semantic classes is different than each semantic class of the first number of semantic classes.

33. The non-transitory computer readable medium of claim 29, wherein the encoding further comprises:

computing a first metric corresponding to the first data element being a successor of the second data element, the first metric being computed as a scalar multiple of one of the left contraction operation and the right contraction operation.

34. The non-transitory computer readable medium of claim 29, wherein the weight distribution of the first data element with respect to the second data element is computed as a scalar multiple of one of the left contraction operation and the right contraction operation of each of the first number of semantic classes with respect to each of the second number of semantic classes.

35. The non-transitory computer readable medium of claim 34, wherein the weight distribution associated with one of the left contraction operation and the right contraction operation of each of the first number of semantic classes with respect to each of the second number of semantic classes is one of a Jaccard metric, Dice coefficient metric, Hamming Distance metric, Manhattan metric, and a Cosine metric.

36. The non-transitory computer readable medium of claim 29, wherein the weight distribution of the first data element with respect to the second data element is based on a number of elements included in each semantic class.

37. The non-transitory computer readable medium of claim 30, wherein the partitioning further comprising:

generating a plurality of data clusters, each data cluster including at least one semantic class, and wherein substantially similar data elements are assigned to a data cluster.

38. The non-transitory computer readable medium of claim 37, wherein a number of semantic classes is one or more of data clusters, parts of speech, a language synonym set, and an ontology.

39. The non-transitory computer readable medium of claim 29, wherein the determining further comprises:

repeating the encoding and the computing, for the second data element being a successor of the first data element.

40. The non-transitory computer readable medium of claim 29, wherein the data is one of language data, medical data, and image data.

41. The non-transitory computer readable medium of claim 37, wherein each semantic class belonging to the data cluster corresponds to a blade in a heterogeneous space formed by the plurality of data clusters.

42. The non-transitory computer readable medium of claim 29, wherein each of the semantic class is assigned a unique metric, the unique metric being utilized in the computation of one of the left contraction and a right contraction operations.

43. A method of geometrically encoding data, the method being performed by circuitry included in a computing device, the method comprising:

generating, based on a plurality of semantic classes, a subspace formed by a first data element and a second data element, the first data element being included in a first number of semantic classes, and the second data element being included in a second number of semantic classes;

encoding by circuitry, the first data element with respect to the second data element such that the generated subspace formed by the first data element and the second data element is orthogonal, the encoding being performed by computing one of a left contraction and a right contraction of a first set that includes the first data element with respect to a second set that includes the second data element;

computing by circuitry, a weight distribution of the first data element with respect to the second data element, the weight distribution being performed for each of the first number of semantic classes with respect to the second number of semantic classes; and

indexing by circuitry, the encoded subspaces based on the computed weight distributions.

44. A method of geometrically encoding data, the method being performed by circuitry included in a computing device, the method comprising:

generating, based on a plurality of semantic classes, a subspace formed by a first data element and a second data element, the first data element being included in a first number of semantic classes, and the second data element being included in a second number of semantic classes;

encoding by circuitry, the first data element with respect to the second data element such that the generated subspace formed by the first data element and the second data element is orthogonal, the encoding being performed by computing one of a left contraction and a right contraction of a first set that includes the first data element with respect to a second set that includes the second data element;

computing by circuitry, a weight distribution of the first data element with respect to the second data element, the weight distribution being performed for each of the first number of semantic classes with respect to the second number of semantic classes; and

selecting by circuitry, a subspace from the encoded subspaces based on the computed weight distributions.

45. A method of geometrically encoding data, the method being performed by circuitry included in a computing device, the method comprising:

generating, based on a plurality of semantic classes, a subspace formed by a first data element and a second data element, the first data element being included in a first number of semantic classes, and the second data element being included in a second number of semantic classes;

encoding by circuitry, the first data element with respect to the second data element such that the generated subspace formed by the first data element and the second data element is orthogonal, the encoding being performed by computing one of a left contraction and a right contraction of a first set that includes the first data element with respect to a second set that includes the second data element;

computing by circuitry, a weight distribution of the first data element with respect to the second data element, the weight distribution being performed for each of the first number of semantic classes with respect to the second number of semantic classes; and

translating by circuitry, the encoded subspaces based on the computed weight distributions.