کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4956534 1444521 2017 32 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
DOTS: An online and near-optimal trajectory simplification algorithm
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
DOTS: An online and near-optimal trajectory simplification algorithm
چکیده انگلیسی
The last decade witnessed an increasing number of location acquisition equipments such as mobile phone, smart watch etc. Trajectory data is collected with such a high speed that the location based services (LBS) meet challenge to process and take advantage of that big data. Good trajectory simplification (TS) algorithm thus plays an important role for both LBS providers and users as it significantly reduces processing and response time by minimizing the trajectory size with acceptable precision loss. State of the art TS algorithms work in batch mode and are not suitable for streaming data. The online solutions, on the other hand, usually use some heuristics which won't hold the optimality. This paper proposed a Directed acyclic graph based Online Trajectory Simplification (DOTS) method which solves the problem by optimization. Time complexity of DOTS is O(N2/M). A cascaded version of DOTS with time complexity of O(N) is also proposed. To our best knowledge, this is the first time that an optimal and online TS method is proposed. We find both the normal and cascaded DOTS outperform current TS methods like Douglas-Peucker (Douglas and Peucker, 1973), SQUISH (Muckell et al., 2011) etc. with pretty big margin.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Systems and Software - Volume 126, April 2017, Pages 34-44
نویسندگان
, ,