Survey of Spatio-Temporal Databases

Spatio-temporal databases aim to support extensions to existing models of Spatial Information Systems (SIS) to include time in order to better describe our dynamic environment. Although interest into this area has increased in the past decade, a number of important issues remain to be investigated. With the advances made in temporal database research, we can expect a more unified approach towards aspatial temporal data in SIS and a wider discussion on spatio-temporal data models. This paper provides an overview of previous achievements within the field and highlights areas currently receiving or requiring further investigation.     

Classes of Spatio-Temporal Objects and their Closure Properties

We present a data model for spatio-temporal databases. In this model spatio-temporal data is represented as a finite union of objects described by means of a spatial reference object, a temporal object and a geometric transformation function that determines the change or movement of the reference object in time.We define a number of practically relevant classes of spatio-temporal objects, and give complete results concerning closure under Boolean set operators for these classes. Since only few classes are closed under all set operators, we suggest an extension of the model, which leads to better closure properties, and therefore increased practical applicability. We also discuss a normal form for this extended data model.     

Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data

The filtering method considered in this paper is based on approximation of a spatial object in d-dimensional space by the minimal convex polyhedron that encloses the object and whose facets are normal to preselected axes. These axes are not necessarily the standard coordinate axes; furthermore, their number is not determined by the dimension of the space. We optimize filtering by selecting optimal such axes based on a preprocessing analysis of stored objects or a sample thereof. The number of axes selected represents a trade-off between access time and storage overhead, as more axes usually lead to better filtering but require more overhead to store the associated access structures. We address the problem of minimizing the number of axes required to achieve a predefined quality of filtering and the reverse problem of optimizing the quality of filtering when the number of axes is fixed. In both cases we also show how to find an optimal collection of axes. To solve these problems, we introduce and study the key notion of separability classification, which is a general tool potentially useful in many applications of a computational geometry flavor. The approach is best suited to applications in which the spatial data is relatively static, some directions are more dominant than others, and the dimension of the space is not high; maps are a prime example.     

Continuous Query Processing of Spatio-Temporal Data Streams in PLACE

The tremendous increase in the use of cellular phones, GPS-like devices, and RFIDs results in highly dynamic environments where objects as well as queries are continuously moving. In this paper, we present a continuous query processor designed specifically for highly dynamic environments (e.g., location-aware environments). We implemented the proposed continuous query processor inside the PLACE server (Pervasive Location-Aware Computing Environments); a scalable location-aware database server developed at Purdue University. The PLACE server extends data streaming management systems to support location-aware environments. These environments are characterized by the wide variety of continuous spatio-temporal queries and the unbounded spatio-temporal streams. The proposed continuous query processor includes: (1) New incremental spatio-temporal operators to support a wide variety of continuous spatio-temporal queries, (2) Extended semantics of sliding window queries to deal with spatial sliding windows as well as temporal sliding windows, and (3) A shared-execution framework for scalable execution of a set of concurrent continuous spatio-temporal queries. Experimental evaluation shows promising performance of the continuous query processor of the PLACE server. This work was supported in part by the National Science Foundation under Grants IIS-0093116, IIS-0209120, and 0010044-CCR.     

Efficient Querying and Animation of Periodic Spatio-Temporal Databases

We propose a representation of spatio-temporal objects with continuous and cyclic or acyclic periodic movements. We also describe an extended relational algebra query language for databases with such objects. We show that the new spatio-temporal databases are closed under the extended relational algebra queries, and each fixed relational algebra query can be evaluated in PTIME in the size of the input database.     

Constraint-based Interoperability of Spatiotemporal Databases*

We propose constraint databases as an intermediate level facilitating the interoperability of spatiotemporal data models. Constraint query languages are used to express translations between different data models. We illustrate our approach in the context of a number of temporal, spatial, and spatiotemporal data models.     

时空推理研究进展

与时态和空间有关的推理问题是人工智能研究中重要的组成部分,在地理信息系统、时空数据库、CAD/CAM等领域有着重要应用.从本体、表示模型和推理方法3个方面分别介绍了时态推理和空间推理的发展,并在此基础上综述了时空结合推理的研究进展.讨论了目前时空推理领域存在的问题,并指出了今后的发展方向.     

一种预测性连续时空区域查询处理方法

预测性连续时空区域查询在用户指定的时间范围期间持续地返回给定未来查询时间范围期间将出现在查询区域的移动对象。论文提出了一种预测性连续时空区域查询处理方法,设计了支持连续查询处理的两种索引结构。移动对象索引用于记录移动对象不断更新的位置信息,它用于支持查询的首次处理。连续查询索引结构用于记录所有查询结果可能受到移动对象位置变化影响的连续查询,它用于支持连续查询处理。实验表明,论文提出的方法能够有效地提高处理大量连续查询的效率。     

时空特性约束下多源空间融合数据挖掘仿真

多源空间融合可以将不同信息存储系统的数据整合,用较少的人力、物力资源完成大量工作,但是融合过程中,难免会出现数据损耗,导致融合后部分数据不能读取,有效数据与损坏信息混合存放,较难区分,如何方便得到空间融合后有效数据是亟待解决的重要问题。提出一种时空特性约束下多源空间融合数据挖掘。分析多源空间的时间和空间特性,确定约束条件,将多源空间向量集成,建立空间融合规则,在减少损耗的基础上,分别融合多源空间内的几何方位与空间要素,最后构建EM数据挖掘模型,根据数据质量评价指标挖掘出有有效信息。仿真结果证明,时空特性约束下多源空间融合数据挖掘能够稳定、有效地准确挖掘出多源空间融合后的有效数据,实现资源准确共享。     

时空数据发布中的隐式隐私保护

随着大数据时代的到来,大量的用户位置信息被隐式地收集.虽然这些隐式收集到的时空数据在疾病传播、路线推荐等科学、社会领域中发挥了重要的作用,但它们与用户主动发布的时空数据相互参照引起了大数据时代时空数据发布中新的个人隐私泄露问题.现有的位置隐私保护机制由于没有考虑隐式收集的时空数据与用户主动发布的位置数据可以相互参照的事实,不能有效保护用户的隐私.首次定义并研究了隐式收集的时空数据中的隐私保护问题,提出了基于发现-消除的隐私保护框架.特别地,提出了基于前缀过滤的嵌套循环算法用于发现隐式收集的时空数据中可能泄露用户隐私的记录,并提出基于频繁移动对象的假数据添加方法消除这些记录.此外,还分别提出了更高效的反先验算法和基于图的假数据添加算法.最后,在若干真实数据集上对提出的算法进行了充分实验,证实了这些算法有较高的保护效果和性能.     

基于时空数据的驻留行为特征可视分析

随着智慧城市的快速发展,大量商业场所每天会产生海量的驻留行为数据,然而传统驻留行为数据分析方法难以克服数据稀疏性问题,并且对于时空伴随关系的发现准确度也较低。根据驻留行为数据特征和可视分析任务,设计一种交互式的可视分析系统。对原始数据进行处理,提取相关的时空特征并发现用户伴随关系。使用改进的可变滑动窗口算法,并结合可视分析技术,设计用户关系图、时间甘特图、多变量表达的示意性地图、径向条形图、日历热力图等多种视图,实现对驻留场所的流量分布、用户来源等特征的多时段可视分析。应用两个真实数据集进行案例分析,并对发现的行为模式及对应现象进行解释说明,证明了该系统的可用性和拓展性,并表明其可实现团体出行特征和场所流量分析等系统级应用,为相关经营性商业场所提供合理化建议及辅助决策支持。     

一种基于数据融合和方法融合的时空综合预测算法

时空数据挖掘是数据挖掘中的重要研究内容,其中时空预测的应用领域最为广泛.针对目前时空预测方法中的不足,提出了一种基于数据融合和方法融合的时空综合预测算法.该方法首先采用统计学原理对目标对象本身的时序进行预测;然后通过神经网络解算相邻对象的空间影响,继而对混合数据序列使用时空自回归预测模型;最后使用线性回归将单个的时间预测、空间预测和时空预测有效地融合在一起,得到综合预测结果.应用该方法预测铁路客流,突破了传统铁路客流预测方法的局限,实验结果表明了算法的有效性.     

Beyond Schema Versioning: A Flexible Model for Spatio-Temporal Schema Selection

Schema versioning provides a mechanism for handling change in the structure of database systems and has been investigated widely, both in the context of static and temporal databases. With the growing interest in spatial and spatio-temporal data as well as the mechanisms for holding such data, the spatial context within which data items are formatted also becomes an issue. This paper presents a generalized model that accommodates temporal, spatial and spatio-temporal schema versioning within databases.     

Development of a Process-Based Model for Dynamic Interaction in Spatio-Temporal GIS

Spatial processes and their interactions are fundamental in explaining the complex behavior of real world systems. Current GIS describes space based on map layers and by means of either the vector or raster model. However, current vector and raster models cannot dynamically maintain topological relationships between spatial entities while these are changing rapidly in the real world. This makes current GIS incapable of modeling dynamic spatial processes. In this paper, the development of a process-based model is described. The model is developed based on spatial system theory and the Voronoi spatial model. First, the paper discusses spatial system theory, which forms the theoretical background for the model. Second, the Voronoi spatial model is adopted to describe spatial processes; it is more efficient than conventional vector and raster models. Third, the paper presents the capabilities of the model in one application.     

时空推理中自动生成复合表的通用算法

时空推理是面向时间/空间问题的研究领域,在人工智能(如语义Web、机器人导航、自然语言处理、物理过程的定性模拟和常识推理等)和其他领域有着广泛的应用前景.复合推理在时空推理中具有重要作用,是约束满足问题等其他定性推理的基础.复合推理是由R(a,b)和R(b,c)决定R(a,c)的一种演绎推理.一般将关系复合结果放在复合表中备查.但目前复合表的建立需要逐个模型进行手工推导,少数模型给出了独立的复合表生成算法,没有适合多种时空关系模型、能自动生成复合表的通用算法.为此,提出了一种能自动生成复合表的通用算法.首先,给出了基于空间划分的通用时空表示模型.在此基础上,提出了基于场景检测的通用复合表生成算法.通过理论分析和对RCC、宽边界、区间代数等20余种典型时空模型的测试,证明了本算法对于所有以精确区域(或区间)为基础的确定、不确定时空模型均能正确快速地生成复合表.     

面向出租车需求预测的多因素时空图卷积网络

精确地预测出租车需求,有助于缩短司机和乘客的等待时间,缓解交通拥堵状况。然而,目前的研究工作大都忽略了出租车历史流入量以及不同区域间潜在的空间依赖关系对出租车需求的影响。鉴于此,综合考虑多个影响出租车需求的因素,建立多因素时空图卷积网络模型（MFSTGCN）,期望精确地预测出租车需求。具体地,MFSTGCN模型设计4个组件,分别建模出租车需求对临近时刻需求序列、日需求序列、出租车历史流入量序列的时间依赖性以及不同区域间的潜在空间依赖性。组件通过时空卷积块捕捉不同因素下的潜在时空表达。为了证明MFSTGCN模型的有效性,与交通预测常用的五种基准模型进行比较,并利用RMSE、MAE和MAPE三个指标进行评估。实验结果表明,融合多因素的MFSTGCN模型能够更精确地预测出租车需求。     

到达数据中时空异常聚簇发现

在时空数据中有一类表示用户在某一时间到达某一地点的数据——到达数据,到达数据可以是社交网站的签到数据、轨迹数据中的停留点及公共交通中乘客抵达的位置数据,这些数据的聚簇可以反映用户的聚集行为.基于到达数据,提出一类新的时空数据查询——时空异常聚簇发现.将到达数据进行周期性划分,通过时空聚类算法对一个时间段的数据进行聚类,比较不同时间段内聚簇的差异度,发现具有最大簇异常度的前k个簇.通过该查询发现的时空异常聚簇可以应用于城市安全管理、基于位置的服务和交通调度等方面.定义了异常簇查询模型,提出了针对任意形状聚簇的簇差异度度量,将异常簇查询转化为二分图最大匹配问题,对二分图构建与匹配进行了优化并提出了高效的查询算法.利用真实数据集进行了充分实验,验证了查询结果的实际意义,评估了所提出的各查询算法在不同参数设置下的查询效率.     

An Application of Advanced Spatio-Temporal Formalisms to Behavioural Ecology

There is great potential for the development of many new applications using data on mobile objects and mobile regions. To promote these kinds of applications advanced data management techniques for the representation and analysis of mobility-related data are needed. Together with application experts (behavioural ecologists), we investigate how two novel data management approaches may help. We focus on a case study concerning the analysis of fauna behaviour, in particular crested porcupines, which represents a typical example of mobile object monitoring. The first technique we experiment with is a recently developed conceptual spatio-temporal data modelling approach, MADS. This is used to model the schema of the database suited to our case study. Relying on this first outcome a subset of the problem is represented in the logical language MuTACLP. This allows us to formalise and solve the queries which enable the behavioural ecologists to derive crested porcupines behaviour from the raw data on animal movements. Finally, we investigate the support from a commercial Geographic Information System (GIS) for the analysis of spatio-temporal data. We present a way to integrate MuTACLP and a GIS, combining the advantages of GIS technology and the expressive power of MuTACLP.

Making Space for Time: Issues in Space-Time Data Representation

Even with much activity over the past decade, including organized efforts on both sides of the Atlantic, the representation of both space and time in digital databases is still problematic and functional space-time systems have not gone beyond the limited prototype stage. Why is this the case? Why did it take twenty years from the first GIS for the for representation and analysis in the temporal, as well as the spatial dimension, to begin? I explore the answers to these questions by giving a historical overview of the development of space-time representation in the geographic information systems and database communities and a review of the most recent research. Within the context of this perspective, I also question what seems to be a spirit of self-accusation in which the lack of functional space-time systems has been discussed in the literature and in meetings of GIS researchers. I close by offering my own interpretation of current research issues on space-time data models and languages.     

统一时空电网数据模型与访问技术

在电网的地理信息系统发展过程中,存在着多种不同的文件或空间数据库格式,也产生了大量的电网时空数据.为解决数据集中或各个系统间数据交互时,面临的异构数据问题以及时空数据应用问题,特提出统一时空电网数据模型与访问技术.本文从实际应用出发,利用元数据思想及软件插件模式,从数据及访问层面解决了异构数据和时态数据的使用.通过应用证明,采用统一空间数据模型与访问技术方式,能够有效地减少数据准备、系统开发的工作量,并且可以整合利用不同数据源各自的优点.