tinkerpop-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Marc de Lignie (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (TINKERPOP-1967) Add a connectedComponent() step
Date Wed, 06 Jun 2018 19:57:00 GMT

    [ https://issues.apache.org/jira/browse/TINKERPOP-1967?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16503837#comment-16503837
] 

Marc de Lignie commented on TINKERPOP-1967:
-------------------------------------------

The comparison between the OLTP query and the connectedComponent step was more productive.
Below you see figures for graphs with random components of fixed size with a edge/vertex ratio
of 6, for which the two algorithms have the same order of magnitude runtime. This means the
OLTP query could still be useful for networks with long strings of vertices. So, I will do
some more work to produce some comparison graphs, add them to my work and rework them into
a PR against TTINKERPOP-1967.

OLTP: Duration: 0.064
Component sizes: [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]
Step: Duration: 0.052
Component sizes: [100, 100, 100, 100, 100, 100, 100, 100, 100, 100]
OLTP: Duration: 0.134
Component sizes: [200, 200, 200, 200, 200, 200, 200, 200, 200, 200]
Step: Duration: 0.096
Component sizes: [200, 200, 200, 200, 200, 200, 200, 200, 200, 200]
OLTP: Duration: 0.269
Component sizes: [400, 400, 400, 400, 400, 400, 400, 400, 400, 400]
Step: Duration: 0.129
Component sizes: [400, 400, 400, 400, 400, 400, 400, 400, 400, 400]
OLTP: Duration: 0.585
Component sizes: [800, 800, 800, 800, 800, 800, 800, 800, 800, 800]
Step: Duration: 0.252
Component sizes: [800, 800, 800, 800, 800, 800, 800, 800, 800, 800]
OLTP: Duration: 1.183
Component sizes: [1600, 1600, 1600, 1600, 1600, 1600, 1600, 1600, 1600, 1600]
Step: Duration: 0.559
Component sizes: [1600, 1600, 1600, 1600, 1600, 1600, 1600, 1600, 1600, 1600]
OLTP: Duration: 2.375
Component sizes: [3200, 3200, 3200, 3200, 3200, 3200, 3200, 3200, 3200, 3200]
Step: Duration: 1.125
Component sizes: [3200, 3200, 3200, 3200, 3200, 3200, 3200, 3200, 3200, 3200]
OLTP: Duration: 4.986
Component sizes: [6400, 6400, 6400, 6400, 6400, 6400, 6400, 6400, 6400, 6400]
Step: Duration: 2.326
Component sizes: [6400, 6400, 6400, 6400, 6400, 6400, 6400, 6400, 6400, 6400]
OLTP: Duration: 10.507
Component sizes: [12800, 12800, 12800, 12800, 12800, 12800, 12800, 12800, 12800, 12800]
Step: Duration: 6.308
Component sizes: [12800, 12800, 12800, 12800, 12800, 12800, 12800, 12800, 12800, 12800]
OLTP: Duration: 22.265
Component sizes: [25600, 25600, 25600, 25600, 25600, 25600, 25600, 25600, 25600, 25600]
Step: Duration: 16.212
Component sizes: [25600, 25600, 25600, 25600, 25600, 25600, 25600, 25600, 25600, 25600]

> Add a connectedComponent() step
> -------------------------------
>
>                 Key: TINKERPOP-1967
>                 URL: https://issues.apache.org/jira/browse/TINKERPOP-1967
>             Project: TinkerPop
>          Issue Type: Improvement
>          Components: process
>    Affects Versions: 3.3.3
>            Reporter: stephen mallette
>            Assignee: stephen mallette
>            Priority: Minor
>             Fix For: 3.4.0
>
>
> Given TINKERPOP-1852 we should probably just simplify and improve performance of connected
component identification. Implementing this will involved the creation of {{ConnectedComponentVertexProgram}}.



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

Mime
View raw message