Skyline Query Framework for the Analysis of Electric Vehicle Trajectories

Sanporean, Ion-Anastasiu ; Galinauskas, Paulius

4. term

Data Engineering, MSc

2016

2016-06-13

Electrical vehicle's travel is affected by battery capacity, distance and charging stations along the road network. Thus charging routs are necessary to be optimized or to identify possible locations for charging stations. This paper proposes first a framework to identify trajectories in a dataset that are both inconvenient and important using Skyline Queries Algorithm (SQA) and second, a method to generate data under different conditions. Skyline queries are performed using a bicriteria approach: detour time of fastest route/path from source to target (deviation) and its frequency of occurrence in the historical dataset (support). Experiments were performed considering two different sizes maps: central Aalborg as a small map and North East Canada as a big map. The tests were performed to prove the efficiency of SQA by comparing it with 2 other algorithms: brute force skyline and sort filter skyline (SFS). The results showed that SQA running time outperforms the other two on the big map, while on the small map is comparable with Brute Force running time. The SQA algorithm identifies the skyline set in less than 3/4 of the time Brute Force algorithm does, using efficient pruning techniques. The Skyline obtained for different number of routes shows that the larger the support values, the smaller deviation values on both types of maps. The results have revealed that the framework is efficient in cases of analyzing large datasets, however a negative impact on performance was observed when analyzing small datasets.

Download
View record in AAU Student Projects