Probabilistic range queries for uncertain trajectories on road networks
Probabilistic range queries for uncertain trajectories on road networks
复制标题
DOI：
10.1145/1951365.1951400
复制
发表时间：
2011-03
期刊：
影响因子：
--
通讯作者：
Kai Zheng;Goce Trajcevski;Xiaofang Zhou;P. Scheuermann
中科院分区：
文献类型：
--
作者：
Kai Zheng;Goce Trajcevski;Xiaofang Zhou;P. Scheuermann
表示移动对象运动的轨迹通常在离散时刻通过位置采样获得，例如使用GPS或路边传感器。在连续采样之间，对给定移动对象的下落一无所知。已经提出了各种模型(例如，剪切圆柱体；时空棱镜)来表示移动物体在不受约束的欧几里得空间以及道路网络中的不确定性。在本文中，假设每个路段上的最大速度可用，我们将沿道路网络移动的对象的不确定性表示为与时间相关的概率分布函数。针对这些情况，我们引入了一种新的索引机制--不确定轨迹层次结构，并在此基础上提出了处理时空范围查询的高效算法。我们还给出了实验结果，证明了我们所提出的方法的好处。
Trajectories representing the motion of moving objects are typically obtained via location sampling, e.g. using GPS or road-side sensors, at discrete time-instants. In-between consecutive samples, nothing is known about the whereabouts of a given moving object. Various models have been proposed (e.g., sheared cylinders; spacetime prisms) to represent the uncertainty of the moving objects both in unconstrained Euclidian space, as well as road networks. In this paper, we focus on representing the uncertainty of the objects moving along road networks as time-dependent probability distribution functions, assuming availability of a maximal speed on each road segment. For these settings, we introduce a novel indexing mechanism -- UTH (Uncertain Trajectories Hierarchy), based upon which efficient algorithms for processing spatio-temporal range queries are proposed. We also present experimental results that demonstrate the benefits of our proposed methodologies.