flink-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Greg Hogan (JIRA)" <j...@apache.org>
Subject [jira] [Created] (FLINK-3925) GraphAlgorithm to filter by maximum degree
Date Wed, 18 May 2016 15:28:12 GMT
Greg Hogan created FLINK-3925:
---------------------------------

             Summary: GraphAlgorithm to filter by maximum degree
                 Key: FLINK-3925
                 URL: https://issues.apache.org/jira/browse/FLINK-3925
             Project: Flink
          Issue Type: New Feature
          Components: Gelly
    Affects Versions: 1.1.0
            Reporter: Greg Hogan
            Assignee: Greg Hogan
            Priority: Minor


Filtering by minimum degree is K-Core which is iterative. Filtering by maximum degree can
be performed in constant time by filtering the set of high-degree vertices then doing an anti-join
against the original vertex set and two anti-joins against the original edge set.

Two reasons to remove high-degree vertices: 1) they may simply be noise in the input data,
and 2) speedup algorithms such as Adamic-Adar and Jaccard Index which run quadratic in the
vertex degree.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message