Algorithms for Summarizing, Representing, and Analyzing Trajectories of Moving Objects

时空轨迹数据集的移动对象的分析正在迅速成为一个重要的研究领域，高效的几何算法是必要的。具有GPS功能的设备和运动跟踪传感器的成本和尺寸的降低已经导致用于记录运动的设备的数量和使用的巨大增加，从而通过各种应用迅速产生对轨迹集的处理和分析的广泛需求：动物的迁移模式;商用车辆的车队;骑自行车者、徒步旅行者和跑步者在小径上的路线;分析购物者在商场中的运动的商业利益;用于创建视频游戏或计算机动画的运动捕捉数据;在接收紧急消息时对手机用户的运动的政府分析;对玩家跟踪数据的体育分析;用于支持这些任务的有效算法的开发是必不可少的，并且将代表将直接有益于涉及运动的广泛应用的显著贡献。 大多数现有的几何优化算法对静态输入进行操作，例如，这同样适用于大多数现有的中心性、数据深度、位置估计器和聚类目标函数的概念。受当今涉及运动的众多应用以及记录运动的方法的易用性、普遍性和多样性的启发，所提出的研究旨在开发用于简化、总结、表示和分析移动输入的有效算法。具体而言，该算法对表示随时间推移移动通过空间的对象的位置的时空轨迹集进行操作。拟议的研究计划的目标包括： 1.识别用于时空轨迹数据的良好位置估计器和汇总统计，包括定义有效汇总和表示运动的输入集合的中心性和数据深度的新度量，沿着用于计算这些的有效算法，以及 2.定义适当的目标函数，用于基于移动对象的时空轨迹的相似性将移动对象的集合划分为簇，沿着高效的计算算法。 更广泛的目标是开发新的思想和新的技术，以有效地总结，表示和分析运动和运动对象组的轨迹。 拟议的研究将涉及培训大约15名HQP，他们将发展与加拿大各种行业相关的专业知识，这些行业的业务涉及轨迹数据和运动。

The analysis of spatio-temporal trajectory data for sets of moving objects is quickly becoming an important area of research for which efficient geometric algorithms are necessary. The decreased cost and size of GPS-enabled devices and motion-tracking sensors has led to a tremendous increase in the number and use of devices for recording motion, quickly creating extensive demand for processing and analysis of sets of trajectories by a variety of applications: migratory patterns of animals; fleets of commercial vehicles; routes of cyclists, hikers, and runners on trails; commercial interests in analyzing the motion of shoppers in malls; motion-capture data used in the creation of video games or computer animation; government analysis of the movement of cell-phone users upon receiving an emergency message; sports analytics of player tracking data; etc. The development of efficient algorithms for supporting these tasks is essential, and would represent a significant contribution that would directly benefit a wide range of applications that involve motion. Most existing geometric optimization algorithms operate on static input, e.g., on a given set of points, line segments, polyhedra, etc. The same holds for most existing notions of centrality, data depth, location estimators, and clustering objective functions. Motivated by the multitude of present-day applications involving motion, and the ease, prevalence, and variety of methods for recording motion, the proposed research seeks to develop efficient algorithms for simplifying, summarizing, representing, and analyzing moving input. Specifically, the algorithms operate on sets of spatio-temporal trajectories representing the positions of objects moving through space over time. The proposed research program's objectives include: 1. Identifying good location estimators and summary statistics for spatio-temporal trajectory data, including defining new measures of centrality and data depth that effectively summarize and represent the input set of motions, along with efficient algorithms for computing these, and 2. Defining appropriate objective functions for partitioning sets of moving objects into clusters based on the similarities of their spatio-temporal trajectories, along with efficient algorithms for computation. The broader goal is to develop new ideas and new techniques to efficiently summarize, represent, and analyze motion and the trajectories of groups of moving objects. The proposed research will involve training approximately 15 HQP who will develop expertise relevant to the large variety of Canadian industries whose business involves trajectory data and motion.