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.