search

hiposfer / kamal

A routing engine service using Open Street Maps and GTFS as data source
GNU Lesser General Public License v3.0
11 stars 1 forks source link

consider compressing stop.times entities into frequency based model #126

Closed carocad closed 6 years ago

carocad commented 6 years ago

Most of the time spend routing a person with GTFS feeds is wasted searching the right trip/src/dst combination among thousands of entries (saarland has 189000 lines).

Even with a our current indexes it still takes around 1 milliseconds to find the right entry. If we want to have query times of less than 100 milliseconds we cannot waste that much time per stop.

The current algorithm to solve that is frequency-based model:

It basically compresses a route into a sequence of tuples of the form [8:00, 15min, 41] where the last element is the frequency. This a reduction from possibly hundreds of entries down to single one !!

carocad commented 6 years ago

the GTFS spec already contains a similar feature. It could be integrated directly into o2g :)

related issue: https://github.com/hiposfer/osmtogtfs/issues/84

mehdisadeghi commented 6 years ago

@carocad I'm working on that.

carocad commented 6 years ago

closing in favour of #224