Mailing-List: contact user-help@giraph.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@giraph.apache.org
Received-SPF: pass (athena.apache.org: domain of thschweiger@ebay.com
 designates 216.113.175.152 as permitted sender)
DomainKey-Signature: s=ebaycorp; d=ebay.com; c=nofws; q=dns;
  h=X-EBay-Corp:X-IronPort-AV:Received:Received:From:To:
   Subject:Thread-Topic:Thread-Index:Date:Message-ID:
   References:In-Reply-To:Accept-Language:Content-Language:
   X-MS-Has-Attach:X-MS-TNEF-Correlator:x-originating-ip:
   Content-Type:MIME-Version:X-CFilter;
  b=MvsvZ06PboGrgp28OFwTpBtQWSldVXUneycMXZH1uUWVKxXhtnTYY4r/
   PtPOdDmA7etjq18bVbAdfeO2vHYTnsNwyheez9HrtXsX5ANCf8Xxae5r3
   uUMMq3UdhR4/xiC+rO7+fNxscvxUEs9zEdCSffLacW9eiyJfyIhVPEguF
   Q=;
From: "Schweiger, Tom" <thschweiger@ebay.com>
To: "user@giraph.apache.org" <user@giraph.apache.org>
Subject: RE: Generating unique vertex id's for addVertexRequest
Thread-Topic: Generating unique vertex id's for addVertexRequest
Thread-Index: AQHPqxXliF2k2681C02QNcutU42wDZu3PN1h
Date: Tue, 29 Jul 2014 16:34:28 +0000
Message-ID: 
 <9B590560869E3741B7665052119D024225F412@DEN-EXDDA-S51.corp.ebay.com>
References: 
 <CAC7_g15e+RSSQfkYbRR39T7W+PU52=0pPnS9ZodtpR973XkPJA@mail.gmail.com>
In-Reply-To: 
 <CAC7_g15e+RSSQfkYbRR39T7W+PU52=0pPnS9ZodtpR973XkPJA@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
Content-Type: multipart/alternative;
	boundary="_000_9B590560869E3741B7665052119D024225F412DENEXDDAS51corpeb_"
MIME-Version: 1.0

--_000_9B590560869E3741B7665052119D024225F412DENEXDDAS51corpeb_
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable


With any generated ID like a hash, there will always be the possibility of =
a collision (different ids creating the same generated id).  However, becau=
se you are using a long, the size of the hash space is quite large.  a coll=
ision won't become likely until you have around 4 billion vertexes.  If you=
r graph has, say, 10 million vertexes, you can be 99.97% sure there are no =
collisions.  Put another way, you would have to generate  3700 graphs. each=
 with 10 million vertexes, before you got one with a single collision.

Your other options are:

* Manage your ids, using a cross-reference table, so that you guarantee a o=
ne-to-one relationship between the id and the long.

* Change the classes you are using in Giraph to use Text instead of Long fo=
r the vertex ids.


________________________________
From: Panagiotis Eustratiadis [ep.pan.dit@gmail.com]
Sent: Tuesday, July 29, 2014 3:14 AM
To: user@giraph.apache.org
Subject: Generating unique vertex id's for addVertexRequest

Hello everyone,

I'm looking for a way to generate unique id's (of type Long) for the addVer=
texRequest. For example, a very silly implementation that works for graphs =
with less than 100 vertices would look like this:

public void compute(Iterable<NullWritable> messages) {
...
    long generatedId =3D generateId(long getId().get());
    addVertexRequest(new LongWritable(generatedId), new DoubleWritable(0));
...
}

private long generateId(long seed) {
    return seed + 100;
}

But as I said, this is just silly. How can I modify the generateId so that =
I know the vertex id is unique regardless of the graph size?

Panagiotis Eustratiadis.

--_000_9B590560869E3741B7665052119D024225F412DENEXDDAS51corpeb_
Content-Type: text/html; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

<html dir=3D"ltr">
<head>
<meta http-equiv=3D"Content-Type" content=3D"text/html; charset=3Diso-8859-=
1">
<style id=3D"owaParaStyle" type=3D"text/css">P {margin-top:0;margin-bottom:=
0;}</style>
</head>
<body ocsi=3D"0" fpstyle=3D"1">
<div style=3D"direction: ltr;font-family: Tahoma;color: #000000;font-size: =
10pt;"><br>
With any generated ID like a hash, there will always be the possibility of =
a collision (different ids creating the same generated id).&nbsp; However, =
because you are using a long, the size of the hash space is quite large.&nb=
sp; a collision won't become likely until
 you have around 4 billion vertexes.&nbsp; If your graph has, say, 10 milli=
on vertexes, you can be 99.97% sure there are no collisions.&nbsp; Put anot=
her way, you would have to generate&nbsp; 3700 graphs. each with 10 million=
 vertexes, before you got one with a single collision.<br>
<br>
Your other options are:<br>
<br>
* Manage your ids, using a cross-reference table, so that you guarantee a o=
ne-to-one relationship between the id and the long.<br>
<br>
* Change the classes you are using in Giraph to use Text instead of Long fo=
r the vertex ids.<br>
<br>
<br>
<div style=3D"font-family: Times New Roman; color: #000000; font-size: 16px=
">
<hr tabindex=3D"-1">
<div style=3D"direction: ltr;" id=3D"divRpF517171"><font color=3D"#000000" =
face=3D"Tahoma" size=3D"2"><b>From:</b> Panagiotis Eustratiadis [ep.pan.dit=
@gmail.com]<br>
<b>Sent:</b> Tuesday, July 29, 2014 3:14 AM<br>
<b>To:</b> user@giraph.apache.org<br>
<b>Subject:</b> Generating unique vertex id's for addVertexRequest<br>
</font><br>
</div>
<div></div>
<div>
<div dir=3D"ltr">
<div>
<div>
<div>
<div>
<div>Hello everyone,<br>
<br>
</div>
I'm looking for a way to generate unique id's (of type Long) for the addVer=
texRequest. For example, a very silly implementation that works for graphs =
with less than 100 vertices would look like this:<br>
<br>
</div>
<div>public void compute(Iterable&lt;NullWritable&gt; messages) {<br>
</div>
<div>...<br>
</div>
&nbsp;&nbsp;&nbsp; long generatedId =3D generateId(long getId().get());<br>
</div>
&nbsp;&nbsp;&nbsp; addVertexRequest(new LongWritable(generatedId), new Doub=
leWritable(0));<br>
...<br>
}<br>
<br>
</div>
private long generateId(long seed) {<br>
</div>
&nbsp;&nbsp;&nbsp; return seed &#43; 100;<br>
<div>}<br>
<br>
</div>
<div>But as I said, this is just silly. How can I modify the generateId so =
that I know the vertex id is unique regardless of the graph size?<br>
<br>
</div>
<div>Panagiotis Eustratiadis.<br>
</div>
</div>
</div>
</div>
</div>
</body>
</html>

--_000_9B590560869E3741B7665052119D024225F412DENEXDDAS51corpeb_--