This dissertation challenges an unstudied area in moving objects database domains; predicting (long-term) future locations of moving objects. Moving object prediction enables us to provide a wide range of applications, such as traffic prediction, pre-detection of an aircraft collision, and reporting attractive gas prices for drivers along their routes ahead. Nevertheless, existing location prediction techniques are limited to support such applications since they are generally capable only of short-term predictions. In the real world, many objects exhibit typical movement patterns. This pattern information is able to serve as an important background to tackle the limitations of the existing prediction methods. We aims at offering foundations of pattern-aware prediction for moving objects, rendering more precise prediction results. Specifically, this thesis focuses on three parts. The first part of the thesis studies the problem of predicting future locations of moving objects in Euclidean space. We introduce a novel prediction approach, termed the hybrid prediction model, which utilizes not only the current motion of an object, but also the object's trajectory patterns for prediction. We define, mine, and index the trajectory patterns with a novel access method for efficient query processing. We then propose two different query processing techniques along given query time, i.e., for near future and for distant future. The second part covers the prediction problem for moving objects in network space. We formulate a network mobility model that offers a concise representation of mobility statistics extracted from massive collections of historical objects trajectories. This model captures turning patterns of the objects at junctions, at the granularity of individual objects as well as globally. Based on the model, we develop three different algorithms for predicting the future path of a mobile user moving in a road network, named the PathPredictors. The third part of the thesis extends the prediction problem for a single object to that for multiple objects. We introduce a convoy query that retrieves all groups of objects, i.e., convoys, from the objects' historical trajectories, each convoy consists of objects that have traveled together for some time; thus they may also move together in the future. We then propose three efficient algorithms for the convoy discovery, called the CuTS family, that adopt line simplification methods for reducing the size of the trajectories, permitting efficient query processing. For each part, we demonstrate comprehensive experimental results of our proposals, which show significantly improved accuracies for moving object prediction compared with state-of-the-art methods, while also facilitating efficient query processing.

This dissertation challenges an unstudied area in moving objects database domains; predicting (long-term) future locations of moving objects. Moving object prediction enables us to provide a wide range of applications, such as traffic prediction, pre-detection of an aircraft collision, and reporting attractive gas prices for drivers along their routes ahead. Nevertheless, existing location prediction techniques are limited to support such applications since they are generally capable only of short-term predictions. In the real world, many objects exhibit typical movement patterns. This pattern information is able to serve as an important background to tackle the limitations of the existing prediction methods. We aims at offering foundations of pattern-aware prediction for moving objects, rendering more precise prediction results. Specifically, this thesis focuses on three parts. The first part of the thesis studies the problem of predicting future locations of moving objects in Euclidean space. We introduce a novel prediction approach, termed the hybrid prediction model, which utilizes not only the current motion of an object, but also the object's trajectory patterns for prediction. We define, mine, and index the trajectory patterns with a novel access method for efficient query processing. We then propose two different query processing techniques along given query time, i.e., for near future and for distant future. The second part covers the prediction problem for moving objects in network space. We formulate a network mobility model that offers a concise representation of mobility statistics extracted from massive collections of historical objects trajectories. This model captures turning patterns of the objects at junctions, at the granularity of individual objects as well as globally. Based on the model, we develop three different algorithms for predicting the future path of a mobile user moving in a road network, named the PathPredictors. The third part of the thesis extends the prediction problem for a single object to that for multiple objects. We introduce a convoy query that retrieves all groups of objects, i.e., convoys, from the objects' historical trajectories, each convoy consists of objects that have traveled together for some time; thus they may also move together in the future. We then propose three efficient algorithms for the convoy discovery, called the CuTS family, that adopt line simplification methods for reducing the size of the trajectories, permitting efficient query processing. For each part, we demonstrate comprehensive experimental results of our proposals, which show significantly improved accuracies for moving object prediction compared with state-of-the-art methods, while also facilitating efficient query processing.

Efficient twig pattern matching is essential to XML queries and other tree-based queries. Numerous so-called holistic algorithms have been proposed for efficiently processing the twig patterns in XML queries. However, a more general form of twig pattern, called Boolean-twig (or B-twig for short), which allows arbitrary combination of an arbitrary number of all the three logical connectives, AND, OR, and NOT, in a twig pattern, has not been adequately addressed. The theme of this study is on holistic (and efficient) B-twig pattern matching using region encoding and Dewey encoding schemes. We first adopt region encoding and propose a novel, direct approach called DBTwigMerge for holistic B-twig pattern matching, which although enjoys certain theoretical ``beauty'' and ``elegance'' but does not always outperform our prior approach, BTwigMerge. Based on the experience gained and in-depth investigation, we then come up with another new and more efficient approach, FBTwigMerge, which is proven to be the overall winner among all the holistic approaches using region encoding. In this study, we also studied the holistic B-twig pattern matching problem using Dewey encoding. The unique properties of Dewey encoding bring challenges and also benefits to this problem. By carefully addressing the challenges, this dissertation finally presents the first Dewey based holistic approach, called DeweyNOT, for efficiently solving the pattern matching problem with a subclass of B-twigs, i.e., twig queries involving arbitrary AND/NOT predicates. Extensive experimental studies have been conducted that demonstrate the viability and outstanding performance of the proposed approaches.

Over the last four decades, relational database systems, with their mathematical basis in first-order logic, have provided a congenial and efficient environment to handle enterprise data during its entire life cycle of generation, storage, maintenance and processing. An organic reason for their pervasive popularity is intrinsic support for declarative user queries, wherein the user only specifies the end objectives, and the system takes on the responsibility of identifying the most efficient means, called “plans”, to achieve these objectives. A crucial input to generating efficient query execution plans are the compile-time estimates of the data volumes that are output by the operators implementing the algebraic predicates present in the query. These volume estimates are typically computed using the “selectivities” of the predicates. Unfortunately, a pervasive problem encountered in practice is that these selectivities often differ significantly from the values actually encountered during query execution, leading to poor plan choices and grossly inflated response times. While the database research community has spent considerable efforts to address the above challenge, the prior techniques all suffer from a systemic limitation - the inability to provide any guarantees on the execution performance. In this thesis, we materially address this long-standing open problem by developing a radically different query processing strategy that lends itself to attractive guarantees on run-time performance. Specifically, in our approach, the compile-time estimation process is completely eschewed for error-prone selectivities. Instead, from the set of optimal plans in the query’s selectivity error space, a limited subset called the “plan bouquet”, is selected such that at least one of the bouquet plans is 2-optimal at each location in the space. Then, at run time, an exploratory sequence of cost-budgeted executions from the plan bouquet is carried out, eventually finding a plan that executes to completion within its assigned budget. The duration and switching of these executions is controlled by a graded progression of isosurfaces projected onto the optimal performance profile. We prove that this construction provides viable guarantees on the worst-case performance relative to an oracular system that magically possesses accurate apriori knowledge of all selectivities. Moreover, it ensures repeatable execution strategies across different invocations of a query, an extremely desirable feature in industrial settings. Our second contribution is a suite of techniques that substantively improve on the performance guarantees offered by the basic bouquet algorithm. First, we present an algorithm that skips carefully chosen executions from the basic plan bouquet sequence, leveraging the observation that an expensive execution may provide better coverage as compared to a series of cheaper siblings, thereby reducing the aggregate exploratory overheads. Next, we explore randomized variants with regard to both the sequence of plan executions and the constitution of the plan bouquet, and show that the resulting guarantees are markedly superior, in expectation, to the corresponding worst case values. From a deployment perspective, the above techniques are appealing since they are completely “black-box”, that is, non-invasive with regard to the database engine, implementable using only API features that are commonly available in modern systems. As a proof of concept, the bouquet approach has been fully prototyped in QUEST, a Java-based tool that provides a visual and interactive demonstration of the bouquet identification and execution phases. In similar spirit, we propose an efficient isosurface identification algorithm that avoids exploration of large portions of the error space and drastically reduces the effort involved in bouquet construction. The plan bouquet approach is ideally suited for “canned” query environments, where the computational investment in bouquet identification is amortized over multiple query invocations. The final contribution of this thesis is extending the advantage of compile-time sub-optimality guarantees to ad hoc query environments where the overheads of the off-line bouquet identification may turn out to be impractical. Specifically, we propose a completely revamped bouquet algorithm that constructs the cost-budgeted execution sequence in an “on-the-fly” manner. This is achieved through a “white-box” interaction style with the engine, whereby the plan output cardinalities exposed by the engine are used to compute lower bounds on the error-prone selectivities during plan executions. For this algorithm, the sub-optimality guarantees are in the form of a low order polynomial of the number of error-prone selectivities in the query. The plan bouquet approach has been empirically evaluated on both PostgreSQL and a commercial engine ComOpt, over the TPC-H and TPC-DS benchmark environments. Our experimental results indicate that it delivers orders of magnitude improvements in the worst-case behavior, without impairing the average-case performance, as compared to the native optimizers of these systems. In absolute terms, the worst case sub-optimality is upper bounded by 20 across the suite of queries, and the average performance is empirically found to be within a factor of 4 wrt the optimal. Even with the on-the-fly bouquet algorithm, the guarantees are found to be within a factor of 3 as compared to those achievable in the corresponding canned query environment. Overall, the plan bouquet approach provides novel performance guarantees that open up exciting possibilities for robust query processing.

In Wireless Sensor and Robot Networks (WSRNs), static sensors report event information to one of the robots. In the k nearest neighbour query processing problem in WSRNs, the robot receives event report needs to find exact k nearest robots (KNN) to react to the event, among those connected to it. We are interested in localized solutions, which avoid message flooding to the whole network. Several existing methods restrict the search within a predetermined boundary. Some network density-based estimation algorithms were proposed but they either result in large message transmission or require the density information of the whole network in advance which is complex to implement and lacks robustness. Algorithms with tree structures lead to the excessive energy consumption and large latency caused by structural construction. Itinerary based approaches generate large latency or unsatisfactory accuracy. In this thesis, we propose a new method to estimate a search boundary, which is a circle centred at the query point. Two algorithms are presented to disseminate the message to robots of interest and aggregate their data (e.g. the distance to query point). Multiple Auction Aggregation (MAA) is an algorithm based on auction protocol, with multiple copies of query message being disseminated into the network to get the best bidding from each robot. Partial Depth First Search (PDFS) attempts to traverse all the robots of interest with a query message to gather the data by depth first search. This thesis also optimizes a traditional itinerary-based KNN query processing method called IKNN and compares this algorithm with our proposed MAA and PDFS algorithms. The experimental results followed indicate that the overall performance of MAA and PDFS outweighs IKNN in WSRNs.

No description available.

Fast and accurate estimations for complex queries are profoundly beneficial for large databases with heavy workloads. The most widely adopted query optimizers use synopses to tune up the databases in manners of optimization and re-optimization. From Chapter 1 to Chapter 3, we focus on the synopses for query optimization. We propose a statistical summary for a database, called CS2 (Correlated Sample Synopsis), to provide rapid and accurate result size estimations for all queries with joins and arbitrary selections. Unlike the state-of-the-art techniques, CS2 does not completely rely on simple random samples, but mainly consists of correlated sample tuples that retain join relationships with less storage. We introduce a statistical technique, called reverse sample, and design an innovative estimator, called reverse estimator, to fully utilize correlated sample tuples for query estimation. We prove both theoretically and empirically that the reverse estimator is unbiased and accurate using CS2. Extensive experiments on multiple datasets show that CS2 is fast to construct and derives more accurate estimations than existing methods with the same space budget. In Chapter 4, we focus on the synopses for query re-optimization on repetitive queries. Repetitive queries refer to those queries that are likely to be executed repeatedly in the future, such as those that are used to generate periodic reports, perform routine maintenance, summarize data for analysis, etc. They can constitute a large part of daily activities of a database system and deserve more optimization efforts. In this paper, we propose to collect information about how tuples are joined in a query, called the query or join trace, during execution of a query. We intend to use this join trace to compute the selectivities of joins in all join orders for the query. We use existing operators, as well as new operators, to gather such information. We show that the trace gathered from a query is sufficient to compute the exact selectivities of all plans of the query. To reduce the overheads of generating a trace, we propose a sampling scheme that generates only a sample of the trace. Experimental results have shown that with only a small sample of the trace, accurate estimates of join selectivities can be obtained. The sample trace makes re-estimation of join selectivities of a repetitive query efficient and accurate.

With the onset of the semantic web, the problem of making semantic content effectively searchable for the general public emerges. Demanding an understanding of ontologies or familiarity with a new query language would likely frustrate semantic web users and prevent widespread success. Given this need, this thesis describes AskOntos, which is a system that uses extraction ontologies to convert conjunctive, free-form queries into structured queries for semantically annotated web pages. AskOntos then executes these structured queries and provides answers as tables of extracted values. In experiments conducted AskOntos was able to translate queries with a precision of 88% and a recall of 81%.

No description available.

No description available.