Building Non-centralized Discovery of Big Trajectory Streams: A Hybrid System Design

轨迹流由大量带有时间戳的空间数据组成，这些数据不断从不同的地理分布源生成，例如GPS定位、传感器探测、移动的手机监控和许多智能设备。从轨迹流中发现模式具有广泛的应用，例如公共应急响应，兴趣点，推荐，健康监测，安全监管，车队管理等。为了计算数据挖掘或机器学习模型，传统方法采用集中式方法，需要将轨迹采样数据聚集在单个机器上或数据中心中。然而，这种集中式方法在（1）可扩展计算方面具有限制。轨迹挖掘任务要求计算资源水平扩展。即使轨迹数据集可以在集中式计算环境中加载，在挖掘算法的迭代步骤中对轨迹数据集的转换也可以生成比原始数据大得多的数据。另一个限制是（2）隐私保护。轨迹挖掘不可避免地需要从分散的数据源收集、传输和聚合轨迹数据。但是，数据共享应在不损害用户隐私的情况下进行。很多工作都集中在集中式设置上，其中可信的数据管理者位于聚合器和数据源之间，具有扰动噪声以保证隐私。这种集中式方法容易受到攻击，其中对手可以通过攻击可信数据管理者来访问真正的未受保护的数据。 本研究的长期目标是定义非集中式范式，用于集体共享轨迹数据，并具有隐私保护和可扩展的有意义模式发现。该研究计划的短期目标是在五年内研究一种混合系统设计，该系统能够在保证本地隐私的情况下分散和集体释放轨迹流。本研究围绕三个主要研究课题展开。主题1：分布式并行计算环境下的轨迹分割、特征表示和半监督分类模型。主题二：探讨集体弹道数据分享与局部微分。研究的重点是预算分配算法，需要较少的信息交换，同时保持可比的效用。主题3：通过提高数据局部性和负载再平衡，扩展轨迹流挖掘，减少端到端延迟。重新平衡工作负载需要保证新分区的并行精度。由于与加拿大的ICT公司（包括Ciena，Ubisoft，Neubla AI和Videotron）建立了合作，本研究能够从真实案例中推导出实验场景来验证假设和系统设计。

Trajectory streams consist of big volumes of time-stamped spatial data that are constantly generated from diverse and geographically distributed sources such as GPS positioning, sensors probing, mobile phones monitoring and many smart devices. Discovering patterns from trajectory streams has broad applications such as public emergency responses, point of interests, recommendation, health monitoring, safety regulation, fleet management and etc. To compute data mining or machine learning models, traditional methods adopt a centralized approach that requires the trajectory sampling data be aggregated on a single machine or in a datacenter. This centralized approach, however, has limitation on (1) scalable computing. The trajectory mining tasks demand on horizontal scaling of computing resources. Even if the trajectory dataset could be loaded in a centralized computing environment, the transformation over trajectory datasets among iterative steps of mining algorithms can generate data with much larger magnitude than the original. Another limitation is (2) privacy protection. Trajectory mining inevitably requires collection, transmission, and aggregation of trajectory data from de-centralized data sources. However, data should be shared without jeopardizing users privacy. Much work focuses on centralized setting where a trusted data curator located between the aggregator and data sources with perturbed noise to guarantee privacy. This centralized approach is vulnerable to attacks where an adversary may access the true unprotected data by attacking the trusted data curator. The long term goal of this research is defining non-centralized paradigm for collective sharing of trajectory data with privacy protection and scalable discovery of meaningful patterns. This research program has the short term goal in five years to investigate a hybrid system design that enables decentralized and collective releasing of trajectory streams with local privacy guarantee. This research focuses on three major research topics. Topic 1: Trajectory segmentation, feature representation and semi-supervised classification model in distributed and parallel computing environment. Topic 2: investigate collective trajectory data sharing with local differential. The research focuses on the budget allocation algorithms that require less information to be exchanged while retain the comparable utility. Topic 3: scaling the trajectory stream mining and reduce the end-to-end delay by means of improving data locality and rebalancing workload at runtime. Rebalancing the workload needs to assure the precision under parallelism of the new partition. Thanks to collaboration established with ICT companies in Canada including Ciena, Ubisoft, Neubla AI and Videotron, this research is able to derive experimental scenarios to validate assumptions and the system design from real-word cases.