3 ms·

I just lost track at the airbnb example. What is the inherent advantage of using a graph in the context of computing scores over 4million possibilities ? Should

I just lost track at the airbnb example. What is the inherent advantage of using a graph in the context of computing scores over 4million possibilities ? Should’t a Modern sql database be enough? PS : Or maybe we could use a blockchain to be even more modern?

hodl 9y ago
Or a hadoop cluster. Oh I'm showing my age!
vardanator 9y ago
The point of example is to show that graphs (for Airbnb case - trees) are a good fit. Modern sql database should be enough, but just because it has strong indexing, which is mostly implemented using B-trees, which are again graphs. So Airbnb example takes the reader to balanced binary trees (though it seems long reading).
- twic 9y ago
  I thought it was odd to treat trees as graphs. They are, but they're different enough that you don't use the same tools on them.
  - coldtea 9y ago
    Hmm? Trees are just acyclic and connected graphs in graph theory. Why wouldn't you use the same tools that apply to graphs in general?
    - yorwba 9y ago
      Acyclicity usually makes it possible to come up with a specialized algorithm that works better on trees than an algorithm that needs to handle all possible graphs. For example, many NP-complete problems become fixed-parameter tractable if you fix the tree-width of the graph (essentially, how many nodes you have to bag together until the graph looks like a tree). Because of this, algorithms on trees are often very different from general graph algorithms in practice. You could use the same tools, but it would be unnecessarily slow and/or complex.
Twisell 9y ago
Hold on I get It’s because actually that example was all about binary tree (which are often used under the hood by database engine for index scanning). I’ll give another shot to this article later but, I’m more lost than before because I managed to have a grasp of graph theory without knowing a lot about binary tree (I’am more a data analyst than a developer). PS : Thx vardanator
- deleted 9y ago
  [deleted]
- vardanator 9y ago
  Oh, thank you too, it's really great to hear a feedback.

hodl 9y ago

Or a hadoop cluster. Oh I'm showing my age!

vardanator 9y ago

The point of example is to show that graphs (for Airbnb case - trees) are a good fit. Modern sql database should be enough, but just because it has strong indexing, which is mostly implemented using B-trees, which are again graphs. So Airbnb example takes the reader to balanced binary trees (though it seems long reading).

twic 9y ago
I thought it was odd to treat trees as graphs. They are, but they're different enough that you don't use the same tools on them.
- coldtea 9y ago
  Hmm? Trees are just acyclic and connected graphs in graph theory. Why wouldn't you use the same tools that apply to graphs in general?
  - yorwba 9y ago
    Acyclicity usually makes it possible to come up with a specialized algorithm that works better on trees than an algorithm that needs to handle all possible graphs. For example, many NP-complete problems become fixed-parameter tractable if you fix the tree-width of the graph (essentially, how many nodes you have to bag together until the graph looks like a tree). Because of this, algorithms on trees are often very different from general graph algorithms in practice. You could use the same tools, but it would be unnecessarily slow and/or complex.

Twisell 9y ago

Hold on I get It’s because actually that example was all about binary tree (which are often used under the hood by database engine for index scanning). I’ll give another shot to this article later but, I’m more lost than before because I managed to have a grasp of graph theory without knowing a lot about binary tree (I’am more a data analyst than a developer). PS : Thx vardanator

deleted 9y ago
[deleted]
vardanator 9y ago
Oh, thank you too, it's really great to hear a feedback.