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

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

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.