III: Small: Discovering Hidden Semantics from Spatio-temporal Sensed Data

全球定位系统设备的日益普及以及监控和跟踪机制的广泛部署，包括摄像机、移动电话、活动跟踪器和路边传感器，正在创建非常庞大的时空数据集，这些数据集具有极其丰富的语义。这些数据嵌入了大量关于移动物体行为的高级信息，以及它们与环境中的物体以及彼此之间的相互作用。诸如范围查询和连接之类的标准查询可能足以提取空间数据的语义，但对时空语义的固有丰富性却不够公正。该项目将开发专门针对从轨迹数据集中提取语义和行为信息的方法。例如，对一个区域进行监视的移动物体将在监视期间保持在该区域附近。使用标准方法很难检测到这种行为：范围查询要求用户指定监视的空间和时间范围，而实际上，目的是确定两者。拟议的工作有许多国家安全应用，包括执法、监视和安全监测，以及社会和商业应用，如社交网络、链接分析和流行病学。开发的解决方案将增加时空数据的效用，特别是对于需要调查探索的任务。该项目解决了时空领域的一类新问题，这些问题提出了一系列新的技术挑战：首先，它研究了引发移动物体与其环境之间交互语义的查询。其次，它研究引发交互语义的查询，例如移动对象本身之间的潜在会议。第三，它探索了现实环境中的此类查询，其中可用的数据是不完整和不精确的。第一类查询的例子包括“驻留区域”查询，它探索移动物体和环境中物体之间的时空接近性，并应用于通过移动物体检测区域监视。该项目还将解决说明上述第二和第三个挑战的“秘密”查询。当运动物体的轨迹不完全或不精确时，这样的查询返回它们之间可能的相遇点。提出的工作还探讨了复杂的时空“可达性”查询，它通过中介引发对象之间可能的交互。最后，考虑到时空数据集的巨大规模，该项目旨在提供可扩展的解决方案。一个基本的问题是如何有效地索引轨迹数据。虽然在这个领域已经有了各种各样的过去的工作，这个项目提出了第四个挑战：希尔伯特曲线可以用来索引轨迹吗？空间填充曲线（sfc）可以降低空间维数，在空间对象索引中具有优势。在过去的研究中，sfc主要用于多维点的索引或任意对象的排序；由于该项目旨在克服的各种挑战，它们尚未直接用于轨迹索引。项目网站（http://www.cs.ucr.edu/~tsotras/semtraj/index.html）将提供对项目结果的访问，包括所开发算法的源代码和相关数据。

The increasing ubiquity of Global Positioning System devices and the widespread deployment of monitoring and tracking mechanisms, including video cameras, cellular phones, activity trackers and roadside sensors are creating very large spatio-temporal datasets that are extremely rich in semantics. Such data embed a great deal of high-level information on the behavior of moving objects as well their interactions with objects in the environment and with each other. Standard queries such as range queries and joins may be adequate for extracting the semantics of spatial data, but do scant justice to the inherent richness of spatio-temporal semantics. This project will develop approaches aimed specifically at extracting semantic and behavioral information from trajectory datasets. For instance, a moving object conducting surveillance on a region will remain in the vicinity of the region for the duration of surveillance. Detecting this behavior is difficult with standard approaches: a range query would require the user to specify the spatial and temporal ranges of surveillance, when the intent is, in fact, to determine both. The proposed work has many national security applications, including law enforcement, surveillance and security monitoring as well as social and commercial applications, such as in social networks, link analysis and epidemiology. The solutions developed will increase the utility of spatio-temporal data, specifically for tasks that require investigative exploration.This project addresses a novel class of problems in the spatio-temporal domain, which raise a novel set of technical challenges: First, it studies queries that elicit the semantics of interactions between moving objects and their environment. Second, it studies queries eliciting the semantics of interactions, such as potential meetings between moving objects themselves. Third, it explores such queries in the real-world contexts, where the available data is incomplete and imprecise. Examples of the first class of query include "dwell regions" queries, which explore spatio-temporal proximity between moving objects and objects in the environment, with applications to detection of surveillance of regions by moving objects. The project will also address "conclave" queries that illustrate the second and third challenges above. Such queries return possible meeting points between moving objects when their trajectories are not known fully or precisely. The proposed work also explores complex spatio-temporal "reachability" queries, which elicit possible interactions between objects via intermediaries. Finally, given the sheer magnitude of spatio-temporal datasets, this project aims to provide solutions that scale. A basic question is then how to efficiently index trajectory data. While there have been various past works in this domain, this project proposes a fourth challenge: can Hilbert Curves been used to index trajectories? Space filling curves (SFCs) have been shown to be advantageous in indexing spatial objects since they can reduce the space dimensionality. In past research, SFCs have been mainly used to index multidimensional points or order arbitrary objects; they have not though been directly used for indexing trajectories due to various challenges that this project aims to overcome. The project web site (http://www.cs.ucr.edu/~tsotras/semtraj/index.html) will provide access to the project results, including source code of the developed algorithms and relevant data.