REST: A Reference-based Framework for Spatio-temporal Trajectory Compression

gps设备和无线通信技术的普及导致了海量轨迹数据的产生，造成了昂贵的存储、传输和查询处理成本。为了缓解这一问题，文中提出了一种新的轨迹数据压缩框架REST (reference -based Spatio-temporal trajectory compression)，在给定的时空偏差阈值内，将原始轨迹由一系列历史(子)轨迹(称为参考轨迹)拼接起来，形成压缩后的轨迹。为了构建最有利于后续压缩的参考轨迹集，提出了三种技术来从大型数据集中明智地选择参考轨迹，使生成的参考轨迹集更紧凑，同时覆盖了感兴趣区域的大多数轨迹足迹。为了解决由于相似给定轨迹可能存在大量参考轨迹组合而导致的计算问题，本文提出了快速运行的高效贪婪算法和可实现最佳压缩比的动态规划算法。与现有的轨迹压缩工作相比，所提框架对数据在路网内移动或以恒定的方向和速度移动等假设较少，具有更好的压缩性能和相当小的时空损失。在真实出租车轨迹数据集上的大量实验表明，该框架在压缩率和效率方面均优于现有代表性方法。 

 如图1所示，REST框架由两个组件组成:reference set construction and referencebased compression。第一个部分旨在构建一个reference system，其中的挑战是如何在reference system set中的高覆盖率和低冗余之间进行权衡，以使后续的压缩能够更加有效和高效地进行。为此，提出3种方法，包括基于频繁模式的方法、基于冗余减少的方法和基于压缩的方法，它们使用不同的策略从大型训练数据集中选择紧凑但具有表现力的参考集。第二个组件需要解决我们可以用来表示给定轨迹的大量参考轨迹中的计算问题。为了提高效率，本文提出贪婪算法，试图用单个参考轨迹表示最长可能的样本序列。我们还开发了最优算法来计算压缩轨迹的最小存储代价，并获得相应的最优参考轨迹组合。

 2 PROBLEM STATEMENT

2.3 Reference-based Compression

 

 3 REFERENCE SET CONSTRUCTION

3.1 Frequent Pattern-based Approach (FPA) 

3.2 Redundancy Reduction Approach

3.3 Compression-based Approach (CA)

Graph-Flashback Network for Next Location Recommendation 

下一个兴趣点(Next point of Interest, POI)推荐在基于位置的应用中扮演着重要角色，旨在根据用户的历史轨迹向其推荐其最有可能访问的下一个POI。现有的方法通常使用丰富的边信息或定制的兴趣点图来捕获兴趣点之间的序列模式。然而，这些图只关注兴趣点之间的连通性。很少有研究提出显式地学习一个加权POI图，该图能够反映POI之间的过渡模式，并显示其不同邻居对每个POI的重要性。此外，这些方法只是简单地利用用户特征进行个性化兴趣点推荐，没有充分考虑用户兴趣点。为此，文中构建了一种具有强表示能力的用户-兴趣点知识图谱——时空知识图谱(Spatial-Temporal Knowledge Graph, STKG)。STKG用于学习每个节点(即用户，POI)和每个边的表示。然后，设计相似度函数来基于学习到的表示构建POI转移图。为了将学习到的图融入到序列模型中，提出一种新的网络图——闪回来进行推荐。图闪回在POI转移图上应用简化的图卷积网络(GCN)来丰富每个POI的表示。进一步，定义了一个相似度函数，在建模序列规则性时同时考虑时空信息和用户偏好。在两个真实数据集上的实验结果表明，所提出的方法取得了最先进的性能，明显优于所有现有的解决方案。 

阅读者总结：这篇论文是地理知识图谱的有趣论文

 本文提出Graph-Flashback model来解决上述三个挑战。针对第一个限制，首先构建了具有较强表示能力的时空知识图谱(STKG);基于STKG，使用知识图谱嵌入(KGE)算法来学习每个节点和每个边的表示。然后，使用学习到的表示构建POI转移图，这是一个加权的基于学习的图。我们学习到的POI转移图是从STKG派生的，并且在下一个学习过程中权重系数是恒定的。图1显示了我们的学习图和自定义图之间的差异。学习到的POI图明确显示了其不同邻居(不包括自己)对每个POI的重要性。然而，之前基于图的方法将GNN应用于构建的连通图，以学习每个POI的邻居的权重系数，这些POI是时变的和不透明的[11,13]。针对第二个限制，本文在兴趣点转移图上应用简化的图卷积网络(GCN)[9]来丰富每个兴趣点的表示，然后将其输入到基于rnn的模型中，为用户提供更好的推荐服务。请注意，我们的POI转换图能够反映POI之间的转换模式。同时，该模型可以与其他序列模型无缝集成，增强对序列的捕获能力转换规律。针对第三个限制，设计了一个相似度函数来衡量不同用户基于当前位置和时间的偏好，从而实现个性化兴趣点推荐

 

 5 MODEL FRAMEWORK

本节介绍了Graph-Flashback网络框架,包括:(i)嵌入层学习用户和POIs的密度表示,(ii) GCN layer that enriches the representations of POIs by our learned POI transition graph,(3)聚合层学习聚合加权隐状态的时空和用户偏好效应作为输出,和(iv)预测层,建议下个POI的输出和用户嵌入聚合。图3显示了我们提出的图闪回模型的网络架构。

 MetaNER: Named Entity Recognition with Meta-Learning

最近的命名实体识别(NER)神经架构在单域数据(如新闻通讯社)上产生了最先进的性能。然而，它们仍然存在以下问题:(i)需要大量的训练数据以避免过拟合;(ii)当训练和测试之间的数据分布存在域偏移时，性能会大幅下降。本文研究了同构和异构环境下命名实体识别的领域自适应问题。本文提出MetaNER，一种新的NER领域自适应元学习方法。具体来说，MetaNER融合了元学习和对抗性训练策略，以鼓励用于序列标记的鲁棒、通用和可迁移表示。MetaNER的关键优势是，它能够从这些域的少量注释数据中适应新的未见过的域。在同构和异构设置下的多个数据集上广泛评估了MetaNER。实验结果表明，MetaNER在8个基准数据集上取得了最好的性能。MetaNER超越了域内性能，在同构和异构设置中平均只使用16.17%和34.76%的目标域数据。 

AUC-MF: Point of Interest Recommendation with AUC Maximization 

兴趣点(point of interest, POI)推荐任务旨在根据用户的签到历史向其推荐未访问过的地点。兴趣点推荐的一个主要挑战是数据稀疏性，因为在所有可用兴趣点中，用户通常只访问极少数兴趣点。为此，提出一种最大化ROC曲线下面积(Area Under the ROC curve, AUC)的兴趣点推荐算法AUC- mf。AUC被广泛用于衡量不平衡数据分布下的分类性能。为了优化AUC，将推荐任务转换为分类问题，其中已访问的位置为正例，未访问的位置为负例。为了利用LambdaMF模型，将基于lambda的方法与协同过滤中的矩阵分解模型相结合，定义了一个新的AUC lambda。在两个数据集上的实验结果表明，AUC-MF在推荐精度方面明显优于现有方法。 

 

 本节详细介绍了拟议的AUC-MF，如图2所示。给定签到数据，我们生成正的和负的用户-兴趣点对，它们将被用作AUC-MF的输入。通过随机梯度下降(stochastic gradient descent, SGD)方法优化AUC-MF，得到用户偏好矩阵。

Node2LV: Squared Lorentzian Representations for Node Proximity

近年来，网络嵌入引起了广泛的研究兴趣。现有的网络嵌入模型大多基于欧氏空间。然而，欧氏嵌入模型不能有效地捕获复杂的模式，特别是真实世界图中的潜在层次结构。因此，双曲表示模型被开发出来以保留层次信息。然而，现有的双曲模型仅捕捉节点之间的一阶邻近性。本文提出一种新的嵌入模型Node2LV，使用平方洛伦兹距离学习节点的双曲表示。这样做有三个好处。首先，该模型可以有效地捕获来自网络拓扑结构的层次结构。其次，与传统的使用昂贵的黎曼梯度的双曲嵌入方法相比，该方法可以以更高效的方式进行优化。最后，与现有的双曲嵌入模型不同，Node2LV捕捉了高阶邻近性。用两个双曲嵌入表示每个节点，并使相关节点的嵌入彼此靠近。为了保持高阶的节点邻近性，使用随机游走策略生成局部邻域上下文。在四种不同类型的真实世界网络上进行了广泛的实验。实验结果表明，Node2LV显著优于各种图嵌入基线。 

Parallel Semantic Trajectory Similarity Join 

轨迹相似性连接(trajectory similarity join)是空间数据管理的一项基本功能。研究了语义轨迹相似性连接(semantic trajectory similarity join, STS-Join)问题。每个语义轨迹都是包含位置和文本信息的兴趣点(point -of-interest, poi)序列。因此，给定两个语义轨迹集合和一个阈值θ， STS-Join返回两个集合中空间-文本相似度不小于θ的所有语义轨迹对。这种join针对的应用包括基于词的轨迹近似重复检测、地理文本数据清洗、个性化拼车推荐、关键词感知的路线规划和旅行路线推荐。 

考虑到这些应用，本文提供了一个有目的的空间-文本相似度的定义。为了在大规模语义轨迹集上实现高效的STSJoin处理，开发了轨迹对过滤技术，并考虑了现代处理器的并行处理能力。具体地，提出了一种两阶段并行搜索算法。首先根据文本信息对语义轨迹进行分组;该算法的pergroup搜索是相互独立的，因此可以并行执行。对于每一组，基于空间域对轨迹进行进一步划分。为每个轨迹批次生成空间和文本摘要，在此基础上开发了批量过滤和轨迹-批量过滤技术，以批量模式修剪不合格的轨迹对。此外，提出了一种高效的分治算法来推导两个语义轨迹之间的空间相似度边界和文本相似度边界，使我们能够在不计算空间-文本相似度精确值的情况下剪枝不相似的轨迹对。在大规模语义轨迹数据上的实验结果表明，语义轨迹连接算法的性能是设计的基准算法的8-12倍。 

 IV. TWO-PHASE PARALLEL MATCHING

本文提出了一个处理STS-Join的两阶段并行匹配算法(2-PM)。具体地，针对τi和τj中的不足，提出了轨迹对剪枝策略，剪枝"不合格"的轨迹对，而不需要计算每个对象对之间的相似度。为解决限制(2)，本文提出一种并行化的批处理算法，能够同时评估一组轨迹对。 

 

图4展示了我们的2-PM算法的框架。给定语义轨迹集合T，为每个轨迹生成摘要，以表示其空间和文本信息(参见第IV-B节)。基于总结信息，我们将相似轨迹分组并进行批处理过滤(参见第IV-D节)。如果一对批次(组)无法剪枝，则继续使用轨迹对过滤技术评估这两个批次中的每个轨迹对(参见第IV-C节)。请注意，批量过滤和轨迹对过滤都可以并行处理

Traffic Congestion Alleviation over Dynamic Road Networks: Continuous Optimal Route Combination for Trip Query Streams 

路线规划与推荐是近年来的研究热点。本文研究了一个连续的最优路径组合问题:给定一个动态的路网和一个出行查询流，我们不断地为查询流上的每个新批查询寻找一个最优的路径组合，使所有路径的总旅行时间最小。每条路线对应于当前查询批次中特定行程查询的规划结果。该问题适用于交通流管理、实时路径规划和持续拥塞预防等领域。精确算法具有指数级的时间复杂度，在动态交通网络的应用场景中计算量过大。针对该问题，提出一种自感知的批处理算法。广泛的实验为所提出算法的准确性和效率提供了深入的见解。 

Towards Alleviating Traffic Congestion: Optimal Route Planning for Massive-Scale Trips 

本文研究了大规模出行的最优路径规划问题:给定一个交通感知的道路网络和一组出行查询Q，旨在为每个出行找到一条路线，使Q中所有查询的全局旅行时间成本最小。该问题可应用于交通流管理、路线规划和交通拥挤预防等领域。精确算法具有指数级的时间复杂度，在动态交通网络的应用场景中计算量过大。为了应对这一挑战，我们提出了贪婪算法和-精炼算法。广泛的实验为所提出算法的准确性和效率提供了深入的见解。 

 Parallel Subtrajectory Alignment over Massive-Scale Trajectory Data

本文研究了大规模轨迹数据上的子轨迹对齐问题。给定一组轨迹，子轨迹对齐查询通过对已有轨迹进行拆分和对齐，返回新的目标轨迹。由此产生的功能针对一系列应用，包括轨迹数据分析、路线规划和推荐、拼车和一般的基于位置的服务。为了实现高效和有效的子轨迹对齐计算，本文提出了一种新的搜索算法和过滤技术，使现代处理器的并行处理能力得以利用。在大规模轨迹数据集上进行了实验，以评估该方法的性能。实验结果表明，该方法能够生成高质量的子轨迹对齐结果，具有较高的效率和可扩展性。 

 

 3 Parallel Subtrajectory Alignment Search

我们的PSTAS算法包括两个阶段:(1)生成候选轨迹(章节3.1);(2)子候选序列对齐(第3.2节)。 

Contextualized Point-of-Interest Recommendation 

兴趣点(Point-of-interest, POI)推荐已经成为推荐系统研究中一个越来越重要的子领域。已有的推荐方法通过多种假设来利用上下文信息来提高推荐精度。它们的共同特点是相似的用户更有可能访问相似的兴趣点，相似的兴趣点也希望被同一个用户访问。然而，现有的方法都没有明确地利用相似性来进行推荐。文中提出了一种新的兴趣点推荐框架，该框架显式地利用了上下文信息的相似度。将上下文信息分为两组，即全局上下文和局部上下文，并开发不同的正则化项来合并它们以进行推荐。利用图拉普拉斯正则项来利用全局上下文信息。此外，将用户聚类到不同的组中，并让目标函数约束同一组中的用户具有相似的预测POI评分。采用交替优化方法对模型进行优化，得到最终评分矩阵。实验结果表明，该算法的性能优于现有的所有算法。 

Pay Your Trip for Traffic Congestion: Dynamic Pricing in Traffic-Aware Road Networks

定价是优化运输资源配置的关键。拥堵定价被广泛用于缓解城市交通拥堵。本文提出并研究了一种新的动态定价策略(DPS)，在智能交通平台(如滴滴、Lyft、Uber)中为旅行者的行程定价。这些行程是根据它们对全球城市交通系统的“拥堵贡献”收取费用的。动态定价策略在n个旅行者的出行与潜在出行路线(每个出行有k个潜在路线)之间检索一个匹配，以最小化全球交通拥堵。我们相信，DPS具有造福社会和环境的潜力，例如减少交通拥堵，实现更智能和更绿色的交通运输。DPS问题由于计算复杂度高(存在kn匹配的可能性)而具有挑战性。为了进一步提高匹配效率，提出了一种基于局部搜索的高效近似匹配算法和剪枝技术。通过在真实数据集上的大量实验，验证了动态定价策略的准确性和高效性。 

 Real-Time Route Search by Locations

随着gps数据(如路线和轨迹)的激增，实时路线搜索和推荐的功能变得非常重要。本文定义并研究了一种新的连续按位置路由搜索(CRSL)问题，以实现大量用户在路由数据流上按位置实时路由搜索。给定一组C-RSL查询，其中每个查询q包含一组要访问的地点q. o和一个阈值q.θ，我们不断地向每个查询q提供与q. o相似不小于q.θ的路由。我们还将该方法扩展到支持top-k C-RSL问题，即每个查询持续维护k条最相似的路由。 C-RSL问题针对各种应用，包括实时路线规划、拼车和其他具有实时需求的基于位置的服务。为了在大量的CRSL查询中实现有效的路由匹配，我们开发了新的并行路由匹配算法，该算法具有较好的时间复杂度。使用真实数据进行的大量实验为我们的算法的性能提供了深入的见解，表明我们的建议能够实现高效率和可伸缩性。

Region-Based Message Exploration over Spatio-Temporal Data Streams 

基于位置的社交媒体产生了大量包含位置和文本内容的时空数据。这些时空信息涵盖了广泛的主题。基于用户基于位置和基于主题的需求发现局部趋势主题具有重要意义。该文提出了一种基于区域的消息探索机制，根据用户对消息主题和消息空间分布的偏好，从大量时空消息流中检索出时空消息簇。此外，本文还提出了一种区域摘要算法，该算法在一个聚类中寻找一个具有代表性的消息子集，以概括类中消息的主题和空间属性。在两个真实数据集上的实验结果表明，与基线方法相比，所提方法具有更高的效率和效率。 

 图1说明了我们基于区域的消息探索机制的框架。我们有两种类型的输入数据:(1)基于位置的社交媒体发布的时空消息流;(2)用户注册的订阅区域集合。

在第一阶段，对连续到达的时空消息采用通用的时空在线聚类算法进行聚类;然后，将每个新聚类视为一个“查询”，遍历订阅索引，根据订阅区域与聚类区域的相关性度量找到与新聚类区域匹配的订阅区域子集。通过一个深度度量学习模型，即三元组网络来学习。为了可视化每个交付的簇，从簇区域中选择一个具有代表性的时空消息子集(即区域摘要)。具体来说，所选消息期望代表聚类区域中所有消息的空间和文本信息。

GNN-Retro: Retrosynthetic Planning with Graph Neural Networks 

反合成规划是有机化学领域的一个重要研究内容，它可以为目标产品提供一条合成路线。合成路线是一系列的反应，从可用的分子开始。合成路线生成中最具挑战性的问题是候选反应的大搜索空间。通过估计候选反应的代价可以有效地缩减搜索空间，在相同的搜索迭代次数下达到更高的准确率。一个反应的估计由它所有反应物的估计组成。因此，如何估算这些反应物的成本将直接影响结果的质量。为了获得更好的性能，结合图神经网络(GNN)和最新的搜索算法，提出了一个新的框架GNN- retro，用于反合成规划问题。该框架中的GNN结构可以融合相邻分子的信息，这将提高框架的估计精度。在USPTO数据集上的实验表明，在相同的设置下，该框架能够以较大的差距超越当前最先进的方法。 

Towards Efficient Selection of Activity Trajectories Based on Diversity and Coverage 

随着基于位置的服务的普及，活动轨迹的生成速度越来越快。活动轨迹数据通过用户的语义活动丰富了传统轨迹数据，不仅显示了用户曾经去过的地方，还显示了用户的偏好。然而，大量的数据对人们来说是昂贵的。为了解决这一问题，本文研究了多样性感知的活动轨迹选择(Diversity-aware Activity Trajectory Selection, DaATS)问题。给定用户感兴趣的区域，它会找到少量具有代表性的活动轨迹，这些轨迹可以为用户提供该区域不同方面的广泛覆盖。该问题在轨迹相似度计算效率和子集选择方面都具有挑战性。为了应对这两个挑战，本文提出了一种新的解决方案:(1)利用深度度量学习方法来加速相似度计算;(2)证明了DaATS问题是NP-hard问题，并给出了一个性能保证的近似算法。在两个真实数据集上的实验表明，所提出的建议明显优于最先进的基线 

 Trajectory Similarity Learning

在本节中，我们的目标是学习一个神经网络，它(1)为任意长度的轨迹创建简单的向量表示;(2)很好地逼近了相似性度量。 

 所提出模型的概述如图1所示。它依赖于两个部分来建模轨迹:(1)双向循环神经网络。在许多实际场景中，物体通常在具有一定结构特征的空间网络中移动。由于网络的限制，同一轨迹内的相邻点之间存在一定的依赖关系。为了捕获这种依赖，我们建议使用双向LSTM (BiLSTM)结构，因为它对上下文信息有很好的把握;(2)轨迹间注意力(ITA)模块。根据轨迹的相似性对轨迹进行聚类，并使用记忆张量存储它们在两个方向上的摘要信息。然后，利用基于注意力的方法获取轨迹之间的相关性;