Does pgrouting have an algorithm to solve All Nearest Neighbors. I'd rather not run Dijkstra's or A* n times.
I'm working on a project of build US congressional districts based on a k-means clustering of citizen residences. But i want to use the driving distance for the distance function. This is like asking, what's the closest post office for every person. It's more work than A*, but it seems to me, less work than all pairs shortest path. Am i wrong?
http://en.wikipedia.org/wiki/Nearest_neighbor_search#All_nearest_neighbors
If not, i'll work on it, where's a good place to start.
Brian
--
http://brian.derocher.org
http://mappingdc.org
http://about.me/brian.derocher
The one-to-many pathfinding results can be constrained by distance, so the short answer is that there is a (potentially expensive) solution that you can go with right off the bat. It sounds to me like you need a breadth-first search, which I haven't seen for pgRouting but would be optimized for this kind of problem. I'd also like to see this implemented, so we could get ego networks and cost ego networks more efficiently than running 1-to-all and filtering the results.
-Elijah
----- Original Message -----
From: "Brian DeRocher" <brian@derocher.org>
To: "pgRouting users mailing list" <pgrouting-users@lists.osgeo.org>
Sent: Friday, June 6, 2014 12:56:25 PM
Subject: [pgrouting-users] All Nearest Neighbors
Does pgrouting have an algorithm to solve All Nearest Neighbors. I'd rather not run Dijkstra's or A* n times.
I'm working on a project of build US congressional districts based on a k-means clustering of citizen residences. But i want to use the driving distance for the distance function. This is like asking, what's the closest post office for every person. It's more work than A*, but it seems to me, less work than all pairs shortest path. Am i wrong?
http://en.wikipedia.org/wiki/Nearest_neighbor_search#All_nearest_neighbors
If not, i'll work on it, where's a good place to start.
Brian
--
http://brian.derocher.org
http://mappingdc.org
http://about.me/brian.derocher
_______________________________________________
Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
On 6/6/2014 3:56 PM, Brian DeRocher wrote:
Does pgrouting have an algorithm to solve All Nearest Neighbors. I'd
rather not run Dijkstra's or A* n times.
I'm working on a project of build US congressional districts based on
a k-means clustering of citizen residences. But i want to use the
driving distance for the distance function. This is like asking,
what's the closest post office for every person. It's more work than
A*, but it seems to me, less work than all pairs shortest path. Am i
wrong?
http://en.wikipedia.org/wiki/Nearest_neighbor_search#All_nearest_neighbors
If not, i'll work on it, where's a good place to start.
Brian
Brian,
The short answer is no.
You can look at the driving distance function where you give it a start point and it computes the code to all node in the network as you expand out from there.
You can also look at pgr_kdijkstra() which gives you a one to many solution but you have to give it a list of the "many" points you want the answers to.
In K-means, every time you add a point to a cluster you have to recompute the cluster centroid so because the centroid changed locations your "all nearest neighbors" needs to be recomputed.
I think the driving distance function is probably your best bet.
-Steve