Maximizing Range Sum in Trajectory Data

最大化范围和(MaxRS)查询是计算几何和数据库领域的一项基本操作。给定一组二维空间的加权对象和一个矩形，MaxRS查询的目的是找到矩形的最优位置，使被覆盖对象的总权值(即Range Sum)最大化。所有关于MaxRS查询的现有文献通常假设每个对象都与一个唯一的点相关联。然而，在实际应用中，每个物体(例如GPSenabled移动车辆)都与包括一系列点的轨迹有关，这就超出了这个限制性的假设。如何解决轨迹数据中的MaxRS查询问题是一个重要而具有挑战性的问题。在本文中，我们提出了一个MaxRST查询的定义，当轨迹中至少有一个点被矩形包围时，轨迹被矩形覆盖。提出了一种求解MaxRST查询的新方法，将MaxRST查询转化为直线多边形交问题。在此基础上，提出了一种基于区间树的划分方法来有效地解决直线多边形的交点问题。为了进一步缩短响应时间，我们提出了(，δ)-近似MaxRST查询，该查询返回一个与最优覆盖权值相对误差的近似答案，概率至少为δ。此外，提出了两种基于互补采样的(，δ)近似MaxRST算法。一种是对直线多边形进行随机采样并替换，样本大小与轨迹数量无关。另一种采用网格迁移技术减少样本数量，但需要额外的网格构建成本。理论分析和实验结果表明，所提出的算法具有较高的效率和准确性

阅读者总结：这是一篇很有趣的论文，文中提到的问题在KDD2020 Optimizing Impression Counts for Outdoor kDD2018 以及 Trajectory-driven Influential Billboard Placement 最佳论文  涉及到的问题类似，都是基于轨迹时空数据实现户外广告牌投放问题。这篇论文主要是将整个问题进行了转化，变成为了一种直线几何最大覆盖问题，同时在大规模轨迹问题时，采用了一种采样的方法，在实验部分中显示，采样方法是很适用在大规模轨迹问题中。

 

 

 Challenge 1: Efficiently and exactly solving MaxRST query.

我们的解决方案。首先，将MaxRST查询转化为多边形求交问题;然后，提出一种新的分割技术，将直线多边形分割为多个互不相交的矩形。证明了直角多边形求交问题与分块矩形求交问题是等价的。最后，提出了一种基于轨迹划分的精确算法来解决MaxRST查询，时间复杂度为O(n log n)，其中n为轨迹中包含的点的总数。 

Challenge 2: Efficiently returning an approximate answer to MaxRST query with error guarantees.

我们的解决方案。我们使用概率模型来保证近似精度。提出(，δ)-approximate MaxRST查询，它返回一个近似的结果，最优覆盖权重的误差大于δ。 为了解决这个问题，提出了两种互补的基于采样的(，δ)-近似MaxRST算法。鉴于MaxRST查询可转化为直线多边形相交问题，第1种算法对直线多边形进行随机采样替换，当样本数量达到某个与轨迹数量无关的阈值时，返回(，δ)-近似结果;另一种方法采用网格移动技术来减少样本大小，但需要额外的网格构建成本。

 

 

 

 

 

 实验部分

 

 

 实验结果表明，精确算法PMaxRST具有较高的效率和可扩展性，近似算法Sampling和SamplingWithGrid更适用于大规模轨迹数据集。