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.