Advances in Spatial and Temporal Databases

The standard database mechanisms for concurrency control, which include transactions and locking protocols, do not provide the support needed for updating complex geographic data in a multiuser environment. The preferred method to resolve conflicts in GIS systems is to encapsulate the modifications generated by the end users through the use of multiple versions. Multiuser (or versioned) geographic databases allow users to operate as though they have full access to the entire dataset. Instead of relying upon row locking, versioned databases allow multiple users to simultaneously edit the same row. They implement a model for conflict detection and resolution where the first to commit the change wins by default (though clients can manually intervene and select the latter change as the winner).

Network models are frequently used as a mechanism to describe the connectivity information between spatial features in many emerging GIS applications. Supporting networks within the context of a versioned database imposes additional requirements – the complex network model must retain integrity irrespective of the sequence of simultaneous edits by various clients. In this paper, we review our network model and discuss the enhancements necessary to maintaining topological network integrity in this complex environment. Our solution is based on the notion of dirty areas and dirty objects (i.e., regions or elements that contain edits that have not been reflected in the network connectivity index). The dirty areas and objects are identified and marked during editing of the network feature data. They are then subsequently cleaned as a byproduct of the incremental update of the connectivity network.

In this paper, we propose an efficient method to answer continuous

k

nearest neighbor (C

k

NN) queries in spatial networks. Assuming a moving query object and a set of data objects that make frequent and arbitrary moves on a spatial network with dynamically changing edge weights, C

k

NN continuously monitors the nearest (in network distance) neighboring objects to the query. Previous C

k

NN methods are inefficient and, hence, fail to scale in large networks with numerous data objects because: 1) they heavily rely on Dijkstra-based

blind expansion

for network distance computation that incurs excessively redundant cost particularly in large networks, and 2) they

blindly map

all object location updates to the network disregarding whether the updates are relevant to the C

k

NN query result. With our method, termed ER-C

k

NN (short for

Euclidian Restriction

based C

k

NN), we utilize ER to address both of these shortcomings. Specifically, with ER we enable 1)

guided search

(rather than blind expansion) for efficient network distance calculation, and 2)

localized mapping

(rather than blind mapping) to avoid the intolerable cost of redundant object location mapping. We demonstrate the efficiency of ER-C

k

NN via extensive experimental evaluations with real world datasets consisting of a variety of large spatial networks with numerous moving objects.

Given a collection of sensors monitoring a flow network, the problem of discovering teleconnected flow anomalies aims to identify strongly connected pairs of events (e.g., introduction of a contaminant and its removal from a river). The ability to mine teleconnected flow anomalies is important for applications related to environmental science, video surveillance, and transportation systems. However, this problem is computationally hard because of the large number of time instants of measurement, sensors, and locations. This paper characterizes the computational structure in terms of three critical tasks, (1) detection of flow anomaly events, (2) identification of candidate pairs of events, and (3) evaluation of candidate pairs for possible teleconnection. The first task was addressed in our recent work. In this paper, we propose a RAD (Relationship Analysis of spatio-temporal Dynamic neighborhoods) approach for steps 2 and 3 to discover teleconnected flow anomalies. Computational overhead is brought down significantly by utilizing our proposed spatio-temporal dynamic neighborhood model as an index and a pruning strategy. We prove correctness and completeness for the proposed approaches. We also experimentally show the efficacy of our proposed methods using both synthetic and real datasets.

Recent advances in wireless communications and positioning devices have generated a tremendous amount of interest in the continuous monitoring of spatial queries. However, such applications can incur a heavy burden on the

data owner

(DO), due to very frequent location updates. Database outsourcing is a viable solution, whereby the DO delegates its database functionality to a

service provider

(SP) that has the infrastructure and resources to handle the high workload. In this framework,

authenticated query processing

enables the clients to verify the correctness of the query results that are returned by the SP. In addition to correctness, the dynamic nature of the monitored data requires the provision for

temporal completeness

, i.e., the clients must be able to verify that there are no missing results in between data updates. This paper constitutes the first work that deals with the authentication of continuous spatial queries, focusing on ranges. We first introduce a baseline solution (BSL) that achieves correctness and temporal completeness, but incurs false transmissions; that is, the SP has to notify clients whenever there is a data update, even if it does not affect their results. Then, we propose CSA, a mechanism that minimizes the processing and transmission overhead through an elaborate indexing scheme and a virtual caching mechanism. Finally, we derive analytical models to optimize the performance of our methods, and evaluate their effectiveness through extensive experiments.

Outsourcing data to third party data providers is becoming a common practice for data owners to avoid the cost of managing and maintaining databases. Meanwhile, due to the popularity of location-based-services (LBS), the need for spatial data (e.g., gazetteers, vector data) is increasing exponentially. Consequently, we are witnessing a new trend of outsourcing spatial datasets by data collectors. Two main challenges with outsourcing datasets is to keep the data private (from the data provider) and ensure the integrity of the query result (for the clients). Unfortunately, most of the techniques proposed for privacy and integrity do not extend to spatial data in a straightforward manner. Hence, recent studies proposed various techniques to support either privacy or integrity (but not both) on spatial datasets. In this paper, for the first time, we propose a technique that can ensure both privacy and integrity for outsourced spatial data. In particular, we first use a one-way spatial transformation method based on Hilbert curves, which encrypts the spatial data before outsourcing and hence ensures its privacy. Next, by probabilistically replicating a portion of the data and encrypting it with a different encryption key, we devise a technique for the client to audit the trustworthiness of the query results. We show the applicability of our approach for both

k

-nearest-neighbor and spatial range queries, the building blocks of any LBS application. Finally, we evaluate the validity and performance of our algorithms with real-world datasets.

Mobile devices with global positioning capabilities allow users to retrieve points of interest (POI) in their proximity. To protect user privacy, it is important not to disclose exact user coordinates to un-trusted entities that provide location-based services. Currently, there are two main approaches to protect the location privacy of users:

(i)

hiding locations inside cloaking regions (CRs) and

(ii)

encrypting location data using private information retrieval (PIR) protocols. Previous work focused on finding good trade-offs between privacy and performance of user protection techniques, but disregarded the important issue of protecting the POI dataset

D

. For instance, location cloaking requires large-sized CRs, leading to excessive disclosure of POIs (

O

(|

D

|) in the worst case). PIR, on the other hand, reduces this bound to

$O(\sqrt{|D|})$

, but at the expense of high processing and communication overhead.

We propose a hybrid, two-step approach to private location-based queries, which provides protection for both the users and the database. In the first step, user locations are generalized to coarse-grained CRs which provide strong privacy. Next, a PIR protocol is applied with respect to the obtained query CR. To protect excessive disclosure of POI locations, we devise a cryptographic protocol that privately evaluates whether a point is enclosed inside a rectangular region. We also introduce an algorithm to efficiently support PIR on dynamic POI sub-sets. Our method discloses

O

(1) POI, orders of magnitude fewer than CR- or PIR-based techniques. Experimental results show that the hybrid approach is scalable in practice, and clearly outperforms the pure-PIR approach in terms of computational and communication overhead.

Location-based services (LBS) are receiving increasing popularity as they provide convenience to mobile users with on-demand information. The use of these services, however, poses privacy issues as the user locations and queries are exposed to untrusted LBSs.

Spatial cloaking

techniques provide privacy in the form of

k

-anonymity; i.e., they guarantee that the (location of the) querying user

u

is indistinguishable from at least

k

-1 others, where

k

is a parameter specified by

u

at query time. To achieve this, they form a group of

k

users, including

u

, and forward their minimum bounding rectangle (termed

anonymizing spatial region

, ASR) to the LBS. The rationale behind sending an ASR instead of the distinct

k

locations is that exact user positions (querying or not) should not be disclosed to the LBS. This results in large ASRs with considerable dead-space, and leads to unnecessary performance degradation. Additionally, there is no guarantee regarding the amount of location information that is actually revealed to the LBS. In this paper, we introduce the concept of

information leakage

in spatial cloaking. We provide measures of this leakage, and show how we can trade it for better performance in a tunable manner. The proposed methodology directly applies to centralized and decentralized cloaking models, and is readily deployable on existing systems.

A key issue in clustering data, regardless the algorithm used, is the definition of a distance function. In the case of trajectory data, different distance functions have been proposed, with different degrees of complexity. All these measures assume that trajectories are error-free, which is essentially not true. Uncertainty is present in trajectory data, which is usually obtained through a series of GPS of GSM observations. Trajectories are then reconstructed, typically using linear interpolation. A well-known model to deal with

uncertainty

in a trajectory sample, uses the notion of

space-time prisms

(also called

beads

), to estimate the positions where the object could have been, given a maximum speed. Thus, we can replace a (reconstructed) trajectory by a necklace (intuitively, a

a chain of prisms

), connecting consecutive trajectory sample points. When it comes to clustering, the notion of uncertainty requires appropriate distance functions. The main contribution of this paper is the definition of a distance function that accounts for uncertainty, together with the proof that this function is also a metric, and therefore it can be used in clustering. We also present an algorithm that computes the distance between the chains of prisms corresponding to two trajectory samples. Finally, we discuss some preliminary results, obtained clustering a set of trajectories of cars in the center of the city of Milan, using the distance function introduced in this paper.

In a

route search

over geospatial data, a user provides terms for specifying types of geographical entities that she wishes to visit. The goal is to find a route that

(1)

starts at a given location,

(2)

ends at a given location, and

(3)

travels via geospatial entities that are relevant to the provided search terms. Earlier work studied the problem of finding a route that is

effective

in the sense that its length does not exceed a given limit, the relevancy of the objects is as high as possible, and the route visits a single object from each specified type. This paper investigates route search over

probabilistic geospatial data

. It is shown that the notion of an effective route requires a new definition and, specifically, two alternative semantics are proposed. Computing an effective route is more complicated, compared to the non-probabilistic case, and hence necessitates new algorithms. Heuristic methods for computing an effective route, under either one of the two semantics, are developed. (Note that the problem is NP-hard.) These methods are compared analytically and experimentally. In particular, experiments on both synthetic and real-world data illustrate the efficiency and effectiveness of these methods in computing a route under the two semantics.

Tracking data has become a valuable resource for establishing speed profiles for road networks, i.e., travel-time maps. While methods to derive travel time maps from GPS tracking data sources, such as floating car data (FCD), are available, the critical aspect in this process is to obtain amounts of data that fully cover all geographic areas of interest. In this work, we introduce Wireless Positioning Systems (WPS) based on 802.11 networks (WiFi), as an additional technology to extend the number of available tracking data sources. Featuring increased ubiquity but lower accuracy than GPS, this technology has the potential to produce travel time maps comparable to GPS data sources. Specifically, we adapt and apply readily available algorithms for (a) WPS (centroid and fingerprinting) to derive position estimates, and (b) map matching to derive travel times. Further, we introduce map matching as a means to improve WPS accuracy. We present an extensive experimental evaluation on real data comparing our approach to GPS-based techniques. We demonstrate that the exploitation of WPS tracking data sources is feasible with existing tools and techniques.

With the exponential growth of moving objects data to the Gigabyte range, it has become critical to develop effective techniques for indexing, updating, and querying these massive data sets. To meet the high update rate as well as low query response time requirements of moving object applications, this paper takes a novel approach in moving object indexing. In our approach we do

not

require a sophisticated index structure that needs to be adjusted for each incoming update. Rather we construct conceptually simple

short-lived throwaway indexes

which we only keep for a very short period of time (sub-seconds) in main memory. As a consequence, the resulting technique

MOVIES

supports at the same time high query rates

and

high update rates and trades this for query result staleness. Moreover,

MOVIES

is the first main memory method supporting time-parameterized predictive queries. To support this feature we present two algorithms: non-predictive

MOVIES

and predictive

MOVIES

. We obtain the surprising result that a predictive indexing approach — considered state-of-the-art in an external-memory scenario — does not scale well in a main memory environment. In fact our results show that

MOVIES

outperforms state-of-the-art moving object indexes like a main-memory adapted B

x

-tree by orders of magnitude w.r.t. update rates and query rates. Finally, our experimental evaluation uses a workload unmatched by any previous work. We index the complete road network of Germany consisting of 40,000,000 road segments and 38,000,000 nodes. We scale our workload up to 100,000,000 moving objects, 58,000,000 updates per second and 10,000 queries per second which is unmatched by any previous work.

Indoor spaces accommodate large populations of individuals. With appropriate indoor positioning, e.g., Bluetooth and RFID, in place, large amounts of trajectory data result that may serve as a foundation for a wide variety of applications, e.g., space planning, way finding, and security. This scenario calls for the indexing of indoor trajectories. Based on an appropriate notion of indoor trajectory and definitions of pertinent types of queries, the paper proposes two R-tree based structures for indexing object trajectories in symbolic indoor space. The RTR-tree represents a trajectory as a set of line segments in a space spanned by positioning readers and time. The TP

2

R-tree applies a data transformation that yields a representation of trajectories as points with extension along the time dimension. The paper details the structure, node organization strategies, and query processing algorithms for each index. An empirical performance study suggests that the two indexes are effective, efficient, and robust. The study also elicits the circumstances under which our proposals perform the best.

We consider a setting with numerous location-aware moving objects that communicate with a central server. Assuming a set of focal points of interest, we aim at continuously monitoring object orientations and hence detect situations where many objects get closer to or move away from any such site. Towards this goal, we propose a streaming approach that delegates part of the processing to objects, which relay positional updates upon significant deviations at their course. The central processor maintains the changing distribution of current object headings around each focal point and may issue alerts once it observes many objects moving along a direction (e.g., increased northbound traffic near the stadium). To efficiently answer such navigational queries, we introduce a novel access method that indexes object headings influencing a specific site. Furthermore, we extent this scheme to examine trajectory movements around sites over the recent past. Experimental results verify that this framework is able to cope with scalable numbers of objects at reduced communication cost, while offering instant notification of important trends along diverse directions for multiple focal points.

As more data-intensive applications emerge, advanced retrieval semantics, such as ranking and skylines, have attracted attention. Geographic information systems are such an application with massive spatial data. Our goal is to efficiently support skyline queries over massive spatial data. To achieve this goal, we first observe that the best known algorithm

VS

2

, despite its claim, may fail to deliver correct results. In contrast, we present a simple and efficient algorithm that computes the correct results. To validate the effectiveness and efficiency of our algorithm, we provide an extensive empirical comparison of our algorithm and

VS

2

in several aspects.

In this paper, we formalize the novel concept of incremental reverse nearest neighbor ranking and suggest an original solution for this problem. We propose an efficient approach for reporting the results incrementally without the need to restart the search from scratch. Our approach can be applied to a multi-dimensional feature database which is hierarchically organized by any R-tree like index structure. Our solution does not assume any preprocessing steps which makes it applicable for dynamic environments where updates of the database frequently occur. Experiments show that our approach reports the ranking results with much less page accesses than existing approaches designed for traditional reverse nearest neighbor search applied to the ranking problem.

The range nearest-neighbor (NN) query is an important query type in location-based services, as it can be applied to the case that an NN query has a spatial region, instead of a location point, as the query location. Examples of the applications of range NN queries include uncertain locations and privacy-preserving queries. Given a set of objects, the range NN answer is a set of objects that includes the nearest object(s) to every point in a given spatial region. The answer set size would significantly increase as the spatial region gets larger. Unfortunately, mobile users in wireless environments suffer from scarce bandwidth and low-quality communication, transmitting a large answer set from a database server to the user would pose very high response time. To this end, we propose an approximate range NN query processing algorithm to balance a performance tradeoff between query response time and the quality of answers. The distinct features of our algorithm are that (1) it allows the user to specify an approximation tolerance level

k

, so that we guarantee to provide an answer set

${\cal A}$

such that each object in

${\cal A}$

is one of the

k

nearest objects to every point in a given query region; and (2) it minimizes the number of objects returned in an answer set, in order to minimize the transmission time of sending the answer set to the user. Extensive experimental results show that our proposed algorithm is scalable and effectively reduces query response time while providing approximate query answers that satisfy the user specified approximation tolerance level.

Recent advances in information technology demand handling complex data types, such as images, video, audio, time series and genetic sequences. Distinctly from traditional data (such as numbers, short strings and dates), complex data do not possess the total ordering property, yielding relational comparison operators useless. Even equality comparisons are of little help, as it is very unlikely to have two complex elements exactly equal. Therefore, the similarity among elements has emerged as the most important property for comparisons in such domains, leading to the growing relevance of metric spaces to data search. Regardless of the data domain properties, the systems need to track evolution of data over time. When handling multidimensional data, temporal information is commonly treated as just one or more dimensions. However, metric data do not have the concept of dimensions, thus adding a plain “temporal dimension” does not make sense. In this paper we propose a novel metric-temporal data representation and exploit its properties to compare elements by similarity taking into account time-related evolution. We also present experimental evaluation, which confirms that our technique effectively takes into account the contributions of both the metric and temporal data components. Moreover, the experiments showed that the temporal information always improves the precision of the answer.

In applications involving spatio-temporal modelling, granularities of data may have to adapt according to the evolving semantics and significance of data. In this paper we define

ST

2

_ODMGe, a multigranular spatio-temporal model supporting

evolutions

, which encompass the dynamic adaptation of attribute granularities, and the deletion of attribute values. Evolutions are specified as

Event - Condition - Action

rules and are executed at run-time. The event, the condition, and the action may refer to a period of time and a geographical area. The evolution may also be constrained by the attribute values. The ability of dynamically evolving the object attributes results in a more flexible management of multigranular spatio-temporal data but it requires revisiting the notion of object consistency with respect to class definitions and access to multigranular object values. Both issues are formally investigated in the paper.

We introduce TOQL, a query language for querying time information in ontologies. TOQL is a high level query language that handles ontologies almost like relational databases. Queries are issued as SQL-like statements involving time (i.e., time points or intervals) or high-level ontology concepts that vary in time. Although independent from TOQL, this work suggests a mechanism for representing time evolving concepts in ontologies based on the four-dimensional perdurantist mechanism. However, TOQL prevents users from being familiar with the representation of time in ontologies. To show proof of concept, an application has been developed that supports translation and execution of TOQL queries on temporal ontologies combined with a reasoning mechanism based on event calculus. A real world temporal ontology is also implemented on which several TOQL example queries are processed and discussed.

A lot of information on the web is geographically referenced. Discovering and linking this information poses eminent research challenges to the geospatial semantic web, with regards to the representation and manipulation of geographic data. Towards addressing these challenges, this work explores the potential of the current semantic web languages and tools. In particular, an integrated logical framework of rules and ontologies, using current W3C standards, is assessed for modeling geospatial ontologies of place encoding both symbolic and geometric references to place locations. Spatial reasoning is incorporated in the framework to facilitate the deduction of implicit semantics and for expressing spatial integrity constraints. The logical framework is then extended with geo-computation engines that offer more effective manipulations of geometric information. Example data sets mined from web resources are used to demonstrate and evaluate both frameworks, offering insights to their potentials and limitations.