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.