PostgreSQL + PostGis. Хранить в виде обычных координат желаемой точности. Возможно выборка любой сложности.
Сейчас у меня база координат занимает более 70гб, выборка координат внутри желаемого полигона занимает примерно 6мс на обычном hdd.
При желании можно треки запихать в виде multiline из которого потом легко вытащить отдельные точки
P.S. связку PostgreSQL + PostGis использует OSM, где база планеты в распакованном виде легко переваливает за 500гб