Plus, The row URLs and anchor family of webTable that mentioned in BigTable paper is same with above structure. It's the web-link graph which is represented as an adjacency matrix.
On Wed, Apr 1, 2009 at 5:33 PM, Edward J. Yoon <[email protected]> wrote: > Let's assume the graph looks like presented below: > > 1 - 2 - 3 > | / > 4 > > We can now represent as: > > | 1 2 3 4 > --+---------- > 1 | 0 1 0 1 > 2 | 1 0 1 1 > 3 | 0 1 0 0 > 4 | 1 0 1 0 > > We don't need to store the zeros, Hbase is ideal in storing sparse > matrices. So, It can be simply implemented using Hbase APIs as > describe below. > > public class Graph { > ... > > public void addEdge(String v, String w) { > BatchUpdate update = new BatchUpdate(v); > update.put(w, 1); > table.commit(update); > > update = new BatchUpdate(w); > update.put(v, 1); > table.commit(update); > } > > ... > public static void main(String[] args) { > Graph graph = new Graph(); > graph.addEdge("1", "2"); > > graph.addEdge("1", "4"); > > graph.addEdge("2", "3"); > > graph.addEdge("2", "4"); > > graph.addEdge("4", "1"); > > graph.addEdge("4", "3"); > } > } > > On Wed, Apr 1, 2009 at 4:47 PM, Amandeep Khurana <[email protected]> wrote: >> Right. >> >> Edward, I didnt understand what you were trying to say with this: >> >> Anyway, I guess If you store the graph like that, you'll only need update >> the row 'v/w' to add v to w's/w to v's list of neighbors. >> >> Can you explain it please? >> >> Thanks >> Amandeep >> >> Amandeep Khurana >> Computer Science Graduate Student >> University of California, Santa Cruz >> >> >> On Tue, Mar 31, 2009 at 8:02 PM, Edward J. Yoon <[email protected]>wrote: >> >>> One thing is Hbase 0.19 doesn't work with over 5,000 qualifier of one >>> column so I couldn't test/benchmark for large scale. >>> >>> On Tue, Mar 31, 2009 at 6:04 PM, Amandeep Khurana <[email protected]> >>> wrote: >>> > Response below >>> > >>> > >>> > Amandeep Khurana >>> > Computer Science Graduate Student >>> > University of California, Santa Cruz >>> > >>> > >>> > On Tue, Mar 31, 2009 at 1:58 AM, Edward J. Yoon <[email protected] >>> >wrote: >>> > >>> >> Hama store the sparse graph using Hbase as an sparse adjacency matrix. >>> >> One of reason is to perform matrix decomposition for large sparse >>> >> graphs. Anyway, I guess If you store the graph like that, you'll only >>> >> need update the row 'v/w' to add v to w's/w to v's list of neighbors. >>> > >>> > >>> > I didnt quite understand the last line here. >>> > >>> > I did think of a sparse matrix as well but not sure which is a better >>> > approach. Thats why I posted here... >>> > >>> > Share about your experiences with Hama... >>> > >>> >> >>> >> >>> >> Just FYI, You also may want to see -- >>> >> http://blog.udanax.org/2009/02/breadth-first-search-mapreduce.html >>> >> >>> >> If you have any advice for us, Pls let us know. >>> >> >>> >> On Tue, Mar 31, 2009 at 5:09 PM, Amandeep Khurana <[email protected]> >>> >> wrote: >>> >> > What would be a good schema in HBase to store information pertaining >>> to a >>> >> > many to many graph? I was thinking of having the node id as the row >>> key, >>> >> the >>> >> > type of relation as the column family, the relation name for the >>> column >>> >> > identifier and the actual cell containing the key of the node that is >>> >> being >>> >> > connected with. >>> >> > >>> >> > >>> >> > Amandeep Khurana >>> >> > Computer Science Graduate Student >>> >> > University of California, Santa Cruz >>> >> > >>> >> >>> >> >>> >> >>> >> -- >>> >> Best Regards, Edward J. Yoon >>> >> [email protected] >>> >> http://blog.udanax.org >>> >> >>> > >>> >>> >>> >>> -- >>> Best Regards, Edward J. Yoon >>> [email protected] >>> http://blog.udanax.org >>> >> > > > > -- > Best Regards, Edward J. Yoon > [email protected] > http://blog.udanax.org > -- Best Regards, Edward J. Yoon [email protected] http://blog.udanax.org
