Advances in Spatial and Temporal Databases

In moving object databases, object locations in some multidimensional space depend on time. Previous work focuses mainly on moving object modeling (e.g., using ADTs, temporal logics) and ad hoc query optimization. In this paper we investigate logical properties of moving objects in connection with queries over such objects using tools from differential geometry. In an abstract model, object locations can be described as vectors of continuous functions of time. Using this conceptual model, we examine the logical relationships between moving objects, and between moving objects and (stationary) spatial objects in the database. We characterize these relationships in terms of position, velocity, and acceleration. We show that these fundamental relationships can be used to describe natural queries involving time instants and intervals. Based on this foundation, we develop a concrete data model for moving objects which is an extension of linear constraint databases. We also present a preliminary version of a logical query language for moving object databases.

Moving object databases are becoming more popular due to the increasing number of application domains that deal with moving entities and need to pose queries. So far implementations of such systems have been rather weak and certainly not at industrial strength level. In this paper we define a concise data model and a set of powerful query predicates for moving objects. Moreover, we propose an implementation design based on off-the-shelf industrial solutions enhancing thus the applicability and robustness of our approach.

Like people who casually assess similarity between spatial scenes in their routine activities, users of pictorial databases are often interested in retrieving scenes that are similar to a given scene, and ranking them according to degrees of their match. For example, a town architect would like to query a database for the towns that have a landscape similar to the landscape of the site of a planned town. In this paper, we develop a computational model to determine the directional similarity between extended spatial objects, which forms a foundation for meaningful spatial similarity operators. The model is based on the direction-relation matrix. We derive how the similarity assessment of two direction-relation matrices corresponds to determining the least cost for transforming one direction-relation matrix into another. Using the transportation algorithm, the cost can be determined efficiently for pairs of arbitrary direction-relation matrices. The similarity values are evaluated empirically with several types of movements that create increasingly less similar direction relations. The tests confirm the cognitive plausibility of the similarity model.

In dynamic spatio-temporal environments where objects may continuously move in space, maintaining consistent information about the location of objects and processing motion-specific queries is a challenging problem. In this paper, we focus on indexing and query processing techniques for mobile objects. Specifically, we develop a classification of different types of selection queries that arise in mobile environments and explore efficient algorithms to evaluate them. Query processing algorithms are developed for both native space and parametric space indexing techniques. A performance study compares the two indexing strategies for different types of queries.

This paper addresses the problem of finding k nearest neighbors for moving query point (we call it k-NNMP). It is an important issue in both mobile computing research and real-life applications. The problem assumes that the query point is not static, as in k-nearest neighbor problem, but varies its position over time. In this paper, four different methods are proposed for solving the problem. Discussion about the parameters affecting the performance of the algorithms is also presented. A sequence of experiments with both synthetic and real point data sets are studied. In the experiments, our algorithms always outperform the existing ones by fetching 70% less disk pages. In some settings, the saving can be as much as one order of magnitude.

A method is presented in this paper for answering location-dependent queries in a mobile computing environment. We investigate a common scenario where data objects (e.g., restaurants and gas stations) are stationary while clients that issue queries about the data objects are mobile. Our proposed technique constructs a Voronoi Diagram (VD) on the data objects to serve as an index for them. A VD defines, for each data object d, the region within which d is the nearest point to any mobile client within that region. As such, the VD can be used to answer nearest-neighbor queries directly. Furthermore, the area within which the answer is valid can be computed. Based on the VD, we develop a semantic caching scheme that records a cached item as well as its valid range. A simulation is conducted to study the performance of the proposed semantic cache in comparison with the traditional cache and the baseline case where no cache is used. We show that the semantic cache has a much better performance than the other two methods.

With the emerging availability of small and portable devices that are able to determine their position and to communicate wirelessly, mobile and spatially aware applications become feasible. These applications rely on information that is bound to locations. In this paper we present neXus, a platform for such applications, which is open for both new applications and new information providers, similar to the World Wide Web. Distributed servers provide location-based information, which is federated to an integrated view for the applications. To achieve this goal, we present the concept of the Augmented World Model, which is a common data model for location-based information. We give an example to show how applications can use this platform.

Several studies have focused on the efficient processing of simple spatial query types such as selections and spatial joins. Little work, however, has been done towards the optimization of queries that process several spatial inputs and combine them through join and selection conditions. This paper identifies the dependencies between spatial operators and illustrates how they can affect the outcome of complex queries. A thorough analysis yields selectivity estimations that can be used to optimize any combination of spatial and non-spatial selection and join operators. The accuracy of the formulae is evaluated through experimentation with various queries. In addition to their importance for spatial databases, the presented results can be applied in several other domains, where dependencies exist between operators.

Query cost estimation is an important and well-studied problem in relational database systems. In this paper we study the cost estimation problem in the context of spatial database systems.

We introduce a new method that provides accurate cost estimation for spatial selections, or window queries, by building wavelet-based histograms for spatial data. Our method is based upon two techniques: (a) A representation transformation in which geometric objects are represented by points in higher-dimensional space and window queries correspond to semi-infinite range-sum queries, and (b) Multiresolution wavelet decomposition that provides a time-efficient and space-efficient approximation of the underlying distribution of the multidimensional point data, especially for semi-infinite range-sum queries. We also show for the first time how a wavelet decomposition of a dense multidimensional array derived from a sparse array through a partial-sum computation can still be computed efficiently using sparse techniques by doing the processing implicitly on the original data. Our method eliminates the drawbacks of the partition-based histogram methods in previous work, and even with very small space allocation it gives excellent cost estimation over a broad range of spatial data distributions and queries.

A class of commonly asked queries in a spatial database is known as buffer queries. An example of such a query is to “find house-power line pairs that are within 50 meters of each other.” A buffer query involves two spatial data sets and a distance d. The answer to this query are pairs of objects from the two input sets that are within distance d of each other. This paper addresses the problem of how to evaluate this class of queries efficiently. Geometric objects are used to denote the shape and location of spatial objects. Two objects are within distance d precisely when their minimum distance (minDist) is. A fundamental problem with buffer query evaluation is to find an effective algorithm for solving the minDist problem. Such an algorithm is found and its desirability is demonstrated. Finding a fast minDist algorithm is the first step to evaluate a buffer query efficiently. It is observed that many, and even most, candidates can be determined to be in the answer without resorting to the relatively expensive minDist operation. A candidate is first evaluated with the least expensive technique - called 0-object filtering. If it fails, a more costly operation, called 1-object filtering, is applied. Finally, if both filterings fail, the most expensive minDist algorithm is invoked. To show the effectiveness of these techniques, they are incorporated into the tree join algorithm and tested with real-life as well as synthetic data sets. Extensive experiments show that the proposed algorithm outperforms existing techniques by a wide margin in both the execution time as well as IO accesses. More importantly, the performance gain improves drastically with the increase of distance values.

Spatial joins are fundamental in spatial databases. Over the last decade, the primary focus of research has been on joins with the predicate “region intersection.” In modern database applications involving geospatial data such as GIS, efficient evaluation of joins with other spatial predicates is yet to be fully explored. In addition, most existing join algorithms were developed for two-way joins. Traditionally, a multi-way join is treated as a sequence of two-way joins. The goal of this paper is to study evaluation of multi-way spatial joins with direction predicates: complexity bounds and efficient algorithms. We first give I/O efficient plane sweeping based algorithms for 2-way direction joins and show that by combining the plane sweeping technique with external priority search trees, a 2-way direction join of N-tuple relations can be evaluated in O(Nlog_b N/M + k) I/Os in the worst case, where M is the size of the memory, b is the page size and k is the result size. The algorithms are then extended to perform a subclass of multi-way direction joins called “star joins”. We show that the I/O complexity of evaluating an way star join of N-tuple relations is O(mN log_b MN +K + k), where mN ² is the size of the intermediate result, M, b and k (= N ^m) are the same as above. We also apply the algorithm for star joins to evaluate a more general case of multi-way joins, which are star connections of star joins and show that this can be done in polynomial time. In the general case, we show that testing emptiness of a multi-way direction join is NP-complete. This lower bound holds even when in the join predicate (1) only one attribute for each relation is involved, and (2) each spatial attribute occurs a bounded number of times. It implies that join evaluation in these cases is NP-hard.

Given a collection of boolean spatial features, the co-location pattern discovery process finds the subsets of features frequently located together. For example, the analysis of an ecology dataset may reveal the frequent co-location of a fire ignition source feature with a needle vegetation type feature and a drought feature. The spatial co-location rule problem is different from the association rule problem. Even though boolean spatial feature types (also called spatial events) may correspond to items in association rules over market-basket datasets, there is no natural notion of transactions. This creates difficulty in using traditional measures (e.g. support, confidence) and applying association rule mining algorithms which use support based pruning. We propose a notion of user-specified neighborhoods in place of transactions to specify groups of items. New interest measures for spatial co-location patterns are proposed which are robust in the face of potentially infinite overlapping neighborhoods. We also propose an algorithm to mine frequent spatial co-location patterns and analyze its correctness, and completeness. We plan to carry out experimental evaluations and performance tuning in the near future.

The notion of time granularity comes into play in a variety of problems involving time representation and management in database applications, including temporal database design, temporal data conversion, temporal database inter-operability, temporal constraint reasoning, data mining, and time management in workflow systems. According to a commonly accepted view, any time granularity can be viewed as the partitioning of a temporal domain in groups of elements, where each group is perceived as an indivisible unit (a granule). Most granularities of practical interest are modeled as infinite sequences of time granules, that present a repeating pattern and, possibly, temporal gaps within and between granules. Even though conceptually clean, this definition does not address the problem of providing infinite granularities with a finite representation to make it possible to deal with them in an effective way. In this paper, we present an automata-theoretic solution to such a problem that revises and extends the string-based model recently proposed by Wijsen [13]. We illustrate the basic features of our formalism and discuss its application to the fundamental problems of equivalence and classification of time granularities.

We study the recent proposal of Goyal and Egenhofer who presented a model for qualitative spatial reasoning about cardinal directions. Our approach is formal and complements the presentation of Goyal and Egenhofer. We focus our efforts on the operation of composition for two cardinal direction relations. We point out that the only published method to compute the composition does not always work correctly. Then we consider progressively more expressive classes of cardinal direction relations and give composition algorithms for these classes. Our theoretical framework allows us to prove formally that our algorithms are correct. Finally, we demonstrate that in some cases, the binary relation resulting from the composition of two cardinal direction relations cannot be expressed using the relations defined by Goyal and Egenhofer.

Recently there is much interest in moving objects databases, and data models and query languages have been proposed offering data types such as moving point and moving region together with suitable operations. In contrast to most earlier work on spatio-temporal databases, a moving region can change its shape and extent not only in discrete steps, but continuously. Examples of such moving regions are oil spills, forest fires, hurricanes, schools of fish, spreads of diseases, or armies, to name but a few.

In this paper, we consider triangle-based two-dimensional multiresolution complexes, called Multi-Triangulations (MTs), constructed based on a vertex-removal simplification strategy, which is the most common strategy used to build simplified representations of surfaces, e.g., terrains. We describe and compare compact encoding structures for such MTs. We show that these structures provide good compression ratios not only with respect to an economical data structure for general MTs, but also with respect to encoding the original mesh (i.e., the mesh at the full resolution). We also analyze the basic atomic operations needed for performing selective refinement on an MT, and we show that such operations are efficiently supported by the data structures described.

The need to access spatial data at multiple levels of detail is a fundamental requirement of many applications of geographical information, yet conventional spatial database access methods are based on single resolution spatial objects. In this paper we present a design for multi-scale spatial objects in which both spatial objects and the vertices of their component geometry are labelled with scale priority values. Alternative approaches to database implementation are considered in which vertices are organised into scale-bounded layers. Access times for spatially-indexed vertex block schemes (comparable to the PR-File) were superior to a BLOB scheme where only entire multi-scale objects were spatially indexed. The use of a 3D R-tree to integrate scale and space indexing was found to improve considerably on using either R-Tree indexing of space only or B-tree indexing of scale. Techniques are also presented for client-side reconstruction of cached multi-scale geometry. Implementations are compared in a client-server environment using the Informix object relational database system.

ESRI® ArcIMS® is an Internet Map Server software that facilitates authoring of maps, designing of Web sites using them, and their publication on the Internet. Its distributed architecture offers customization of server, plugability of components, scalability, load balancing, and fail over/recovery and facilitates 24x7 operations. This paper describes the architecture of ArcIMS 3, its components, and some of the live Web sites that use it. The paper also discusses some considerations for the next version of ArcIMS.

The problem of mining spatiotemporal patterns is finding sequences of events that occur frequently in spatiotemporal datasets. Spatiotemporal datasets store the evolution of objects over time. Examples include sequences of sensor images of a geographical region, data that describes the location and movement of individual objects over time, or data that describes the evolution of natural phenomena, such as forest coverage. The discovered patterns are sequences of events that occur most frequently. In this paper, we present DFS_MINE, a new algorithm for fast mining of frequent spatiotemporal patterns in environmental data. DFS_MINE, as its name suggests, uses a Depth-First-Search-like approach to the problem which allows very fast discoveries of long sequential patterns. DFS_MINE performs database scans to discover frequent sequences rather than relying on information stored in main memory, which has the advantage that the amount of space required is minimal. Previous approaches utilize a Breadth-First-Search-like approach and are not efficient for discovering long frequent sequences. Moreover, they require storing in main memory all occurrences of each sequence in the database and, as a result, the amount of space needed is rather large. Experiments show that the I/O cost of the database scans is offset by the efficiency of the DFS-like approach that ensures fast discovery of long frequent patterns. DFS_MINE is also ideal for mining frequent spatiotemporal sequences with various spatial granularities. Spatial granularity refers to how fine or how general our view of the space we are examining is.

Spatial databases store information about the position of individual objects in space. In many applications however, such as traffic supervision or mobile communications, only summarized data, like the number of cars in an area or phones serviced by a cell, is required. Although this information can be obtained from transactional spatial databases, its computation is expensive, rendering online processing inapplicable. Driven by the non-spatial paradigm, spatial data warehouses can be constructed to accelerate spatial OLAP operations. In this paper we consider the star-schema and we focus on the spatial dimensions. Unlike the non-spatial case, the groupings and the hierarchies can be numerous and unknown at design time, therefore the well-known materialization techniques are not directly applicable. In order to address this problem, we construct an ad-hoc grouping hierarchy based on the spatial index at the finest spatial granularity. We incorporate this hierarchy in the lattice model and present efficient methods to process arbitrary aggregations. We finally extend our technique to moving objects by employing incremental update methods.

Data warehouses are becoming increasingly popular in the spatial domain, where they are used to analyze large amounts of spatial information for decision-making purposes. The data warehouse must provide very fast response times if popular analysis tools such as On-Line Analytical Processing [2](OLAP) are to be applied successfully. In order for the data analysis to have an adequate performance, pre-aggregation, i.e., pre-computation of partial query answers, is used to speed up query processing. Normally, the data structures in the data warehouse have to be very “well-behaved” in order for pre-aggregation to be feasible. However, this is not the case in many spatial applications.

In this paper, we analyze the properties of topological relationships between 2D spatial objects with respect to pre-aggregation and show why traditional pre-aggregation techniques do not work in this setting. We then use this knowledge to significantly extend previous work on pre-aggregation for irregular data structures to also cover special spatial issues such as partially overlapping areas.

The design of external index structures for one- and multidimensional extended objects is a long and well studied subject in basic database research. Today, more and more commercial applications rely on spatial datatypes and require a robust and seamless integration of appropriate access methods into reliable database servers. This paper proposes an efficient, dynamic and scalable approach to manage one-dimensional interval sequences within off-the-shelf object-relational database systems. The presented technique perfectly fits to the concept of space-filling curves and, thus, generalizes to spatially extended objects in multidimensional data spaces. Based on the Relational Interval Tree, the method is easily embedded in modern extensible indexing frameworks and significantly outmatches Linear Quadtrees and Relational R-trees with respect to usability, concurrency, and performance. As demonstrated by our experimental evaluation on an Oracle server with real GIS and CAD data, the competing methods are outperformed by factors of up to 4.6 (Linear Quadtree) and 58.3 (Relational R-tree) for query response time.

The broadcasting of spatial data together with an index structure is an effective way of disseminating data in a wireless mobile environment. Mobile clients requesting data tune into a continuous broadcast only when spatial data of interest and relevance is available on the channel and thus minimize their power consumption. A mobile client experiences latency (time elapsed from requesting to receiving data) and tuning time (the amount of time spent listening to the channel). This paper studies the execution of spatial queries on broadcasted tree-based spatial index structures. The focus is on queries that require a partial traversal of the spatial index, not only a single-path root-to-leaf search. We present techniques for processing spatial queries while mobile clients are listening to a broadcast of the tree. Our algorithms can handle clients with limited memory, trees broadcast with a certain degree of replication of index nodes, and algorithms executed at the clients may employ different data structures. Experimental work on R*-trees shows that these techniques lead to different tuning times and different latencies. Our solutions also lead to efficient methods for starting the execution of a query in the middle of a broadcast cycle. Spatial query processing in a multiple channel environment is also addressed.