[postgis-users] How to match lines between two similar graphs?

[Stephen Woodbridge]

Hi All,

I have an interesting problem I am trying to solve and would love some 
feedback on how to best go about it.

I have road data from two different vendor data sets. But this could 
also be one road network and a GPS track, so I think this is a pretty 
common use case.

Assumptions:

o the networks are similar, ie: they have similar roadway coverage
o the two sets might be slightly misaligned, ie: shifted by some amount
o the segments in the two data sets do not have to be broken into 
equivalent segments, ie: one segment in A might be represented my 
multiple segments in B
o segments are not aligned end point wise, ie: a segment in A might go 
from mid-point one segment in B to the midpoint of a connected segment in B
o in many cases I will be working with a set of lines in one set that I 
need to match to the other to select a matching set of lines.

So strategies for matching these:

1. take a segment from A and buffer it, then intersect the data in B and 
select the longest intersected object. I can probably throw out any 
pieces smaller than the buffer distance.

2. Do the same but buffer and union the set of lines into a single 
multipolygon, and intersect that with the other set.

3. ??? Other ideas?

Thoughts on performance?

Typically I will have a small set (1-20) of segments to compare against 
a larger (100K-2M) set. Obvious a spatial index will will be used. But 
I'm wondering what is the fast way to do this matching computationally. 
I think I will want to be able to compare 1-200 sets like this every 5 
mins as data comes in from a feed, while supporting other queries.

Thoughts would be appreciated.

-Steve