DASFAA2023_SimiDTR Deep Trajectory Recovery with Enhanced Trajectory Similarity_华为云.pdf

迹部景吾

17页

2次

2024-08-28

免费下载

SimiDTR: Deep Trajectory Recovery

with Enhanced Trajectory Similarity

Yupu Zhang

, Liwei Deng

, Yan Zhao

, Jin Chen

, Jiandong Xie

and Kai Zheng

1,2,3(

)

Yangtze Delta Region Institute (Quzhou), University of Electronic Science and

Technology of China, Chengdu, China

zhengkai@uestc.edu.cn

School of Computer Science and Engineering, University of Electronic Science and

Technology of China, Chengdu, China

{zhangyupu,deng

liwei,chenjin}@std.uestc.edu.cn

Shenzhen Institute for Advanced Study, University of Electronic Science and

Technology of China, Chengdu, China

Department of Computer Science, Aalborg University, Aalborg, Denmark

yanz@cs.aau.dk

Cloud Database Innovation Lab of Cloud BU, Huawei Technologies Co., Ltd.,

Chengdu, China

xiejiandong@huawei.com

Abstract. The pervasiveness of GPS-equipped smart devices and the

accompanying deployment of sensing technologies generates increasingly

massive amounts of trajectory data that cover applications such as per-

sonalized location recommendation and urban transportation planning.

Trajectory recovery is of utmost importance for incomplete trajectories

(resulted from the constraints of devices and environment) to enable

their completeness and reliability. To achieve eﬀective trajectory recov-

ery, we propose a novel trajectory recovery framework, namely Deep

Trajectory Recovery with enhanced trajectory Similarity (SimiDTR),

which is capable of contending with the complex mobility regularity

found in trajectories in continuous space. In particular, we design a rule-

based information extractor to extract the spatial information related

to an incomplete trajectory, which is then fed into a deep model based

on attention mechanism to generate a tailored similar trajectory for the

incomplete trajectory. Finally, we use a deep neural network model to

recover the incomplete trajectory with the blessing of its similar trajec-

tory. An extensive empirical study with real data oﬀers evidence that the

framework is able to advance the state of the art in terms of eﬀectiveness

for trajectory recovery, especially in scenes with sparse trajectory data.

Keywords: Trajectory Recovery

· Trajectory Similarity · Sparse Data

 The Author(s), under exclusive license to Springer Nature Switzerland AG 2023

X. Wang et al. (Eds.): DASFAA 2023, LNCS 13943, pp. 431–447, 2023.

https://doi.org/10.1007/978-3-031-30637-2

_28

432 Y. Zhang et al.

1 Introduction

The widespread use of mobile devices has resulted in a proliferation of trajectory

data, which contain a wealth of mobility information that is critical to location-

based services, e.g., route optimization [29] and travel time estimation [6].

Trajectory data use discrete spatial-temporal point pairs to describe the

motion of objects in continuous time and space. Due to the limitations of equip-

ment and environment such as equipment failure and signal missing, many trajec-

tories are recorded at a low sampling rate or with missing locations, called incom-

plete trajectories. Too large sampling interval between two consecutive sampling

points can lose detailed information and lead to high uncertainty [30], which

aﬀects downstream applications (e.g., indexing [12], clustering [20], and min-

ing [11,24,25]) negatively. Therefore, it is important to recover missing spatial-

temporal points for incomplete trajectories and reduce their uncertainty.

In general, previous studies on trajectory recovery can be divided into two

directions. The ﬁrst direction focuses primarily on modeling users’ transition

pattern among diﬀerent locations to predict users’ missing locations [4,7,8,10,

15,19,25–27]. The basic task is essentially a classiﬁcation task, and the recov-

ered trajectories are usually composed of locations or POIs. The second direction

aims to recover the speciﬁc geographic coordinates of trajectories at the miss-

ing timestamps based on the incomplete trajectory data recorded [2,5,9,14,16–

18,23,24,28]. The ﬁnal rebuilt trajectories usually consist of precise (GPS or

road network) coordinates. In this work, we focus on the second direction, i.e.,

recovering precise GPS coordinates for incomplete trajectories.

A straightforward approach for the second direction is to regard a single

trajectory as two-dimensional time series directly and apply time series impu-

tation methods to recover incomplete trajectories [2,5,9,16,17,28]. These meth-

ods exhaust all the precise information of a single incomplete trajectory when

recovering it and work quite well when the proportion of the missing trajectory

data is small. However, their eﬀectiveness decreases signiﬁcantly as the miss-

ing proportion increases, which means that they cannot deal with the sparse

trajectory data. Another common solution for this problem is cell-based meth-

ods [14,18,23,24], which divide the space into discrete cells and then recover

the missing trajectories described by cells. They further design diﬀerent post-

calibration algorithms to reﬁne the results. These methods transform the trajec-

tory recovery problem from inﬁnitely continuous space into ﬁnite discrete space,

which reduce the complexity of prediction to improve the capacity of modeling

transition patterns. Although the cell-based methods can alleviate the problem

of data sparsity to some extent, they only use the information contained in the

incomplete trajectory instead of making full use of information coming from

other trajectories. Besides, some extra noise and inaccurate information would

inevitably be introduced since these methods use cells to represent trajectories.

Furthermore, in the calibration stage, there is a lack of available information for

getting accurate trajectory coordinates.

Exploiting the similarity among diﬀerent trajectories to model the complex

mobility regularity for incomplete trajectories, we propose a novel trajectory

SimiDTR: Deep Trajectory Recovery with Enhanced Trajectory Similarity 433

recovery framework, namely Deep Trajectory Recovery with enhanced trajec-

tory Similarity (SimiDTR) to recover precise coordinates for trajectories. To

address the problem of data sparsity, we carefully design a rule-based informa-

tion extractor to tease out a raw similar trajectory, which has relevant spatial

information about the given incomplete trajectory. This raw similar trajectory

is the result of integrating information from several other related incomplete tra-

jectories. Considering the properties (e.g., spatial bias, temporal bias, and tem-

poral shifts) of trajectory data, we use an attention-based deep neural network

model to sort out this raw similar trajectory and generate a similar trajectory

tailored to the incomplete trajectory (i.e., the similar trajectory that does not

actually exist but best ﬁts the data of incomplete trajectory), which is used for

recovering the incomplete trajectory. In order to make full use of the trajectory

coordinate information, we perform the trajectory recovery in continuous space.

Our contributions can be summarized as followed:

1) We propose a novel deep trajectory recovery framework with enhanced tra-

jectory similarity, which directly recovers coordinates of trajectories in con-

tinuous space. To our knowledge, this is the ﬁrst study that takes similar

trajectory information into the deep learning model in the ﬁeld of trajectory

recovery.

2) To contend with the sparsity of incomplete trajectories, we design a rule-

based information extractor that aims to generate a raw similar trajectory

for the target incomplete trajectory and propose an attention-based deep

neural network model to create a tailor-made similar trajectory based on the

inherent characteristics of trajectory data for incomplete trajectory recovery.

3) We report on experiments using real trajectory data, showing that our pro-

posal signiﬁcantly outperforms state-of-the-art baselines in terms of eﬀective-

ness for trajectory recovery, especially in scenes with sparse trajectory data.

2 Related Work

Based on the objects to be recovered, the trajectory recovery can be classiﬁed

into location recovery and coordinate recovery.

Location recovery aims to predict missing locations (e.g., POIs) for a tra-

jectory [19,25,26]. Xi et al. [25] propose a framework named Bi-STDDP for

location recovery, which takes into account bidirectional spatio-temporal depen-

dency. AttnMove [26] uses attention mechanisms to inject aggregated historical

trajectory information into recovery process. On the basis of AttnMove, Period-

icMove [19] takes into account the inﬂuence of trajectory shifting periodicity.

Taking the trajectory data as two-dimensional time series, the time series

imputation methods [2,5,9,16,17,28] can be used to recover the missing coordi-

nates (observations) in trajectories (time series). Some RNN-based [2,28], GAN-

based [16,17] and VAE-based methods [9] exist, which can be used to recover

coordinates. Generating the recovered trajectories represented by cells, following

by a post-calibration algorithm to get the coordinates of trajectories, Cell-based

methods [14,18,23,24] are proposed for this task. For example, Wei et al. [24]

of 17

免费下载

相关文档

评论