NeTS: Small: Geometric and Topological Analysis on Trajectory Sensing: Collection, Classification and Anonymization

移动的设备和系统的成熟提供了前所未有的机会来收集关于所有尺度的真实的世界人体运动的大量数据。这些数据集中包含的丰富知识可以在许多领域产生巨大影响，从交通到医疗保健，从土木工程到能源管理，从电子商务到社交网络。虽然这些应用正在改变范式，但最近的研究表明，轨迹数据可能会在泄露个人敏感信息（如经常访问的位置或社会关系）时引发严重的隐私问题。这些问题成为利用这些数据集的主要障碍。 本项目系统地研究了轨迹数据的匿名化问题，从底层的轨迹感知和数据采集，到中间层的轨迹表示和匿名，再到应用层的匿名轨迹数据如何使用。由于轨迹是带有时间戳的点序列，在这个项目中，新的几何和拓扑算法，直接工作在分布式传感器收集的轨迹被开发用于实现的目标。对这种分散的传感器进行加密，以确保没有敏感信息被释放。智力贡献在于以下几个方面。1)轨迹的拓扑表示，即，采用轨迹如何绕过域中的障碍物和地标。拓扑表示是紧凑的和描述性的，引入新的离散和组合问题进行研究。2)提出了一种新的分布式传感器直接学习、分类和比较目标轨迹的拓扑类型的框架，该框架利用代数拓扑中的调和一形式和Hodge分解。新的框架可以大大降低网络内的通信成本，同时从传感和数据收集的一开始就保持用户隐私的要求。3)通过改变将时间戳点连接到轨迹的方式，通过调整拓扑分辨率以达到数据匿名性和实用性之间的平衡，以及通过感测和记录随机散列数据来回答流行的轨迹查询，开发了一系列使用不同思想的匿名化算法。4)轨迹数据集通常是巨大的，因此用于处理大规模轨迹数据集的算法在集中式和分散式设置中被开发。

The maturing of mobile devices and systems provide an unprecedented opportunity to collect a large amount of data about real world human motion at all scales. The rich knowledge contained in these data sets can have a huge impact in many fields ranging from transportation to health care, from civil engineering to energy management, from e-commerce to social networking. While the applications are paradigm-transforming, recent studies show that the trajectory data can raise serious privacy concerns in revealing personally sensitive information such as frequently visited locations or social ties. These concerns become the major hurdle in utilizing these data sets. This project systematically studies the issue of anonymizing trajectory data, from the bottom layer of trajectory sensing and data collection, to the middle layer of trajectory representation and anonymity, to the application layer of how the anonymized trajectory data can be used.By the nature of trajectories as being time stamped sequence of points, in this project novel geometric and topological algorithms that directly work on distributed sensors collecting the trajectories are developed for achieving the objective. Queries to such decentralized sensors are made to ensure no sensitive information is released. The intellectual contribution lies in the following aspects. 1) The topological representation of trajectories, i.e., how trajectories pass around obstacles and landmarks in the domain is adopted. The topological representation is compact and descriptive, introducing novel discrete and combinatorial problems to study. 2) A novel framework is developed for distributed sensors to directly learn, classify and compare the topological types of the target trajectories, using harmonic one-forms and Hodge decomposition from algebraic topology. The new framework can substantially reduce the communication cost within the network, while maintaining the requirement of user privacy from the very beginning of sensing and data collection. 3) A family of anonymization algorithms using different ideas are developed, by altering the way to connect the time-stamped points into trajectories, by adjusting the topological resolution to reach a balance between data anonymity and utility, and by sensing and recording randomized hash data to answer popular trajectory queries. 4) The trajectory data sets are often huge, so algorithms for handling large scale trajectory data sets are developed in both centralized and decentralized settings.