How to use ES to find shortest pat(in graph)


(HJ Shin) #1

Hi, Thank you for the amazing work!

I am trying to build a GPS tracking system.
For this I am concerning to use graph theory.

If I build nodes(geo-point) and edges(from node id, to node id), can I find the shortest path between 2 nodes?

Above is my index concept.
If I want to find a shortest path between node 111 and node 333, is there any method to find it at once.
(I can find edges with 'from node 111' and expand it to 'to' but is has lots of loop so the time complexity is grow up)

  1. 'nodes' index
    {
    id : 111,
    geo-point
    }

{
id : 222,
geo-point
}

{
id : 333,
geo-point
}

....

  1. 'edges' index
    {
    from : 111,
    to : 222
    }

{
from : 222,
to : 333
}

...

If you have any idea on it, please share this with me.

Thanks.
HJ Shin.


(Adrien Grand) #2

I don't think you can make Elasticsearch solve the problem for you. I think the best you could do with Elasticsearch would be to implement the shortest path algorithm on top of Elasticsearch (by the way, you might want to cache the distances on the edges). Note that it might be slow though, I suspect a graph database would be a better fit for this problem.


(HJ Shin) #3

Thank you for the suggestion!

I have an idea to build the shortest path algorithm but the search time is the issue.
(I may try this to see whether I can make it time efficiently or not :slight_smile: )

Also, I will search for the other options(graph db)

Thanks again


(system) #4

This topic was automatically closed 28 days after the last reply. New replies are no longer allowed.