14th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services

Research Article

A Fast and Accurate Index Structure for Spatiotemporal Trajectories

  • @INPROCEEDINGS{10.4108/eai.7-11-2017.2274988,
        author={Somayeh Naderivesal and Lars Kulik and James Bailey},
        title={A Fast and Accurate Index Structure for Spatiotemporal Trajectories},
        proceedings={14th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services},
        publisher={ACM},
        proceedings_a={MOBIQUITOUS},
        year={2018},
        month={4},
        keywords={spatiotemporal trajectory indexing locality sensitive hashing},
        doi={10.4108/eai.7-11-2017.2274988}
    }
    
  • Somayeh Naderivesal
    Lars Kulik
    James Bailey
    Year: 2018
    A Fast and Accurate Index Structure for Spatiotemporal Trajectories
    MOBIQUITOUS
    ACM
    DOI: 10.4108/eai.7-11-2017.2274988
Somayeh Naderivesal1,*, Lars Kulik1, James Bailey1
  • 1: The University of Melbourne
*Contact email: naderis@student.unimelb.edu.au

Abstract

trajectory data provided by location-aware devices. Traffic management, ridesharing and Pay-As-You-Drive insurance are some example applications. These applications require one to scan a large-scale historical dataset in order to extract similar trajectories to a query trajectory. A naive approach is a one-by-one similarity comparison between the query trajectory and dataset trajectories. However, most existing methods for assessing similarity between pairs of trajectories have quadratic time-complexity, making sequential scan of a large dataset computationally expensive. Existing solutions for this problem mainly focus on reducing the computation time by summarizing the trajectories or by defining upper-bounds (lower-bounds) for the similarity between two trajectories. However, these solutions do not directly address the efficiency challenge. To tackle this challenge of large scale similar trajectory retrieval, we propose an efficient index structure that filters out distant trajectories and outputs an approximate set of similar trajectories. Experimental results show that our novel index structure significantly improves the efficiency of trajectory retrieval, whilst maintaining high accuracy.