MEASURING SEMANTIC AND SYNTACTIC SIMILARITY BETWEEN GRAMMARS ACCORDING TO DISTANCE METRICS FOR CLUSTERED DATA

• US 20160224652A1
• Filed: 01/30/2015
• Published: 08/04/2016
• Est. Priority Date: 01/30/2015
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: SCHWARTZ, Adam, GUEDALIA, Isaac David
• Granted Patent: US 10,037,374 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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:

constructing at least a first grammar associated with a first device and a second grammar associated with a second device, wherein the first grammar and the second grammar 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;

calculating one or more distance metrics that quantify a similarity between the first grammar and the second grammar according to a comparison between the one or more rules in the first grammar and the one or more rules in the second grammar; and

determining 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 constructing at least a first grammar associated with a first device and a second grammar associated with a second device, wherein the first grammar and the second grammar 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;

means for comparing the one or more rules in the first grammar and the one or more rules in 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:

construct at least a first grammar associated with a first device and a second grammar associated with a second device, wherein the first grammar and the second grammar 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;

calculate one or more distance metrics that quantify a similarity between the first grammar and the second grammar according to a comparison between the one or more rules in the first grammar and the one or more rules in 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.