Hacker News Reader

Comment by jonpaine | Hacker News Reader

Index-free-adjacency.

There are myriad pros/cons between graph/relational/nosql, but to me, a "real" graph db will have index free adjacency, allowing it to do deep traversals (friend of a friend-of a friend-oaf-oaf....) in constant time. It finds it's value in traversal of deeply connected datasets.

Any article or comparison that doesn't at least try to explain index free adjacency isn't going to make a compelling case for a graphdb, let along a native graph db. One reason for that may be that many "graph" databases don't have index free adjacency, so have worst than expected deep traversal characteristics.

View on HN

That makes sense. I'm seeing index-free adjacency mentioned in some other comparisons. Sounds pretty cool.

So if each node has pointers directly to related nodes (without needing an index lookup), does that also mean that inserts and updates are slower? From what I understand, if you're bypassing the need for an index lookup at query time, you have to pay for that at some other point in time - specifically by looking up the appropriate pointers at the time of insert/update. Is that accurate?

That's right. However, there are still indexes, even if they aren't necessary for traversal. Ideally you'll use an index to find a start node and traverse on from there (or in the case of your question, update from there).

Using a novel index, which combines hashes with linked-list, it is possible to gain the same complexity O(n) when traversing the whole graph.

Index-free adjacency is an implementation detail - with drawbacks:

If you store the vertices at each node as list of direct pointers, then traversing all neighbors has complexity O(k), if a vertex has k edges. Note that this is the best possible complexity because O(k) is the size of the answer. Deleting a single edge also has the same complexity of O(k) (assuming a doubly linked list), which is much worse.

Furthermore, usually one will want to be able to traverse edges in both directions, which makes it necessary to store direct pointers on both vertices that are incident with an edge. A consequence of this is that deleting a supernode is even worse: To remove all incident edges one has to visit every adjacent vertex – and perform a potentially expensive removal operation for each of them.

In general, a graph database is “a database that uses graph structures for semantic queries with nodes, edges and properties to represent and store data” (Wikipedia) – independent of the way the data is stored internally.

Your last sentence is perfect. Each chosen internal representation has time/space-tradeoffs its making. Users needs to pick a graph database based on the tradeoffs they can live with for their application.

You have to consider both in-memory and disk representation.

http://thinkaurelius.com/2013/11/01/a-letter-regarding-nativ...

Some graph databases have direct references in-memory and thats great, but a poor organization on-disk and thats bad.

Reply on news.ycombinator.com