移动空间数据类型和操作的初步研究

1 引言移动空间对象是随时间变化的空间数据,由时空数据库(Spatio-Temporal Databases)进行管理和处理。一个空间点可能随时间而改变其位置,为了完整地反映该点的信息,数据库中应该存储该点的全部历史信息,这个空间对象就是一个移动点。同理,一个区域也可能随时间移动、扩大或缩小。时空现象在现实生活中非常普遍,如飞机航行时随着时间变化而改变它的空间位置,这飞机就是一个移动点;当森林中某处发生火灾时,火灾区就是一个空间对象:区域。该区域可能     

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.     

时空数据库中数据建模的研究

研究了时空数据库中的时空建模技术。早期表示时空信息的数据模型通常用基于几何学的空间对象来表示实体，重要的特性都用空间对象的属性来表示。时态信息可以与基于时间戳的独立层次相关联，也可以与独立的空间对象相关联。随着时空建模的进一步发展，出现了面向对象的数据模型和基于事件的数据模型。综合研究了这些典型的时空数据模型，讨论了它们的应用及时空分析建模的作用。此外介绍了针对移动对象的数据类型的建模方法，以及在时空分析数据库管理系统STADBS中，基于Realms的二级平衡二叉树的时空数据模型。     

Temporal association algebra: a mathematical foundation forprocessing object-oriented temporal databases

This paper describes an object-oriented temporal association algebra (called TA-algebra) which is intended to serve as a formal foundation for supporting a pattern-based query specification and processing paradigm. Different from the traditional table-and-attribute-based paradigm, the pattern-based paradigm views the intension of an object-oriented temporal database as a network of object classes interconnected by different association types and its extension as a network of associated temporal object instances. Consistent with this view, queries can be specified in terms of patterns of temporal object associations or nonassociations (i.e., linear, tree and network structures of object classes/objects with logical AND and OR branches). TA-algebra provides a set of algebraic operators for processing these patterns and allows the direct and/or indirect associations and/or nonassociations among temporal object instances to be more explicitly represented and maintained during processing than the traditional tabular representation of temporary or final query results. TA-algebra operators are based on time-interval and valid-time semantics and they preserve the closure property. The algebra is capable of operating on heterogeneous as well as homogeneous patterns of object associations. Both homogeneous and heterogeneous patterns are decomposed into a set of primitive temporal pattern instances for uniform treatment. This paper formally defines the TA-algebra operators and their mathematical properties. The applications of these operators in query decomposition and processing are illustrated by examples     

Fast Nearest-Neighbor Query Processing in Moving-Object Databases

A desirable feature in spatio-temporal databases is the ability to answer future queries, based on the current data characteristics (reference position and velocity vector). Given a moving query and a set of moving objects, a future query asks for the set of objects that satisfy the query in a given time interval. The difficulty in such a case is that both the query and the data objects change positions continuously, and therefore we can not rely on a given fixed reference position to determine the answer. Existing techniques are either based on sampling, or on repetitive application of time-parameterized queries in order to provide the answer. In this paper we develop an efficient method in order to process nearest-neighbor queries in moving-object databases. The basic advantage of the proposed approach is that only one query is issued per time interval. The time-parameterized R-tree structure is used to index the moving objects. An extensive performance evaluation, based on CPU and I/O time, shows that significant improvements are achieved compared to existing techniques.     

Feature-based 3D non-manifold freeform object construction

This paper presents a novel technique for modeling a 3D non-manifold freeform model around a 3D reference model. To represent both the design abstractions and the incomplete topological information, a new non-manifold data structure is first defined. Our data structure embodies the functional vitalities of both the boundary representation data structure and the complex-based data structure. Along with our data structure, a set of topological operators is defined to manipulate the entities in the data structure. Based on the non-manifold data structure and the topological operators, we develop a technique to construct 3D freeform objects around a reference model. Intuitive 2D sketches are adopted to specify the detailed profile of the object constructed. The construction method is feature-based – every reference model has pre-defined features, and the feature template of the constructed object is related to the features of the reference model by feature node encoding. Therefore, the surfaces derived from one reference model can be regenerated automatically on another reference model with the same features. The geometry coverage of our geometric modeling approach includes both manifold and non-manifold 3D freeform objects.     

An Algebra for PowerPoint Sources

There are now millions of PowerPoint documents available within corporate intranets and/or over the Internet. In this paper, we develop a formal model of PowerPoint databases. We propose a relational style algebra called pptA (PowerPoint Algebra) to query PowerPoint databases. The algebra contains some new operators (such as the APPLY operator that changes properties of objects, slides and presentations) as well as interesting twists on relational operators (e.g. join and cartesian product allow different entities being joined together to share attributes whose values may be merged). We prove a set of equivalence results within this algebra. We have implemented a version of pptA—the paper provides a cost model and experimental results on the conditions under which these equivalences are useful.     

Modeling Motion Relations for Moving Objects on Road Networks

In this paper, a basic set of motion relations capturing specific prototypical movements of vehicles on US road networks are introduced. Vehicle positional data collected from a geosensor network and stored in a spatio-temporal database serve as the basis for computing the relations that include isBehind, inFrontOf, driveBeside, and passBy. Relational SQL queries are used to derive the relations, returning information about pairs of moving objects and their relative positions. This information provides additional user contexts for binary vehicle patterns relative to a reference object. A framework for the kinds of moving objects that participate in these relations is supplied through an associated TransportationDevice ontology. Depending on the class of moving object, a relation such as isBehind captures scenarios that are facilitating or inhibiting with respect to the movement of traffic. For example, if a police car is known to be behind an automobile, the automobile typically slows to correspond with the legal speed limit. In this work, we show how linking the spatio-temporal database to an ontology can augment and extend the motion relation information, providing multi-granular perspectives of moving vehicles.

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.     

Continuous aggregate nearest neighbor queries

This paper addresses the problem of continuous aggregate nearest-neighbor (CANN) queries for moving objects in spatio-temporal data stream management systems. A CANN query specifies a set of landmarks, an integer k, and an aggregate distance function f (e.g., min, max, or sum), where f computes the aggregate distance between a moving object and each of the landmarks. The answer to this continuous query is the set of k moving objects that have the smallest aggregate distance f. A CANN query may also be viewed as a combined set of nearest neighbor queries. We introduce several algorithms to continuously and incrementally answer CANN queries. Extensive experimentation shows that the proposed operators outperform the state-of-the-art algorithms by up to a factor of 3 and incur low memory overhead.     

Spatio-Temporal Modeling in Video and Multimedia Geographic Information Systems

The geographic application domain includes important information such as design plans, record drawings, photographs, and video data records. The corresponding geographic information systems (GISs) should maintain a specific model for each geographic data modality such as geographic video model for video records. Real-time 3-D geographic information systems provide comprehensive interface to complex and dynamic databases and truly immersive capability for visualizing geographic data. In cases, where information about location of geographic objects is needed at different moments of time, a GIS should process video data that is directly manipulated and retrieved through representation of its spatio-temporal characteristics. In this context, the most advanced multimedia form—digital video, finds an efficient application in GIS for versatile specification of geographic data. In this paper, a model for spatial data evolving with time is introduced in the context of video data manipulation. We designed a model that represents the spatio-temporal continuum among geographic objects in geographic video sequences, or digital video. The model developed here was motivated by the requirements for manipulating, managing, and analyzing geographic data for the necessities of infrastructure management, urban and regional planning, hazard prevention and management, transportation networks, vehicles routing, etc. This model allows the important issues for GIS such as conditions of adjacency (what is next to what), containment (what is enclosed by what), and proximity (how close one geographic object is to another) to be determined. Our model describes the spatial relationships among objects for each key frame in a given video scene, and the temporal relationships of the temporal intervals measuring the validity duration of the spatial relationships spanning over the given key frame. One of the main GIS issues—distance estimation, is solved as quantitative metrics of geographic objects in digital video are easily and precisely specified. This model is a basis for annotation of raw video for subsequent use in geographic video databases and digital libraries that provide access to and efficient storage of large volume of geographic data.     

Continuous visible k nearest neighbor query on moving objects

A visible k nearest neighbor (Vk NN) query retrieves k objects that are visible and nearest to the query object, where “visible” means that there is no obstacle between an object and the query object. Existing studies on the Vk NN query have focused on static data objects. In this paper we investigate how to process the query on moving objects continuously. We propose an effective filtering-and-refinement framework for evaluating this type of queries. We exploit spatial proximity and visibility properties between the query object and data objects to prune search space under this framework. A detailed cost analysis and a comprehensive experimental study are conducted on the proposed framework. The results validate the effectiveness of the pruning techniques and verify the efficiency of the proposed framework. The proposed framework outperforms a straightforward solution by an order of magnitude in terms of both communication and computation costs.     

Spatio-Temporal Data Handling with Constraints

Most spatial information systems are limited to a fixed dimension (generally 2) which is not extensible. On the other hand, the emerging paradigm of constraint databases allows the representation of data of arbitrary dimension, together with abstract query languages. The complexity of evaluating queries though might be costly if the dimension of the objects is really arbitrary. In this paper, we present a data model, based on linear constraints, dedicated to the representation and manipulation of multidimensional data. In order to preserve a low complexity for query evaluation, we restrict the orthographic dimension of an object O, defined as the dimension of the components ^O ₁ ,..., O _n such that O=O ₁×...× O _n. This allows to process queries independently on each component, therefore achieving a satisfying trade-off between design simplicity, expressive power of the query language and efficiency of query evaluation. We illustrate these concepts in the context of spatio-temporal databases where space and time are the natural components. This data model has been implemented in the DEDALE system and a spatio-temporal application, with orthographic dimension 2, is currently running, thus showing the practical relevance of the approach.     

Views as first-class citizens in object-oriented databases

Extensibility and dynamic schema evolution are among the attractive features that lead to the wide acceptance of the object-oriented paradigm. Not knowing all class hierarchy details should not prevent a user from introducing new classes when necessary. Naive or professional users may define new classes either by using class definition constructs or as views. However, improper placement of such classes leads to a flat hierarchy with many things duplicated. To overcome this problem, we automated the process in order to help the user find the most appropriate position with respect to her class in the hierarchy regardless of her knowledge of the hierarchy. The system must be responsible for the proper placement of new classes because only the system has complete knowledge of the details of the class hierarchy, especially in a dynamic environment where changes are very frequent. In other published work, we proved that to define a view it is enough to have the set of objects that qualify to be in a view in addition to having message expressions (possible paths) that lead to desired values within those objects. Here, we go further to map a view that is intended to be persistent into a class. Then we investigate the proper position of that class in the hierarchy. To achieve this, we consider current characteristics of a new class in order to derive its relationship with other existing classes in the hierarchy. Another advantage of the presented model is that views that generate new objects are still updatable simply because we based the creation of new objects on existing identities. In other words, an object participates inside view objects by its identity regardless of which particular values from that object are of interest to the view. Values are reachable via message expressions, not violating encapsulation. This way, actual values are present in only one place and can be updated.Received: 19 March 1999, Accepted: 26 December 2003, Published online: 8 April 2004Edited by: R. Topor.     

On the Generation of Time-Evolving Regional Data*

Benchmarking of spatio-temporal databases is an issue of growing importance. In case large real data sets are not available, benchmarking requires the generation of artificial data sets following the real-world behavior of spatial objects that change their locations, shapes and sizes over time. Only a few innovative papers have recently addressed the topic of spatio-temporal data generators. However, all existing approaches do not consider several important aspects of continuously changing regional data. In this report, a new generator, called generator of time-evolving regional data (G-TERD), for this class of data is presented. The basic concepts that determine the function of G-TERD are the structure of complex 2-D regional objects, their color, maximum speed, zoom and rotation-angle per time slot, the influence of other moving or static objects on the speed and on the moving direction of an object, the position and movement of the scene-observer, the statistical distribution of each changing factor and finally, time. Apart from these concepts, the operation and basic algorithmic issues of G-TERD are presented. In the framework developed, the user can control the generator response by setting several parameters values. To demonstrate the use of G-TERD, the generation of a number of sample data sets is presented and commented. The source code and a visualization tool for using and testing the new generator are available on the Web.¹ Thus, it is easy for the user to manipulate the generator according to specific application requirements and at the same time to examine the reliability of the underlying generalized data model.     

The living in a lattice rule language

This paper presents a rule-based query language for an object-oriented database model. The database model supports complex objects, object identity, classes and types, and a class/type hierarchy. The instances are described by ‘object relations’ which are functions from a set of objects to value sets and other object sets. The rule language is based on object-terms which provide access to objects via the class hierarchy. Rules are divided into two classes: object-preserving rules manipulating existing objects (yielding a new ‘view’ on objects available in the object base) and object-generating rules creating new objects with properties derived from existing objects. The derived object sets are included in a class lattice. We give conditions for whether the instances of the ‘rules’ heads are ‘consistent’, i.e. represent object relations where the properties of the derived objects are functionally determined by the objects.     

SOLE: scalable on-line execution of continuous queries on spatio-temporal data streams

This paper presents the scalable on-line execution (SOLE) algorithm for continuous and on-line evaluation of concurrent continuous spatio-temporal queries over data streams. Incoming spatio-temporal data streams are processed in-memory against a set of outstanding continuous queries. The SOLE algorithm utilizes the scarce memory resource efficiently by keeping track of only the significant objects. In-memory stored objects are expired (i.e., dropped) from memory once they become insignificant. SOLE is a scalable algorithm where all the continuous outstanding queries share the same buffer pool. In addition, SOLE is presented as a spatio-temporal join between two input streams, a stream of spatio-temporal objects and a stream of spatio-temporal queries. To cope with intervals of high arrival rates of objects and/or queries, SOLE utilizes a load-shedding approach where some of the stored objects are dropped from memory. SOLE is implemented as a pipelined query operator that can be combined with traditional query operators in a query execution plan to support a wide variety of continuous queries. Performance experiments based on a real implementation of SOLE inside a prototype of a data stream management system show the scalability and efficiency of SOLE in highly dynamic environments. This work was supported in part by the National Science Foundation under Grants IIS-0093116, IIS-0209120, and 0010044-CCR.     

A Sequence-Based Object-Oriented Model for Video Databases

Structuration, annotation and composition are amidst the most crucial modeling issues that video editing and querying in the context of a database entail. In this paper, we propose a sequence-based, object-oriented data model that addresses them in an unified, yet orthogonal way. Thanks to this orthogonality, the interactions between these three aspects are properly captured, i.e., annotations may be attached to any level of video structuration, and all the composition operators preserve the structurations and annotations of the argument videos. We also propose to query both the structuration and the annotations of videos using an extension of ODMG's OQL which integrates a set of algebraic operators on sequences. The overall proposal is formalized and implemented on top of an object-oriented DBMS.     

基于嵌套语义的约束代数

1 引言约束数据库近期被Kanellakis等提出作为处理空间数据的一般性框架。约束数据库用约束来建模和检索数据。在数据层,约束能用有限的形式来表示可能是无限的关系元组集。例如,约束x~2 y~2≤9表示中心在点(0,0)处,半径为3的圆。在查询语言层,约束通过允许数学计算而增强了简单关系语言的表达能力,同时约束查询语言保留了关系查询语言的所有特征,如封闭性和自底向上求值。关系代数能被扩充来处理约束关系,这个新的代数叫做约束代数CALG。     

时空数据库中多个最近邻对象的查询算法

在时空数据库中，最近邻查询用于对某个查询对象，在被查询对象中找出离它最近的一个或多个对象。该文在TPR树这一时空索引的基础上，提出了一种高效的最近邻查询算法，能够支持移动对象的多个最近邻对象的查询，并在性能上也有所提高。