Using Graph DB to store distance between points using PHP

Question

I need to quickly find n closest destinations for given destinations, compute an nxn distance matrix for n destinations, and several other such operations related to the distances between two or more destinations.

I found out that a DB graph will give much better performance compared to a MySQL database. My application is written in PHP.

SO my question is: is it possible to use Graph DB with a PHP application, if so, which one is the best option and open source and how to store this data in a DB graph and how it will be available.

Thanks in advance.

Answer 1

Neo4j is a very reliable DB column and has flexible (if a bit complicated) licensing. It implements the Blueprints API and should be fairly easy to use from any language, including PHP. It also has a REST API , which is about as flexible as it is, and there is at least one good example of using it from PHP.

Depending on what data you have, there are several ways to save it.

If you have route data where your points are already connected to each other through certain paths (i.e. you cannot go from one point directly to another), then you just make each point a node and the connections that you have between the points of your routes, these are the edges between the nodes, and the distances are the properties of these edges. This will give you a graph similar to your classic “traveling salesman” problem, and calculating the distances between the nodes is just a weighted rough search (if you want to get the shortest path).

If you can jump from place to place with your data set, then you have a fully connected schedule. Obviously, this is a lot of data and grows quadratically when you add more destinations, but it is probably better to deal with this than with a relational database. To keep distances when you add nodes to the graph, you also add an edge to each other of the existing node with a pre-calculated distance as one of its properties. Then, to get the distance between the two nodes, you just find the edge between them and get its distance property.

However, if you have a large number of fully connected nodes, you probably would be better off just storing the coordinates of these nodes and calculating the necessary distances and possibly caching the results to speed things up.

Finally, if you use the Blueprints API and other tools in this stack, such as Gremlin and Rexter , you can swap any compatible graphics database that allows you to play with various implementations that can suit your needs better, for example, using Titan on top of Cassandra / Hadoop .

Answer 2

Yes, a graph database will give you more performance than an extension for MySQL or Postgres. One that looks really smooth , OrientDB , aa beta implementation in PHP using a binary protocol, and another that uses HTTP as a transport layer.

Regarding the sample code, Alessandro (from odino.org ) wrote an implementation of Dijkstra's algorithm along with a full explanation of how to use it with OrientDB to find the minimum distance between cities .

Answer 3

Actually it is not so much about a database, as about indexes. I used MongoDB geospatial indexing and search (DB document), which has geo-indexing designed to search for several nearest elements for given coordinates - with good results, However - it only runs simple queries (find the nearest one) and it slows down a bit if your index does not fit into RAM (I used the geonames database with 8 million locations with coordinates and received 0.005-2.5 s for a request for VM - 1. overhead hdd 2. perhaps the index did not fit into RAM).