[FLINK-3780] Jaccard Similarity

• Type: New Feature
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 1.1.0
• Fix Version/s: 1.1.0
• Component/s: Library / Graph Processing
• Assignee: Greg Hogan
• Reporter: Greg Hogan
• Created: 18/Apr/16 16:48
• Updated: 20/May/16 20:30
• Resolved: 20/May/16 20:30

Description

Implement a Jaccard Similarity algorithm computing all non-zero similarity scores. This algorithm is similar to TriangleListing but instead of joining two-paths against an edge list we count two-paths.

flink-gelly-examples currently has JaccardSimilarityMeasure which relies on Graph.getTriplets() so only computes similarity scores for neighbors but not neighbors-of-neighbors.

This algorithm is easily modified for other similarity scores such as Adamic-Adar similarity where the sum of endpoint degrees is replaced by the degree of the middle vertex.

Issue Links

• depends upon: FLINK-3771 Methods for translating Graphs
• depends upon: FLINK-3772 Graph algorithms for vertex and edge degree
• links to: GitHub Pull Request #1980