5th International ICST Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services

Research Article

Online Trajectory Data Reduction using Connection-preserving Dead Reckoning

Download202 downloads
  • @INPROCEEDINGS{10.4108/ICST.MOBIQUITOUS2008.3460,
        author={Ralph Lange and Frank D\'{y}rr and Kurt Rothermel},
        title={Online Trajectory Data Reduction using Connection-preserving Dead Reckoning},
        proceedings={5th International ICST Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services},
        publisher={ICST},
        proceedings_a={MOBIQUITOUS},
        year={2010},
        month={5},
        keywords={Online trajectory reduction dead reckoning MOD},
        doi={10.4108/ICST.MOBIQUITOUS2008.3460}
    }
    
  • Ralph Lange
    Frank Dürr
    Kurt Rothermel
    Year: 2010
    Online Trajectory Data Reduction using Connection-preserving Dead Reckoning
    MOBIQUITOUS
    ICST
    DOI: 10.4108/ICST.MOBIQUITOUS2008.3460
Ralph Lange1,*, Frank Dürr1,*, Kurt Rothermel1,*
  • 1: Institute of Parallel and Distributed Systems, Universitätsstraße 38, 70569 Stuttgart, Germany
*Contact email: ralph.lange@ipvs.uni-stuttgart.de, frank.durr@ipvs.uni-stuttgart.de, kurt.rothermel@ipvs.uni-stuttgart.de

Abstract

Moving objects databases (MODs) store objects’ trajectories by spatiotemporal polylines that approximate the actual movements given by sequences of sensed positions. Determining such a polyline with as few vertices as possible under the constraint that it does not deviate by more than a certain accuracy bound fi from the sensed positions is an algorithmic problem known as trajectory reduction. A specific challenge is online trajectory reduction, i.e. continuous reduction with position sensing in realtime. This particularly is required for moving objects with embedded position sensors whose movements are tracked and stored by a remote MOD. In this paper, we present Connection-preserving Dead Reckoning (CDR), a new approach for online trajectory reduction. It outperforms the existing approaches by 30 to 50%. CDR requires the moving objects to temporally store some of the previously sensed positions. Although the storage consumption of CDR generally is small, it is not bounded. We therefore further present CDRM whose storage allocation and execution time per position fix can be adjusted and limited. Even with very limited storage allocations of less than 1 kB CDRM outperforms the existing approach by 20 to 40%