kharita

Kharita (Map in Arabic) is a robust and online algorithm for map inference from crowd-sourced gps data. We provide in this repository the code for two versions of the algorithm, both described in our SIAM SDM 2018 (See Citation below):

• Kharita (Offline): this version creates the map using offline data.
• Kharita Star (Online): this version creates the map in an online fashion, i.e., one trajectory at a time.

Input

The input is a csv file in the following format: vehicule_id,timestamp,lat,lon,speed,angle

Vehicule_id: important to identify trajectories. Timestamp: important to sort gps points within trajectories timestamp: in the format: yyyy-mm-dd hh:mm:ss+03 angle: in 0-360 interval. Angle to the north.

Running Kharita Star (The online version)

Kharita can be invoked from command line as follows:

python kharita_star.py -p data -f data_2015-10-01 -r 25 -s 10 -a 40

-p: the folder containing the input data

-f: the input file name without its extension

-r: the radius (cr) in meters used for the clustering

-s: the densification distance (sr) in meters

-a: the angle heading tolerance in degrees (0-360)

Example

python kharita_star.py -p data -f data_uic -r 100 -s 20 -a 60

Running Kharita offline

Kharita offline is a bit slower but tend to produce nicer and more accurate maps.

• command: python kharita.py

Output

The code will produce a txt file containing the edges of the generated directed graph.

UIC map examples

Kharita* map

Kharita map

Citation

For any use of this code, please cite our work as follows: Stanojevic, Rade, Sofiane Abbar, Saravanan Thirumuruganathan, Sanjay Chawla, Fethi Filali, and Ahid Aleimat. "Robust road map inference through network alignment of trajectories." In Proceedings of the 2018 SIAM International Conference on Data Mining, pp. 135-143. Society for Industrial and Applied Mathematics, 2018. [Arxiv version]

Contact

Sofiane Abbar ([email protected])