[pgrouting-users] All Nearest Neighbors

[Stephen Woodbridge]

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