flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Greg Hogan (JIRA)" <j...@apache.org>
Subject [jira] [Closed] (FLINK-3925) GraphAlgorithm to filter by maximum degree
Date Tue, 07 Jun 2016 15:00:24 GMT

     [ https://issues.apache.org/jira/browse/FLINK-3925?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Greg Hogan closed FLINK-3925.
-----------------------------
    Resolution: Implemented

Implemented in a611271b3ef7a084ec8e7edc4d4dc241550d7ad8

> 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
>             Fix For: 1.1.0
>
>
> 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