Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Graph Databases 101

cray.com

Post reply on HN
Print view View original

91–100 of 107 posts

Re: Graph Databases 101

#91

Post by rspeer »

grandalf wrote: post #83
rspeer wrote: post #63

Earlier quoted context omitted.

ConceptNet [1] started out as an academic project that I was responsible for for a while. Since then I've left to start a company but I still maintain ConceptNet and build lots of stuff on it. [1] http://conceptnet5.media.mit.edu Here's a list of databases, some of them graph databases, some of them barely databases, where I've tried to store and look up edges of ConceptNet: - SQLite - PostgreSQL - MongoDB - Some awf…

It's interesting. I suppose most graph db operations could be easily enough broken down into a series of steps that could be performed in a more scalable but slower way. Did your hand-rolled hashtable have any characteristics that would make its performance characteristics difficult for a smarter optimizer (if such a thing existed in Neo4j)? Can you psudocode an example slow query/operation and indicate how many edge…

The failures of these databases were a lot more fundamental than I think you're looking for. And so far it hasn't been a trade-off where a non-graph DB has been more scalable but slower; instead, non-graph DBs have been more scalable and faster.

Here's what I have to be able to do in the database:

1. Import millions of edges from a flat file (time limit: 24 hours)

2. Query any node to return up to 100 edges connected to it (time limit: 100 milliseconds)

3. (nice to have) Find the maximal core of nodes that all have degree at least n to each other (time limit: a few hours)

4. Iterate all the edges between the nodes in a specified subset, such as the degree-3 core, which may still be millions of edges (time limit: a few hours)

#3 is optional, and the alternative is to export all the edges and compute it outside the database. But it's the only thing here that's actually a graph algorithm. However, every open-source graph database I've tried is orders of magnitude too slow at one of the other steps. They either fail at importing, fail at iterating, or fail to respond to trivial queries in a timely manner.

I forgot to mention one other non-graph-database system that met my requirements, which is Kyoto Cabinet. The main downside of it is the GPLv3 license.

Re: Graph Databases 101

#92

Post by espeed »

rspeer wrote: post #63
grandalf wrote: post #61

Earlier quoted context omitted.

Explain

ConceptNet [1] started out as an academic project that I was responsible for for a while. Since then I've left to start a company but I still maintain ConceptNet and build lots of stuff on it. [1] http://conceptnet5.media.mit.edu Here's a list of databases, some of them graph databases, some of them barely databases, where I've tried to store and look up edges of ConceptNet: - SQLite - PostgreSQL - MongoDB - Some awf…

Graph DB technology has been advancing fast over the last few years, and more evolutions are coming down the pipe. For example, Titan and Blazegraph are distributed and can handle billions of edges, and Blazegraph can be GPU-accelerated, which "demonstrated a throughput of 32 Billion Traversed Edges Per Second (32 GTEPS), traversing a scale-free graph of 4.3 billion directed edges in 0.15 seconds" (https://www.blazegraph.com/product/gpu-accelerated/).

NB: TinkePop is not a graph DB -- it's a graph software stack / computing framework for graph DBs (OLTP) and graph analytic systems (OLAP). Since TinkerPop is integrated with almost all of the graph DBs and graph processing engines, its mailing lists are good place to discuss and get help with graph-related projects.

[1] http://tinkerpop.incubator.apache.org/

[2] TinkerPop / Gremlin Users Mailing List http://groups.google.com/group/gremlin-users

[3] TinkerPop Developer Mailing List http://mail-archives.apache.org/mod_mbox/incubator-tinkerpop...

Re: Graph Databases 101

#93

Post by tkinom »

sophacles wrote: post #89
tkinom wrote: post #77

Earlier quoted context omitted.

Facebook has a very good paper descriptions on how they do graph on top of relational database. Google "facebook tao" for details. I read that and implement my own version with SQL in I am curious what I might be missing with that approach as compare to a real graph database?

From my quick read of tao, it seems to be doing essentially what graph databases do but with the data storage layer being in sql rather than some other object store. And with the interface layer being not quite as feature complete. So the query layer in tao seems to lack a way to follow multiple edges without first returning to the application code, which graph dbs present as a native feature. The other thing that's…

I implemented a table for Nodes, one for Edges. The Nodes table has an entry for JSON for that Nodes.

If I need more info for particular "Edge type", I just add new Node entry type "Edge_info" that link the Edge type to a JSON that content such info. I found that very flexible, but I have not used any real graph database.

Re: Graph Databases 101

#94

Post by rspeer »

espeed wrote: post #92
rspeer wrote: post #63

Earlier quoted context omitted.

ConceptNet [1] started out as an academic project that I was responsible for for a while. Since then I've left to start a company but I still maintain ConceptNet and build lots of stuff on it. [1] http://conceptnet5.media.mit.edu Here's a list of databases, some of them graph databases, some of them barely databases, where I've tried to store and look up edges of ConceptNet: - SQLite - PostgreSQL - MongoDB - Some awf…

Graph DB technology has been advancing fast over the last few years, and more evolutions are coming down the pipe. For example, Titan and Blazegraph are distributed and can handle billions of edges, and Blazegraph can be GPU-accelerated, which "demonstrated a throughput of 32 Billion Traversed Edges Per Second (32 GTEPS), traversing a scale-free graph of 4.3 billion directed edges in 0.15 seconds" ( https://www.blaze…

I like how at least the BlazeGraph people are talking about billions of edges and not thousands, but I'm not sure that's something I could use. That seems to be a "pre-order" page, so it sounds neither open source nor existent. And I'm trying to figure out what their normal non-GPU non-distributed software is, but it seems to mostly be a pile of Javadocs.

Using distributed computing on mere gigabytes of data is silly.

I think TinkerPop was something else back in 2011, but apologies if I've used the wrong terminology.

Re: Graph Databases 101

#95

Post by polymeris »

sophacles wrote: post #58
thesz wrote: post #29

It introduces false dichotomy "graph vs relational". In fact, most (if not all) graph algorithms can be expressed using linear algebra (with specific addition and multiplication). And matrix multiplication is a select from two matrices, related with "where i=j" and aggregation over identical result coordinates. The selection of multiplication and addition operations can account for different "data stored in links and…

Strictly speaking yeah. Practically speaking: Not really true. Just because something can be done, doesn't mean it can be done easily or well. I've done a lot of work with relational databases, and I love them for a lot of data sets. But I also have done a lot of work with graph databases - and they make working with graph shaped data a pleasure. I could do a graph in SQL, it's even moderately straight-forward in pos…

Curious, since you seem to have experience with both graph and relational databases (and I have not really worked much with the former)... if I had a graph where I just want to compute the shortest weighted path between two nodes, which model would suit better and how much difference would it make in terms of performance?

Re: Graph Databases 101

#96

Post by mitchty »

fulafel wrote: post #65
mitchty wrote: post #48

Earlier quoted context omitted.

I'm not clear how Sun ever owned Cray care to explain? The provenance was Cray Research -> SGI -> Tera/Cray according to those that have been around since the Cray Research days. Source: err, I work here and asked a couple people a few cubes over. :) The Sun deal was apparently more SGI wouldn't be caught dead with a supercomputer that ran on sparc so it got sold off to Sun.

My bad about Sun. Yep, Sun just bought the SPARC-based stuff & developed further under their own brand (E10k etc).

No worries, just thought i'd clarify.

Re: Graph Databases 101

#97

Post by GFK_of_xmaspast »

valhalla wrote: post #67

If anyone's curious about Network Science/Graph Theory in general here's a free online textbook used by a grad student friend of mine http://barabasilab.neu.edu/networksciencebook/downlPDF.html

Be careful about Barabasi: https://liorpachter.wordpress.com/2014/02/10/the-network-non...

(FWIW, I had previously read some Barabasi papers and had come away seriously unimpressed, see also https://news.ycombinator.com/item?id=9555547)

Re: Graph Databases 101

#98

Post by thesz »

sklogic wrote: post #72
thesz wrote: post #59

Earlier quoted context omitted.

I beg to disagree. I am part of the team developing Russian CAD system [0]. It uses what one can consider a hypergraph db (relation includes many objects), but that DBMS system has queries on par with SQL. And they prove themselves very useful in development of CAD. What you describe can be explained with development inertia. Most CADs are C/C++ and these languages are not very well suited for changes that go through…

I worked on a (very old) ship-building and factory-building CAD, written mostly in PL/I and Fortran. It was built around a graph database. Throughout its long and turbulent history, there were many attempts of moving to a relational storage, every time resulting in orders of magnitude drop in performance. Keep in mind that in such a CAD designs are huge . Think of an aircraft carrier scale of "huge". And it was desig…

Had the state of art changed from the time of their last attempt to move to relational DB? Had the hardware changed during that time?

You tell us about some old project, written in hard to maintain languages, which had many failures to adapt to new tech. This is exactly what to expect.

I am talking about relatively modern language (C#) using good DB tech (lagging about seven, maybe five years from the state of art). Maybe, the story will be different in our case.

Re: Graph Databases 101

#99

Post by sklogic »

thesz wrote: post #98
sklogic wrote: post #72

Earlier quoted context omitted.

I worked on a (very old) ship-building and factory-building CAD, written mostly in PL/I and Fortran. It was built around a graph database. Throughout its long and turbulent history, there were many attempts of moving to a relational storage, every time resulting in orders of magnitude drop in performance. Keep in mind that in such a CAD designs are huge . Think of an aircraft carrier scale of "huge". And it was desig…

Had the state of art changed from the time of their last attempt to move to relational DB? Had the hardware changed during that time? You tell us about some old project, written in hard to maintain languages, which had many failures to adapt to new tech. This is exactly what to expect. I am talking about relatively modern language (C#) using good DB tech (lagging about seven, maybe five years from the state of art).…

The last attempt was made in around 2008, AFAIR.

Fundamentally nothing changed in the relational storage. Follow-a-graph-edge operation is as expensive as it used to be (involves an index lookup, it cannot be cheap).

If you know a relational arrangement suitable for a cheap O(1) edge traversal - please share. But I am very skeptical.

And I cannot see how the host language is relevant at all. C#, Haskell, whatever - none can make data access operations cost less than what the data model predicts.

Re: Graph Databases 101

#100

Post by gilleain »

GFK_of_xmaspast wrote: post #97
valhalla wrote: post #67

If anyone's curious about Network Science/Graph Theory in general here's a free online textbook used by a grad student friend of mine http://barabasilab.neu.edu/networksciencebook/downlPDF.html

Be careful about Barabasi: https://liorpachter.wordpress.com/2014/02/10/the-network-non... (FWIW, I had previously read some Barabasi papers and had come away seriously unimpressed, see also https://news.ycombinator.com/item?id=9555547 )

I misremembered Albert-László Barabási for Laszlo Babai - I was wondering why you were unimpressed!

Yes, scale-free networks (and so on, and so on), are oversold. Is his work really that bad though?

Post reply on HN