Measuring semantic and syntactic similarity between grammars according to distance metrics for clustered data

• US 10,037,374 B2
• Filed: 01/30/2015
• Issued: 07/31/2018
• Est. Priority Date: 01/30/2015
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Schwartz, Adam, Guedalia, Isaac David
• Primary Examiner(s): Nguyen, Phong H
• Application Number:
  US14/610,345
• Publication Number:
  US 20160224652A1
• Time in Patent Office: 1,278 Days
• Field of Search: 707738
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/288 Entity relationship models
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06V 10/424 Syntactic representation, e.g. by using alphabets or grammars

Abstract

The disclosure relates to various distance metrics that may quantify semantic and syntactic relationships between devices. More particularly, a first grammar associated with a first device and a second grammar associated with a second device may each comprise a symbol sequence that re-expresses one or more sequenced data items and one or more rules that represent a repeated pattern in the symbol sequence. Accordingly, one or more distance metrics that quantify a similarity between the first grammar and the second grammar may be calculated according to a comparison between the rules in the first grammar and the rules in the second grammar such that a relationship between the first device and the second device can be determined according to the one or more distance metrics.

Claims

1. A method for measuring similarity between clustered data grammars, comprising:

receiving, at an apparatus having one or more processors, at least a first data stream from a first device and a second data stream from a second device, wherein the first data stream and the second data stream each include one or more sequenced data items;

constructing, by the one or more processors, at least a first grammar associated with the first device and a second grammar associated with the second device, wherein the first grammar and the second grammar each comprise a symbol sequence that re-expresses the one or more sequenced data items in the respective data streams received from the first device and the second device;

calculating, by the one or more processors, one or more distance metrics that quantify a similarity between the first grammar and the second grammar according to a comparison between one or more rules that represent a repeated pattern in the symbol sequence associated with the first grammar and one or more rules that represent a repeated pattern in the symbol sequence associated with the second grammar; and

determining, by the one or more processors, a relationship between the first device and the second device according to the one or more distance metrics.

2. The method recited in claim 1, wherein the one or more distance metrics include at least one distance metric that quantifies a syntactic similarity between the first grammar and the second grammar.

3. The method recited in claim 2, wherein calculating the at least one distance metric that quantifies the syntactic similarity between the first grammar and the second grammar comprises comparing total rule counts in the first grammar and the second grammar.

4. The method recited in claim 2, wherein calculating the at least one distance metric that quantifies the syntactic similarity between the first grammar and the second grammar comprises comparing average rule lengths in the first grammar and the second grammar.

5. The method recited in claim 2, wherein calculating the at least one distance metric that quantifies the syntactic similarity between the first grammar and the second grammar comprises comparing total rule counts in the first grammar and the second grammar that have an equal length.

6. The method recited in claim 1, wherein the one or more distance metrics include at least one distance metric that quantifies a semantic similarity between individual rules in the first grammar and individual rules in the second grammar.

7. The method recited in claim 6, wherein calculating the at least one distance metric that quantifies the semantic similarity between the individual rules in the first grammar and the individual rules in the second grammar comprises calculating a normalized Hamming distance between the individual rules in the first grammar and the individual rules in the second grammar that have an equal length.

8. The method recited in claim 6, wherein calculating the at least one distance metric that quantifies the semantic similarity between the individual rules in the first grammar and the individual rules in the second grammar comprises:

identifying a rule pair that comprises a first rule in the first grammar and a second rule in the second grammar having a minimum difference in length; and

calculating a normalized Levenshtein distance between the first rule in the first grammar and the second rule in the second grammar.

9. The method recited in claim 1, wherein the one or more distance metrics include an integer score that indicates a nesting level associated with the one or more rules in the first grammar and the one or more rules in the second grammar.

10. The method recited in claim 1, wherein the one or more distance metrics include a binary classification that indicates whether the first grammar and the second grammar are context-free or contextual according to whether one or more symbols that surround the one or more rules in the symbol sequence associated with the first grammar and the second grammar influence the one or more surrounded rules.

11. The method recited in claim 1, further comprising:

summing the one or more calculated distance metrics; and

calculating a net distance that quantifies the similarity between the first grammar and the second grammar, wherein calculating the net distance comprises normalizing the one or more summed distance metrics according to how many distance metrics are included among the summed distance metrics.

12. The method recited in claim 11, wherein calculating the net distance further comprises assigning weights to one or more of the summed distance metrics.

13. An apparatus for measuring similarity between clustered data grammars, comprising:

means for receiving at least a first data stream from a first device and a second data stream from a second device, wherein the first data stream and the second data stream each include one or more sequenced data items;

means for constructing at least a first grammar associated with the first device and a second grammar associated with the second device, wherein the first grammar and the second grammar each comprise a symbol sequence that re-expresses the one or more sequenced data items in the respective data streams received from the first device and the second device;

means for comparing one or more rules that represent a repeated pattern in the symbol sequence associated with the first grammar and one or more rules that represent a repeated pattern in the symbol sequence associated with the second grammar to calculate one or more distance metrics that quantify a similarity between the first grammar and the second grammar; and

means for determining a relationship between the first device and the second device according to the one or more distance metrics.

14. The apparatus recited in claim 13, wherein the one or more distance metrics include at least one distance metric that quantifies a syntactic similarity between the first grammar and the second grammar.

15. The apparatus recited in claim 14, further comprising:

means for calculating the at least one distance metric that quantifies the syntactic similarity between the first grammar and the second grammar according to a comparison between total rule counts in the first grammar and the second grammar.

16. The apparatus recited in claim 14, further comprising:

means for calculating the at least one distance metric that quantifies the syntactic similarity between the first grammar and the second grammar according to a comparison between average rule lengths in the first grammar and the second grammar.

17. The apparatus recited in claim 14, further comprising:

means for calculating the at least one distance metric that quantifies the syntactic similarity between the first grammar and the second grammar comprises according to a comparison between total rule counts in the first grammar and the second grammar that have an equal length.

18. The apparatus recited in claim 13, wherein the one or more distance metrics include at least one distance metric that quantifies a semantic similarity between individual rules in the first grammar and individual rules in the second grammar.

19. The apparatus recited in claim 18, further comprising:

means for calculating the at least one distance metric that quantifies the semantic similarity between the individual rules in the first grammar and the individual rules in the second grammar according to a normalized Hamming distance between the individual rules in the first grammar and the individual rules in the second grammar that have an equal length.

20. The apparatus recited in claim 18, further comprising:

means for calculating the at least one distance metric that quantifies the semantic similarity between the individual rules in the first grammar and the individual rules in the second grammar according to a normalized Levenshtein distance between a first rule in the first grammar and a second rule in the second grammar that have a minimum difference in length.

21. The apparatus recited in claim 13, wherein the one or more distance metrics include an integer score that indicates a nesting level associated with the one or more rules in the first grammar and the one or more rules in the second grammar.

22. The apparatus recited in claim 13, wherein the one or more distance metrics include a binary classification that indicates whether the first grammar and the second grammar are context-free or contextual according to whether one or more symbols that surround the one or more rules in the symbol sequence associated with the first grammar and the second grammar influence the one or more surrounded rules.

23. The apparatus recited in claim 13, further comprising:

means for summing the one or more calculated distance metrics; and

means for calculating a net distance that quantifies the similarity between the first grammar and the second grammar, wherein the calculated the net distance normalizes the one or more summed distance metrics according to how many distance metrics are included among the summed distance metrics.

24. The apparatus recited in claim 23, wherein the means for calculating the net distance further comprises means for assigning weights to one or more of the summed distance metrics.

25. An apparatus, comprising:

one or more network access ports configured to receive at least a first data stream from a first device and a second data stream from a second device, wherein the first data stream and the second data stream each include one or more sequenced data items;

one or more processors configured to;

construct a first grammar associated with the first device and a second grammar associated with the second device, wherein the first grammar and the second grammar each comprise a symbol sequence that re-expresses the one or more sequenced data items in the respective data streams received from the first device and the second device;

calculate one or more distance metrics that quantify a similarity between the first grammar and the second grammar according to a comparison between one or more rules that represent a repeated pattern in the symbol sequence associated with the first grammar and one or more rules that represent a repeated pattern in the symbol sequence associated with the second grammar; and

determine a relationship between the first device and the second device according to the one or more distance metrics.

26. The apparatus recited in claim 25, wherein the one or more distance metrics include at least one distance metric that quantifies a syntactic similarity between the first grammar and the second grammar.

27. The apparatus recited in claim 25, wherein the one or more distance metrics include at least one distance metric that quantifies a semantic similarity between individual rules in the first grammar and the second grammar.

28. A computer-readable storage medium having computer-executable instructions recorded thereon, wherein executing the computer-executable instructions on one or more processors causes the one or more processors to:

receive at least a first data stream from a first device and a second data stream from a second device, wherein the first data stream and the second data stream each include one or more sequenced data items;

construct at least a first grammar associated with the first device and a second grammar associated with the second device, wherein the first grammar and the second grammar each comprise a symbol sequence that re-expresses the one or more sequenced data items in the respective data streams received from the first device and the second device;

calculate one or more distance metrics that quantify a similarity between the first grammar and the second grammar according to a comparison between one or more rules that represent a repeated pattern in the symbol sequence associated with the first grammar and one or more rules that represent a repeated pattern in the symbol sequence associated with the second grammar; and

determine a relationship between the first device and the second device according to the one or more distance metrics.

29. The computer-readable storage medium recited in claim 28, wherein the one or more distance metrics include at least one distance metric that quantifies a syntactic similarity between the first grammar and the second grammar.

30. The computer-readable storage medium recited in claim 28, wherein the one or more distance metrics include at least one distance metric that quantifies a semantic similarity between individual rules in the first grammar and the second grammar.