Search

It is a popular practice to use materialized intermediate results to improve the perfor- mance of RDBMSes. Work in this area has focused either optimisers matching existing materialized results in the cache and selecting intermediate results from a plan to survive the plan execution. To our knowledge, few attempts have been made to create plans with cached intermediate results in mind, and none that make any attempt to deduplicate the stored data to alleviate the storage cost of maintaining possibly large queries. We built FluiDB to explore a novel approach to integrating the selection of materialized results with the planner to optimize the logical representation of data in memory. FluiDB materializes common intermediate results and deduplucates data to alleviate the cost of maintaining them. This is achieved by introducing reversible operations: versions of normal relational operators that may produce complementary tables alongside the normal output, that allow the reconstruction of the input relations. A planner aware of such operations can build query plans that dynamically adapt the data layout to the plan under a constrained memory budget. This thesis revolves around four main chapters, each of which describes in detail a different part of FluiDB and a final one that goes into evaluation of the system. The first chapter focuses on query processing and the relational algebra semantics that FluiDB operates under. FluiDB parses queries into DAGs of sub-queries connected by reversible operators. Each such graph of the workload is merged into a global query graph that is used to infer properties of each relation like cardinality and extent. The next chapter is dedicated to the planner and a novel monad for weighted backtracking that the planer is based on. The planner attempts to generate a plan by traversing the query graph so that, besides solving the query at hand, it leaves in memory a curated set of queries aiming to maximize the amortized performance of the workload being run. In this chapter, the garbage collector is also discussed, which is the part of the planner responsible for inserting plan fragments that delete nodes when required such that the available storage budget is respected while no information is lost from the database. After that, we go into Antisthenis, a framework we built for defining incremental com- putation systems. Antisthenis is used to build modules of the planner that efficiently determine whether a relation materializable, and estimate the cost of materializing a relation, given a set of materialized relations. Besides computation reuse, Antisthenis is able to prune the computation taking advantage of properties of the operators involved like absorbing group elements and bounded partial results. These techniques are also used to allow evaluation of some classes of self-referential computations. The final chapter about the FluiDB architecture describes the transpilation of plans gen- erated by the planner to C++, as well as the supporting libraries that enable the tran- spilation of queries to highly specialized C++ code, and the low level data organization of the database. The thesis closes with a chapter that describes our methods for benchmarking and some experimental results.

This thesis presents strategies to improve the query evaluation performance over huge volumes of relational-like data that is stored in the memory space of managed applications. Storing and processing application data in the memory space of managed applications is motivated by the convergence of two recent trends in data management. First, dropping DRAM prices have led to memory capacities that allow the entire working set of an application to fit into main memory and to the emergence of in-memory database systems (IMDBs). Second, language-integrated query transparently integrates query processing syntax into programming languages and, therefore, allows complex queries to be composed in the application. IMDBs typically serve as data stores to applications written in an object-oriented language running on a managed runtime. In this thesis, we propose a deeper integration of the two by storing all application data in the memory space of the application and using language-integrated query, combined with query compilation techniques, to provide fast query processing. As a starting point, we look into storing data as runtime-managed objects in collection types provided by the programming language. Queries are formulated using language-integrated query and dynamically compiled to specialized functions that produce the result of the query in a more efficient way by leveraging query compilation techniques similar to those used in modern database systems. We show that the generated query functions significantly improve query processing performance compared to the default execution model for language-integrated query. However, we also identify additional inefficiencies that can only be addressed by processing queries using low-level techniques which cannot be applied to runtime-managed objects. To address this, we introduce a staging phase in the generated code that makes query-relevant managed data accessible to low-level query code. Our experiments in .NET show an improvement in query evaluation performance of up to an order of magnitude over the default language-integrated query implementation. Motivated by additional inefficiencies caused by automatic garbage collection, we introduce a new collection type, the black-box collection. Black-box collections integrate the in-memory storage layer of a relational database system to store data and hide the internal storage layout from the application by employing existing object-relational mapping techniques (hence, the name black-box). Our experiments show that black-box collections provide better query performance than runtime-managed collections by allowing the generated query code to directly access the underlying relational in-memory data store using low-level techniques. Black-box collections also outperform a modern commercial database system. By removing huge volumes of collection data from the managed heap, black-box collections further improve the overall performance and response time of the application and improve the application’s scalability when facing huge volumes of collection data. To enable a deeper integration of the data store with the application, we introduce self-managed collections. Self-managed collections are a new type of collection for managed applications that, in contrast to black-box collections, store objects. As the data elements stored in the collection are objects, they are directly accessible from the application using references which allows for better integration of the data store with the application. Self-managed collections manually manage the memory of objects stored within them in a private heap that is excluded from garbage collection. We introduce a special collection syntax and a novel type-safe manual memory management system for this purpose. As was the case for black-box collections, self-managed collections improve query performance by utilizing a database-inspired data layout and allowing the use of low-level techniques. By also supporting references between collection objects, they outperform black-box collections.

Sensor networks comprise of a collection of resource-constrained, low cost, sometimes fragile wireless motes which have the capability to gather information about their surroundings through the use of sensors, and can be conceived as a distributed computing platform for applications ranging from event detection to environmental monitoring. A Sensor Network Query Processor (SNQP) is a means of collecting data from sensor networks where the requirements are defined using a declarative query language with a set of Quality of Service (QoS) expectations. As sensor networks are often deployed in hostile environments, there is a high possibility that the motes could break or that the communication links between the motes become unreliable. SNQP Query Execution Plans (QEPs) are often optimised for a specific network deployment and are designed to be as energy efficient as possible whilst ensuring the QEPs meet the QoS expectations, yet little has been done for handling the situation where the deployment itself has changed since the optimisation in such a way as to make the original QEP no longer efficient, or unable to operate. In this respect, the previous work on SNQPs has not aimed at being resilient to failures in the assumptions used at compilation/optimisation time which result in a QEP terminating earlier than expected. This dissertation presents a collection of approaches that embed resilience into a SNQP generated QEPs in such a way that a QEP operates for longer whilst still meeting the QoS expectations demanded of it, thereby resulting in a more reliable platform that can be applicable to a broader range of applications. The research contributions reported here include (a) a strategy designed to adapt to predictable node failures due to energy depletion; (b) a collection of strategies designed to adapt to unpredictable node failures; (c) a strategy designed to handle unreliable communication channels; and (d) an empirical evaluation to show the benefits of a resilient SNQP in relation to a representative non-resilient SNQP.

We study representation systems for relational data based on relational algebra expressions with unions, products, and singleton relations. Algebraic factorisation using the distributivity of product over union allows succinct representation of many-to-many relationships; further succinctness is brought by sharing repeated subexpressions. We show that these techniques are especially applicable to results of conjunctive queries. In the first part of the dissertation we derive tight asymptotic size bounds for two flavours of factorised representations of results of conjunctive queries. Any conjunctive query is characterised by rational parameters that govern the factorisability of its results independently of the database instance. We relate these parameters to fractional edge covers and fractional hypertree decompositions. Factorisation naturally extends from relational data to its provenance. We characterise conjunctive queries by tight bounds on their readability, which captures how many times each input tuple is used to contribute to an output tuple, and we define syntactically the class of queries with bounded readability. In the second part of the dissertation we describe FDB, a relational database engine that uses factorised representations at the physical layer to reduce data redundancy and boost query performance. We develop algorithms for optimisation and evaluation of queries with selection, projection, join, aggregation and order-by clauses on factorised representations. By introducing novel operators for factorisation restructuring and a new optimisation objective to maintain intermediate and final results succinctly factorised, we allow query evaluation with lower time complexity than on flat relations. Experiments show that for data sets with many-to-many relationships, FDB can outperform relational engines by orders of magnitude.

Sensor networks comprise resource-constrained wireless nodes with the capability of gathering information about their surroundings and have recently risen to prominence with the promise of being an effective computing platform for diverse applications, ranging from event detection to environmental monitoring. The database community proposed the use of sensor network query processors (SNQPs) as means to meet data collection requirements using a declarative query language. Declarative queries posed against a sensor network constitute an effective means to repurpose sensor networks and reduce the high software development costs associated with them. The range of sensor network applications is very broad. Such applications have diverse, and often conflicting, QoS expectations in terms of the delivery time of results, the acquisition interval at which data is collected, the total energy consumption of the deployment, or the network lifetime. The conflicting nature of these desiderata is aggravated by the resource-constrained nature of sensor networks as a computing fabric, making it particularly challenging to reconcile the trade-offs that arise. Previously, SNQPs have been focussed on evaluating queries as energy-efficiently as possible. There has been comparatively less work on attempting to meet a broad range of optimization goals and constraints that captured these QoS expectations. In this respect, previous work in SNQP has not aimed at being general purpose across the breadth of applications to which sensor networks have been applied. This PhD dissertation presents an approach for enabling QoS-awareness in SNQPs so that query evaluation plans are generated that exhibit good performance for a broader range of sensor network applications in terms of their QoS expectations. The research contributions reported here include (a) a functional decomposition of the decision-making steps required to compile a declarative query into a query evaluation plan in a sensor network setting; (b) algorithms to implement these decision-making steps; and (c) an empirical evaluation to show the benefits of QoS-awareness compared to a representative fixed-goal SNQP.

Videos have been widely adopted across various applications, highlighting the increasing importance of database management systems that can support video queries. However, achieving effective query processing in video database management systems is challenging due to factors such as the substantial size of video databases and the unstructured nature of video content. To address these challenges, I demonstrate that video-specific algorithms that support query processing in video database management systems are essential for performance (accelerating video selection queries), policy (balancing competing query requirements), and explanation (supporting queries for real-world explanation). To support this statement, my dissertation focuses on four key parts: (1) building a new indexing mechanism that captures visual similarity for filtering items that are likely to satisfy the query predicate, (2) developing a video degradation-accuracy profiling system, helping administrators to choose an appropriate degradation setting for competing requirement trade-off in video analytics, (3) proposing a commonsense knowledge-enhanced indexing method, which initially constructs a lossy but inexpensive index and subsequently patches it to quickly identify query result candidates, and (4) implementing a causal inference system that uncovers confounding variables within images to solve confounding bias and compute more accurate average treatment effects (ATE).

Today, data-driven analysis and applications exploit vast streams of data that are perpetually generated and collected from numerous data sources. Such a surge in data production, which has reached over 10,000 Exabytes, is driving transformative advancements in sectors such as transportation, emergency services, and health and wellness. Before data is queried and used by downstream data-driven analytical tasks, various computationally-intensive computations often need to be performed. Such tasks include data cleaning, data integration, and/or data enrichment operations that often execute expensively AI/ML models incur non-trivial costs. Such computationally expensive tasks can often not be performed at data ingestion time due to the rate at which data is produced. Periodic, offline computation is also infeasible due to the volume of data. Query processing in such a situation requires careful incorporation and co-optimization of computationally expensive operations into the query engine that can streamline query analysis and enhance execution efficiency in terms of time and resources. The goal of this thesis is to develop mechanisms to support computationally expensive operations (e.g., enrichment, imputations, information extraction, data interpretation) within data management systems in order to support interactiveanalysis. While the techniques developed in the thesis have wide applicability, our focus is on emerging smart space applications. Smart spaces consist of sensor-embedded physical spaces that capture and represent the dynamic state of the physical infrastructure, and that of people interacting with the physical infrastructure, and with each other. Data management in smart spaces opens several new challenges one of which is the ability to support interactive analytics on very large volumes of data being captured at large velocities. The problems studied in this thesis draw its motivation from such challenges. In Chapter 3 we develop a query-time missing value imputation framework, entitled LaZy Imputation during query Processing (ZIP), which modifies relational operators to be imputation-aware in order to minimize the joint cost of imputing and query processing. The modified operators use a cost-based decision function to determine whether to invoke imputation or to defer it to downstream operators to resolve missing values. The modified query processing logic ensures results with deferred imputations are identical to those produced if all missing values were imputed first. ZIP includes a novel outer-join-based approach to preserve missing values during execution, and a bloom filter-based index to optimize the space and running overheads. Extensive experiments on both real and synthetic data sets demonstrate orders-of-magnitude improvements in query processing when ZIP-based deferred imputations are used. In Chapter 4, we present a system for automated Predicate LeArning at QUery timE (PLAQUE), that automatically infers new predicates while running queries in order to accelerate query execution. PLAQUE represents a significant departure from prior work on learning predicates which are either limited to queries containing selection conditions on certain columns (e.g., columns involved in a join in the query), or require statistics to be collected and maintained from data, such as range set. We identify several opportunities to learn predicates from various query conditions, such as aggregation, equi join, theta join, and group by/having conditions at query time. In PLAQUE, learned predicates are pushed down to the optimal positions in a given query plan tree in order to maximize their benefits. A novel partial-order-based approach is developed for such a purpose. Furthermore, we introduce a pre-learning technique for predicate inference before query optimization, which synergistically combines with the runtime learning approach of PLAQUE to further enhance performance. Comprehensive evaluations on both synthetic and real datasets demonstrate that our learned predicates accelerate query execution by an order of magnitude, and the improvements are even higher (two orders of magnitude) when computationally expensive operators (imputations/enrichment) in the form of User-Defined Functions (UDFs) are utilized in queries. PLAQUE, thus, significantly benefits data-driven analytical applications. In Chapter 5, we shift the interest to applying techniques developed in the thesis to data processing and query analytics in smart spaces. We first develop LOCATER, an indoor localization solution based on WiFi connectivity data. LOCATER is zero-cost, accurate (90% accuracy), and passive without the need to install any new hardware in the building or new software on users' phones. LOCATER has already been deployed and is operational in the USA and India, across three distinct locations (UCI, BSU, Plaksha), and in over 40 UCI buildings for four years. LOCATER serves as a representative compute-intensive task in building smart space applications. We conduct a case study by building two applications using LOCATER, occupancy, and contact tracing applications. Our case study clearly demonstrates the benefits of using our query processing techniques -- ZIP and PLAQUE in building campus-scale smart space applications. For instance, we show queries without these optimizations, which were impractical to execute interactively can be used for interactive analytics.

Data has been growing at an unprecedented rate in the past two decades. As a result, systems that store, process, and analyze data have become mission-critical. Crucial to the performance of data systems is the query optimizer, which translates high-level declarative queries (e.g., SQL) into efficient execution plans. However, query optimization is highly complex, leading to two key challenges. First, optimizers use a myriad of hand-designed heuristics to tame the complexity, but heuristics leave performance on the table. Second, optimizers are highly costly to develop, where human experts may spend months writing a first version and years refining it.This dissertation applies and enhances machine learning advances to tame the complexity in query optimization. First, we remove for the first time decades-old and accuracy-impacting heuristics in cardinality estimation—the Achilles’ heel of optimizers where heuristics particularly abound—thereby significantly improving estimation accuracy. We present Naru and NeuroCard, two cardinality estimators based on self-supervised learning advances that learn the joint data distribution of tables without any heuristic assumptions. Our estimators improve the accuracy of cardinality estimation by orders of magnitude compared to the prior state of the art. Second, we show that automatically learning to optimize SQL queries, without learning from an expert-designed optimizer, is both possible and efficient, thereby potentially alleviating the high development cost. We introduce Balsa, a deep reinforcement learning agent that automatically learns to optimize SQL queries by trial-and-error. Balsa can learn to outperform the optimizers of PostgreSQL—one of the most popular database systems—and a commercial database engine with a few hours of learning.Overall, by enhancing machine learning advances with new, carefully designed systems and ML techniques, this line of work improves existing query optimizers, while opening the possibility of alleviating the complex optimization in future environments and engines.

Nowadays, efficient and effective processing over massive stream data has attracted much attention from the database community, which are useful in many real applications such as sensor data monitoring, network intrusion detection, and so on. In practice, due to the malfunction of sensing devices or imperfect data collection techniques, real-world stream data may often contain missing or incomplete data attributes. In this dissertation, we have been formalizing and tackling a novel and important problem, named query processing over incomplete data streams (P-iDS), which retrieves desired objects (in the presence of missing attributes) with high confidences from incomplete data streams. In order to tackle the P-iDS problem, we have proposed a general solution framework that can be used for handling all query operators (e.g., entity resolution) over incomplete data streams. Specifically, we have studied the P-iDS problem for 4 representative operators, entity resolution, skyline, join and top-k. For each studied query operator over incomplete data streams, we have designed efficient approaches to impute missing attributes of objects from incomplete data streams via effective data imputation rules, proposed effective pruning strategies to reduce the search space, devised cost-model-based index structures to facilitate the data imputation and query computation at the same time, and integrated our proposed techniques into an efficient P-iDS query answering algorithm. Extensive experiments over real and synthetic data sets have been conducted to evaluate efficiency and effectiveness of our proposed P-iDS processing approach.

Recently, database users have begun to use cloud database services to outsource their databases. The reason for this is the high computation speed and the huge storage capacity that cloud owners provide at low prices. However, despite the attractiveness of the cloud computing environment to database users, privacy issues remain a cause for concern for database owners since data access is out of their control. Encryption is the only way of assuaging users’ fears surrounding data privacy, but executing Structured Query Language (SQL) queries over encrypted data is a challenging task, especially if the data are encrypted by a randomized encryption algorithm. Many researchers have addressed the privacy issues by encrypting the data using deterministic, onion layer, or homomorphic encryption. Nevertheless, even with these systems, the encrypted data can still be subjected to attack. In this research, we first propose an indexing scheme to encode the original table’s tuples into bit vectors (BVs) prior to the encryption. The resulting index is then used to narrow the range of retrieved encrypted records from the cloud to a small set of records that are candidates for the user’s query. Based on the indexing scheme, we then design three different models to execute SQL queries over the encrypted data. The data are encrypted by a single randomized encryption algorithm, namely the Advanced Encryption Standard AES-CBC. In each proposed scheme, we use a different (secure) method for storing and maintaining the index values (BVs) (i.e., either at user’s side or at the cloud server), and we extend each system to support most of relational algebra operators, such as select, join, etc. Implementation and evaluation of the proposed systems reveals that they are practical and efficient at reducing both the computation and space overhead when compared with state-of-the-art systems like CryptDB.

The past decade has witnessed the proliferation of new ways to ingest, store, index, and query data. This explosion was driven by the needs of the modern applications, including social media, popular web services, and IoT sensors, characterized by high volumes and a rapid rate of incoming data. To cope with such high arrival rates, modern systems rely on the Log-Structured Merge Tree (LSM) storage model that uses sequential I/O instead of in-place updates. In addition to handling incoming data, LSM-based systems should provide useful analytics for their users, which in turn requires accurate statistics.The first contribution of this thesis is developing a lightweight approach to collect and maintain concise statistical representations of the data in LSM-based systems so that it can be later used to drive cost-based optimizer decisions. In particular, we consider two problems, collecting statistics on indexed columns (which orders the stream of records based on the index key), as well as on non-indexed (unordered) columns. For each case, appropriate statistical summaries are considered so that the overall overhead on the system’s critical path remains low, thus not affecting the ingestion process.Recent hardware trends such as growing main memory capacity, stagnating CPU speeds, and increasing usage of parallel architectures have also influenced the design of data processing systems. These advances in hardware allow analyzing large datasets entirely in memory, which requiresspecialized algorithms to process memory-resident data. Apart from the algorithms implemented on traditional CPU architectures, implementations leveraging fine-grained hardware multithreading on FPGAs have been recently proposed. However, up to this moment, there has been a lack of studies directly comparing the performance of these two approaches.The second part of the thesis is devoted to a comparative study of common analytical operations (joins, aggregations, selections) for in-memory workloads using both multicore CPU and hardware multithreading approaches. We present a thorough experimental evaluation and show that implementations that use hardware multithreading outperform state-of-the-art CPU-based algorithms in terms of raw throughput in many cases while achieving much better memory bandwidth utilization.

Recent years have witnessed a rapid growth in the amount of generated data, owing to the emergence of Internet of Things (IoT). Processing such huge data on traditional computing systems is highly inefficient, mainly due to the limited cache capacity and memory bandwidth. Processing in-memory (PIM) is an emerging paradigm which tries to address this issue. It uses memories as computing units, hence reducing the data transfers between memory and processing cores. However, the application of present PIM techniques is restricted by their limited functionality and inability to process large amounts of data efficiently. In this thesis, we propose novel techniques which exploit the analog properties of emerging memory technologies. Not only do these support more complex functions such as addition, multiplication, and search but also manage and process large data more efficiently. We present a new blocked PIM architecture which uses inter-block interconnects to accelerate data intensive processing. We also introduce a heterogeneous architecture having general purpose cores and PIM-enable memory and a data-dependent task allocation scheme for it. We also apply application specific optimizations and approximation techniques to further design accelerators for neural networks and database query systems. While we design a multiplication-by-constant hardware for neural networks, query processing is accelerated by a novel in-memory nearest search technique. Our neural network accelerator achieves 113.9x higher energy efficiency and 56.3x speedup as compared to AMD GPU. Also, the query accelerator provides 49.3x performance speedup and 32.9x energy savings as compared to recent Intel CPU.

The prevalence of location tracking systems has resulted in large volumes of spatiotemporal data generated every day. Addressing reachability queries on such datasets is important for a wide range of applications, such as security monitoring, surveillance, public health, epidemiology, social networks, etc. While traditional graph reachability queries have been studied extensively, little work exists on processing reachability queries on large disk-resident trajectory datasets. What makes spatiotemporal reachability queries different and challenging is that the associated graph is dynamic and space-time dependent. As the spatiotemporal dataset becomes very large over time, a solution needs to be I/O-efficient.Given two objects OS and OT, and a time interval I, a spatiotemporal reachability query identifies whether information (or physical item etc.) could have been transferred from OS to OT during I (typically indirectly through a chain of intermediate transfers). In the previous research on spatiotemporal reachability queries, it is assumed that information can be passed from one object to another instantaneously, which may not always be the case. In this dissertation, we introduce several novel reachability-based queries. For all our problems, we assume that ‘instant transfer’ is not possible, and consider reachability queries with different types of delays (processing and transfer delays), as well as queries with information decay. First, we propose the RICC (Reachability Index Construction by Contraction) framework for processing spatiotemporal reachability queries with processing delays. Next, using this framework, we address reachability queries with transfer delays (or meetings). For this purpose we design two algorithms, RICCmeetMin that precomputes some reachability events considering the shortest valid meetings duration, and RICCmeetMax which uses the longest possible meeting duration.Our next work considers reachability queries under the scenario of information decay. Such queries arise when the value of information that travels through the chain of intermediate objects decreases with each transfer. This leads to an interesting extension: if there are many different sources of information, the aggregate value of information an object can obtain varies. As a result, we examine a top-k reachability problem, identifying the k objects with the highest accumulated information. All proposed algorithms consist of two stages: preprocessing and query processing. To prune the search space during query time, they precompute and store some reachability information. This approach allows for efficient reachability query processing on large disk-resident datasets.

A sorted list is a collection of $\langle$ID, value$\rangle$ pairs sorted either by ID (called an ID-sorted list) or value (called a value-sorted list). Although simple, it is surprisingly the fundamental structure in a wide range of data management systems, e.g., databases, search engines, graph systems, and high-dimensional similarity search systems. Existing query processing over sorted lists were mainly optimized for past hardware, e.g., slow CPUs, small DRAM, and slow disks. However, with the emergence of new hardware, e.g., fast multi-core CPUs, big DRAM, fast SSDs, we find that many of existing design decisions become obsolete.Motivated by this, in this dissertation, we investigate how to best leverage the characteristics of emerging hardware to accelerate query processing over sorted lists. First, we studied the impact of big memory and modern CPUs to ID-sorted list compression. We designed a new compression called MILC, which is SIMD-aware, cache-aware, and most importantly can answer queries directly over compressed lists. Second, we studied the impact of fast SSDs to ID-sorted list intersection. We developed and evaluated SSD-aware intersection algorithms that can skip unnecessary data pages to leverage SSDs’ fast random accesses. Finally, we folded the proposed hardware-specific techniques into a real-world modern application -- mass spectrometry search -- that involves query processing on both ID-sorted lists and value-sorted lists. We also developed domain-specific and data-specific optimizations besides hardware-specific optimizations. Putting them together, our new mass spectrometry search system is significantly faster than state-of-the-art systems.

Developers, researchers, and practitioners have been building a myriad of applications to analyze microblogs data, e.g., tweets, online reviews, and user comments. Examples of such applications include citizen journalism, events detection and analysis, geo-targeted advertising, medical research, and studying social influences in social sciences. Building such applications require data management infrastructure to deal with microblogs, including data digestion, indexing, and main-memory management. The lack of such infrastructure hinders the scalability and the widespread of such applications especially among users who are not computer scientists. This thesis proposes Kite; an end-to-end system that is able to manage microblogs data at a large scale. Using Kite, developers and practitioners can simply write SQL-like queries without worrying about the internal data management issues. Internally, Kite is equipped with scalable indexing and main-memory management techniques to support top-k temporal, spatial, keyword, and trending queries on both very recent data and historical data. Kite indexer supports scalable digestion and retrieval for incoming fast data in real time. Recent data are digested in efficient main-memory index structures. Kite in-memory index structure are able to scale up a single machine indexing capabilities to handle the overwhelming amount of data in real time. Meanwhile, Kite memory manager is monitoring the memory contents and smartly decides on which data is regularly moved to disk. This is accomplished through effective memory flushing policies that are designed for top-k query workloads, which are popular on microblogs data. Both in-memory and in-disk data are queried seamlessly through efficient retrieval techniques that are encapsulated in Kite query processor. The query processor exploits the top-k ranking function to early prune the search space and reduce the query latency significantly. Kite is open-sourced and available to the community to build on (http://kite.cs.umn.edu). Extensive experimentation on different Kite components show the efficiency and the effectiveness of the proposed techniques to manage microblogs data at scale.

Since their inception, computer systems for managing and processing data are in a constant need for evolution to meet the requirements of an increasingly more connected world, and efficiently utilize a rapidly changing hardware. Driven by the internet and the growing popularity of utility computing, a current challenge is handling workloads from data processing services that are exported to many users. In this case, what is desirable is a robust performance across a wide spectrum of workloads both in terms of size and complexity. For instance, as part of strict service level agreements, response time guarantees for all requests must be met even at peeks times under high query and update loads. Moreover, with the large and diverse set of users, the format and shape of user requests evolve more rapidly. This entails the need for data processing systems and methods that provide high and robust performance for dynamic and unpredictable workloads. Making efficient use of available hardware resources is also becoming an increasingly more difficult and an important challenge, as we are at the onset of the end of an era of predictable yearly gains in performance. This dissertation addresses these challenges and presents several techniques for efficient handling large and complex workloads with analytical and transactional parts on modern hardware. The first part presents and evaluates a method for shared evaluation of relational join operations that enables efficient handling of large analytical workloads. This is achieved by using techniques that: 1) minimize redundant work by aggressively batching and sharing data and computation across a large set of concurrent analytical operations; and 2) make efficient use of hardware by minimizing the amount of computation and memory transfers performed per processed data item. The second part presents how large analytical and transactional workloads are handled in isolation, both within a machine and across multiple machines, by minimizing the effect that workloads have on each other’s performance. This is achieved by combining the following techniques: primary-secondary replication, dedicating hardware resources, i efficient and lightweight method of update propagation, and batch scheduling of updates and queries. This allows for strong performance guarantees for both the transactional and analytical parts of complex workloads. Finally, this dissertation investigates ways of dealing with increased parallelism of multicore hardware by analyzing methods for concurrent access to indexing data-structures used in data management systems. In particular, the use of hardware transactional memory is considered as a way to simplify development of concurrent indexes as opposed to the existing error-prone approaches of lock-free programming. It is shown that hardware transactional memory can not replace lock-free approaches, however it can be used to simplify their development. Implemented in a single system called BatchDB, these techniques allow for an efficient use of hardware and high and robust performance for large analytical and transactional workloads with strong guarantees for performance isolation.

As data volumes continue to expand, analytics approaches that require exhaustively scanning data sets become untenable. For this reason, modern analytics systems employ data skipping techniques to avoid looking at large volumes of irrelevant data. By maintaining some metadata for each block of data, a query may skip a data block if the metadata indicates that the block does not contain relevant data. The effectiveness of data skipping, however, depends on how the underlying data are organized into blocks. In this dissertation, we propose a fine-grained data layout framework, called ``Generalized Skipping-Oriented Partitioning and Replication'' (GSOP-R), which aims to maximize query performance through aggressive data skipping. Based on observations of real-world analytics workloads, we find that the workload patterns can be summarized as a succinct set of features. The GSOP-R framework uses these features to transform the incoming data into a small set of feature vectors, and then performs clustering algorithms using the feature vectors instead of the actual data. A resulting GSOP-R layout scheme is highly flexible. For instance, it allows different columns to be horizontally partitioned in different ways and supports replication of only parts of rows or columns. We developed several designs for GSOP-R on Apache Spark and Apache Parquet and then evaluated their performance using two public benchmarks and several real-world workloads. Our results show that GSOP-R can reduce the amount of data scanned and improve end-to-end query response times over the state-of-the-art techniques by a factor of 2 to 9.

The motivation of the current study was to design an algorithm that can speed up the processing of a query. The important feature is generating code dynamically for a specific query.We present the technique of code generation that is applied to query processing on a raw file. The idea was to customize a query program with a given query and generate a machine- and query-specific source code. The generated code is compiled by GCC, Clang or any other C/C++ compiler, and the compiled file is dynamically linked to the main program for further processing. Code generation reduces the cost of generalizing query processing. It also avoids the overhead of the conventional interpretation during achieve high performance.

Organizations and companies archive many versions of digital data such as web pages, internal emails and so on. Such data is critical for internal investigation, regulatory compliance, and electronic discovery. It is estimated that electronic discovery market that leverages archival data will reach $9.9 billions globally in 2017. It is not uncommon for many businesses to retain archived collections for 10 to 15 years. How to archive these versioned data is worth to study and we are facing many challenges including 1) traditional index occupies too much space for versioned data, 2) traditional search is too slow on versioned data, and 3) how to guarantee high accuracy when improving efficiency in new architecture.In this dissertation, we take the opportunity of the fast development of information retrieval and tackle the problem by proposing a new multi-version search architecture with cache-conscious ranking optimization framework. Specifically, we will first discuss our new versioned search architecture. Then, we will talk about a cache-conscious online ranking algorithm to improve the online part. Finally, we will describe a framework to select best blocking methods and parameters for our algorithm to achieve best performance.Firstly, we present our new multi-version search architecture. We propose an approach that uses cluster-based retrieval to quickly narrow the search scope guided by version representatives at Phase 1 and develops a hybrid index structure with adaptive runtime data traversal to speed up Phase 2 search. The hybrid scheme exploits the advantages of forward index and inverted index based on the term characteristics to minimize the time in extracting positional and other feature information during runtime search. We compare several indexing and data traversal options with different time and space tradeoffs and describe evaluation results to demonstrate their effectiveness. The experiment results show that the proposed scheme can be up-to about 4x as fast as the previous work on solid state drives while retaining good relevance.Secondly, we talk about our 2D blocking algorithm to optimize the online ranking part of the system. Multi-tree ensemble models have been proven to be effective for document ranking. Using a large number of trees can improve accuracy, but it takes time to calculate ranking scores of matched documents. We investigate data traversal methods for fast score calculation with a large ensemble and propose a 2D blocking scheme for better cache utilization with simpler code structure compared to previous work. The experiments with several benchmarks show significant acceleration in score calculation without loss of ranking accuracy.Lastly, we describe a framework to fast select best blocking methods and parameters for our 2D blocking algorithm with the help of a full cache analysis. 2D blocking method is very helpful to improve online search efficiency. However, different traversal methods and blocking parameter settings can exhibit different cache and cost behavior depending on data and architectural characteristics. It is very time-consuming to conduct exhaustive search for performance comparison and optimum selection. We provide an analytic comparison of cache blocking methods on their data access performance for an approximation and propose a fast guided sampling scheme to select a traversal method and blocking parameters for effective use of memory hierarchy. The evaluation studies with three datasets show that within a reasonable amount of time, the proposed scheme can identify a highly competitive solution that significantly accelerates score calculation.In summary, we have proposed a new multi-version search architecture with cache-conscious ranking optimization for the online search part and a framework to help fast select best blocking methods and parameters with full cache analysis for the 2D blocking method. By proposing this new versioned search system, we can meet challenges from scalability, efficiency and accuracy in multi-version search, and we believe this work would be useful to future researchers in this direction.

In today's Internet, with the advent of cloud computing, there is a natural desire for enterprises, organizations, and end users to outsource increasingly large amounts of data to a cloud provider. Therefore, ensuring security and privacy is becoming a significant challenge for cloud computing, especially for users with sensitive and valuable data. Recently, many efficient and scalable query processing methods over encrypted data have been proposed. Despite that, numerous challenges remain to be addressed due to the high complexity of many important queries on encrypted large-scale datasets. This thesis studies the problem of privacy-preserving database query processing on structured data (e.g., relational and graph databases). In particular, this thesis proposes several practical and provable secure structured encryption schemes that allow the data owner to encrypt data without losing the ability to query and retrieve it efficiently for authorized clients. This thesis includes two parts. The first part investigates graph encryption schemes. This thesis proposes a graph encryption scheme for approximate shortest distance queries. Such scheme allows the client to query the shortest distance between two nodes in an encrypted graph securely and efficiently. Moreover, this thesis also explores how the techniques can be applied to other graph queries. The second part of this thesis proposes secure top-k query processing schemes on encrypted relational databases. Furthermore, the thesis develops a scheme for the top-k join queries over multiple encrypted relations. Finally, this thesis demonstrates the practicality of the proposed encryption schemes by prototyping the encryption systems to perform queries on real-world encrypted datasets.

Knowledge bases that summarize web information in RDF triples deliver many benefits, including support for natural language question answering and powerful structured queries that extract encyclopedic knowledge via SPARQL. Large scale knowledge bases grow rapidly in terms of scale and significance, and undergo frequent changes in both schema and content. Two critical problems have thus emerged: (i) how to support temporal queries that explore the history of knowledge bases or flash-back to the past; (ii) how to integrate knowledge from difference sources and improve the quality of integrated knowledge base while preserving the provenance information. In this dissertation, we propose a framework that supports knowledge integration, temporal query evaluation and user-friendly interfaces for large-scale knowledge bases. Towards this goal, we make the following contributions:(i) We propose SPARQLT, a temporal extension of structured query language SPARQL based on a point temporal model which simplifies the expression of temporal joins and eliminates the need for temporal coalescing. This approach makes possible an end-user interface HKB (Historical Knowledge Browser) where users can browse the evolution history of knowledge bases and express historical queries via simple by-example conditions in the infoboxes of Wikipedia pages.(ii) We have designed and implemented RDF-TX (RDF Temporal eXpress), an efficient system for managing temporal RDF data and evaluating SPARQLT queries. RDF-TX takes advantage of compressed Multiversion B+ trees to achieve fast evaluation of temporal queries. The experimental result demonstrates that our indexing and query optimization techniques deliver superior performance over other systems.(iii) We propose a framework for knowledge extraction and integration. We first introduce IBMiner, a novel NLP-based system that derives knowledge bases from free text and preserves the provenance of extracted triples. IBminer uses a deep NLP-based approach to extract subject-attribute-value triples from free text, and maps the attributes to those introduced in existing knowledge bases. Then we integrate public knowledge bases with the knowledge base generated by IBMiner into one of superior quality and coverage, called IKBStore. User-friendly interfaces are provided to manage the knowledge in IKBStore while maintaining provenance information.

In recent years, the world has seen an explosion in the amount of data being generated. Google proposed the MapReduce framework to allow programmers easily process massive amounts of data in parallel using a cluster of shared-nothing commodity machines. What started out as a tool for human efficiency subsequently began to be used as an intermediate representation for queries compiled from higher-level declarative languages. In this thesis, we present an alternate software stack for building scalable Big Data systems. We specifically focus on two parts of the stack. Hyracks is a new partitioned-parallel runtime layer that provides an efficient, generalized model for executing data-processing jobs on a cluster of commodity machines. Algebricks is a compiler framework that helps to build high-level declarative language compilers for parallel processing on top of Hyracks.

Influence computation plays a vital role in various applications such as marketing, cluster and outlier analysis and decision support systems. According to different preferences metric applied, several types of queries have been proposed and studied in the past decades. In this thesis, we provide efficient solutions for influence computation by considering the following query types: reverse k nearest neighbour (RkNN) query and its variation impact set query and distance based reverse top-k query. Below is a brief description of our contributions. We first study the RkNN query. We propose a novel algorithm called SLICE that utilizes the strength of region-based pruning and overcomes its limitation. SLICE is significant more efficient than the existing algorithms. We also propose an improved version of the most popular RkNN algorithm TPL called TPL++ that replaces the original filtering technique with a carefully developed cheaper yet more powerful filtering strategy and significant improves its performance. Besides, we are the first to present a comprehensive experimental study comparing the most notable RkNN algorithms. We also study a variation of RkNN query by relaxing the constraint that all users have the same value of k. We formally define such query as impact set query. We are the first to study the problem using query logs. We identify the limitations of the existing algorithms and propose an efficient algorithm that utilizes a novel access order and none-trivial observations to address these limitations. Our extensive experimental study demonstrates that our algorithm significantly outperforms existing algorithms. Last, we study distance based reverse top-k query which is a natural extension of reverse k nearest neighbors queries involving multiple criteria. We provide a pruning and verification based framework to answer distance based reverse top-k query and several optimizations are proposed to improve the efficiency.

This dissertation focuses on several important problems in query answering over a single or multi-source database. The first part of this work focuses on the challenges faced in querying a distributed set of data sources. An Online Answering Systems for Integrated Sources (OASIS) is presented which considers source coverage, overlap, and cost to order source accesses such that answers are returned as soon as possible. The first component of OASIS is a fast and scalable method for estimating source overlaps. The second component utilizes overlap estimates and two ordering strategies (static and dynamic) to order source accesses. The last component applies several heuristics to select additional overlap statistics to compute with the goal of obtaining a better source ordering. The efficiency and effectiveness of the proposed system are demonstrated through an extensive experimental evaluation. While the first part of the dissertation focuses on multi-source query answering, the second part of the dissertation focuses on single-source query answering. First, a candidate document ordering strategy is presented followed by a query processing approach for XML documents and queries. The first component considers a candidate document ordering strategy to minimize the expected time to the first k matches. The optimization problem is considered for applications which contain document precedence constraints which restrict the order in which candidate documents must be processed. The second component presents a unified method for solving three important problems in XML structural matching, namely, Filtering, Query Processing, and Tuple-Extraction. The queries and XML documents are represented using a sequential encoding, referred to as Node Encoded Tree Sequences (NETS). The unified solution for the three problems is composed of two procedures, subsequence matching and structural matching, which can be executed concurrently or sequentially depending on the problem. The solution for subsequence matching is based on the dynamic programming recurrence relation for the Longest Common Subsequence (LCS) problem. For structural matching, a new necessary and sufficient condition is presented which provides a simple verification procedure. In addition to using a unified framework, (for easier implementation and maintenance), experimental results show that the proposed algorithms outperform state of the art approaches for the three XML processing problems.

Abstract: The Wireless Sensor Networks (WSNs) have emerged as a new paradigm for collecting and processing data from physical environments, such as wild life sanctuaries, large warehouses, and battlefields. Users can access sensor data by issuing queries over the network, e.g., to find what are the 10 highest temperature values in the network. Typically, a WSN operates by constructing a logical topology, such as a spanning tree, built on top of the physical topology of the network. The constructed logical topology is then used to disseminate queries in the network, and also to process and return the results of such queries back to the user. A major challenge in this context is prolonging the network's lifetime that mainly depends on the energy cost of data communication via wireless radios, which is known to be very expensive as compared to the cost of data processing within the network. In this research, we investigate some of the core problems that deal with the different aspects of in-network query processing in WSNs. In that context, we propose an efficient filtering based algorithm for the top-k query processing in WSNs. Through a systematic study of the top-k query processing in WSNs we propose several solutions in this thesis, which are applicable not only to the top-k queries, but also to in-network query processing problems in general. Specifically, we consider broadcasting and convergecasting, which are two basic operations that are required by many in-network query processing solutions. Scheduling broadcasting and convergecasting is another problem that is important for energy efficiency in WSNs. Failure of communication links, which are common in WSNs, is yet another important issue that needs to be addressed. In this research, we take a holistic approach to deal with the above problems while processing the top-k queries in WSNs. To this end, the thesis makes several contributions. In particular, our proposed solutions include new logical topologies, scheduling algorithms, and an overall sophisticated communication framework, which allows to process the top-k queries efficiently and with increased reliability. Extensive simulation studies reveal that our solutions are not only energy efficient, saving up to 50% of the energy cost as compared to the current state-of-the-art solutions, but they are also robust to link failures.

Location-based services (LBS for short) providers require users' current locations to answer their location-based queries, e.g., range and nearest-neighbor queries. Revealing personal location information to potentially untrusted service providers could create privacy risks for users. To this end, our objective is to design a privacy-preserving framework for LBS where users can obtain LBS and preserve their location privacy. In this thesis, we propose privacy-preserving LBS frameworks for different environments: (1) client-server environments in Euclidean space (the Casper system), (2) client-server environments in road networks, (3) mobile peer-to-peer environments, and (4) location monitoring services in wireless sensor networks (the TinyCasper system). In general, these frameworks have two main modules, namely, location anonymization and privacy- aware query processing. The location anonymization module blurs an user's exact location into a cloaked area (or a cloaked road segment set in road network environments) that satisfies the user's privacy requirements. The proposed frameworks support the two most popular privacy requirements, k-anonymity, i.e., a user is indistinguishable among k users, and minimum area Amin (or minimum total length of a cloaked road segment set), i.e., the size of a cloaked area is at least Amin. The user is able to specify his/her privacy requirements in a privacy profile and change the privacy profile at any time. The privacy-aware query processing module is embedded inside a database server to provide LBS based on cloaked areas (or cloaked road segment sets). To prove the concept of our privacy-preserving LBS frameworks, we implement system prototypes for Casper and TinyCasper. For each proposed privacy-preserving LBS framework, we conduct extensive experiments to evaluate the performance of its location anonymization and privacy-aware query processing modules. All experiment results show that the proposed frameworks are scalable and efficient with respect to large numbers of users, large numbers of queries, and various privacy requirements, and they provide high quality services in terms of the accuracy of query answers and the query response time.

Uncertainty is inherent in data collected from many important, novel applications such as large sensor networks, WWW, data cleanings and integration, environmental surveillance and market analysis. The sources of uncertainty in these applications vary from data randomness and incompleteness, limitations of measuring equipments, delay or loss in data transfer. As a rapidly growing amount of uncertain data is collected, it is highly desirable to conduct advanced analysing and query processing over uncertain data. The following five important aspects for uncertain data management are investigated in this thesis. We study the problem of probabilistic top-k skyline queries. A model for the top-k skyline operator is proposed combining the feature of top-k objects and that of skyline. Based on this model, an efficient exact algorithm and a randomized algorithm with & -approximation guarantee are developed for discrete and continuous cases, respectively. We extend skyline operator to streaming environment and study the problem of probabilistic skyline queries over sliding windows. We characterize the minimum information needed in continuously computing probabilistic skyline against a sliding window. Then novel, efficient techniques are developed to process a continuous, probabilistic skyline query. As the top-k dominating query is another important method for multi-criterion decision making, we study lop-k dominating queries on uncertain data. The problem is formally defined in a probability threshold fashion. Then, a threshold-based algorithm is developed to compute the exact solution. To overcome some inherent computational deficiency in an exact computation, we develop an efficient randomized algorithm with an accuracy guarantee. We study the problem of quantile-•based KNN over multi-valued objects. Two different quantile distances are proposed. While the first distance can be computed in polynomial time, the second problem is NP-hard. A set of efficient, novel algorithms have been proposed to give an exact solution for the first problem and an approximate solution for the second problem with the approximation ratio 2. To overcome some deficiencies of existing uncertain index structures, we propose VI-tree which can efficiently support various queries including range queries, similarity joins and their size estimation as well as top-k range query, over multi-dimensional uncertain objects against continuous or discrete cases.

As demanded by applications such as GIS, CAD, ecology analysis, and space research, efficient spatial data access methods have attracted much research. Especially, moving object management and continuous spatial queries are becoming highlighted in the spatial database area. However, most of the existing spatial query processing approaches were designed for single-user environments, which may not ensure correctness and data consistency in multiple-user environments. This research focuses on designing efficient concurrent operations on spatial datasets. Current multidimensional data access methods can be categorized into two types: 1) pure multidimensional indexing structures such as the R-tree family and grid file; 2) linear spatial access methods, represented by the Space-Filling Curve (SFC) combined with B-trees. Concurrency control protocols have been designed for some pure multidimensional indexing structures, but none of them is suitable for variants of R-trees with object clipping, which are efficient in searching. On the other hand, there is no concurrency control protocol designed for linear spatial indexing structures, where the one-dimensional concurrency control protocols cannot be directly applied. Furthermore, the recently designed query processing approaches for moving objects have not been protected by any efficient concurrency control protocols. In this research, solutions for efficient concurrent access frameworks on both types of spatial indexing structures are provided, as well as for continuous query processing on moving objects, for multiple-user environments. These concurrent access frameworks can satisfy the concurrency control requirements, while providing outstanding performance for concurrent queries. Major contributions of this research include: (1) a new efficient spatial indexing approach with object clipping technique, ZR+-tree, that outperforms R-tree and R+-tree on searching; (2) a concurrency control protocol, GLIP, to provide high throughput and phantom update protection on spatial indexing with object clipping; (3) efficient concurrent operations for indices based on linear spatial access methods, which form up the CLAM protocol; (4) efficient concurrent continuous query processing on moving objects for both R-tree-based and linear spatial indexing frameworks; (5) a generic access framework, Disposable Index, for optimal location update and parallel search.

The main focus of my research is to design effective learning techniques for information retrieval and mining in high-dimensional databases. There are two main aspects in the retrieval and mining research: accuracy and efficiency. The accuracy problem is how to return results which can better match the ground truth, and the efficiency problem is how to evaluate users' requests and execute learning algorithms as fast as possible. However, these problems are non-trivial because of the complexity of the high-level semantic concepts, the heterogeneous natures of the feature space, the high dimensionality of data representations and the size of the databases. My dissertation is dedicated to addressing these issues. Specifically, my work has five main contributions as follows. The first contribution is a novel manifold learning algorithm, Local and Global Structures Preserving Projection (LGSPP), which defines salient low-dimensional representations for the high-dimensional data. A small number of projection directions are sought in order to properly preserve the local and global structures for the original data. Specifically, two groups of points are extracted for each individual point in the dataset: the first group contains the nearest neighbors of the point, and the other set are a few sampled points far away from the point. These two point sets respectively characterize the local and global structures with regard to the data point. The objective of the embedding is to minimize the distances of the points in each local neighborhood and also to disperse the points far away from their respective remote points in the original space. In this way, the relationships between the data in the original space are well preserved with little distortions. The second contribution is a new constrained clustering algorithm. Conventionally, clustering is an unsupervised learning problem, which systematically partitions a dataset into a small set of clusters such that data in each cluster appear similar to each other compared with those in other clusters. In the proposal, the partial human knowledge is exploited to find better clustering results. Two kinds of constraints are integrated into the clustering algorithm. One is the must-link constraint, indicating that the involved two points belong to the same cluster. On the other hand, the cannot-link constraint denotes that two points are not within the same cluster. Given the input constraints, data points are arranged into small groups and a graph is constructed to preserve the semantic relations between these groups. The assignment procedure makes a best effort to assign each group to a feasible cluster without violating the constraints. The theoretical analysis reveals that the probability of data points being assigned to the true clusters is much higher by the new proposal, compared to conventional methods. In general, the new scheme can produce clusters which can better match the ground truth and respect the semantic relations between points inferred from the constraints. The third contribution is a unified framework for partition-based dimension reduction techniques, which allows efficient similarity retrieval in the high-dimensional data space. Recent similarity search techniques, such as Piecewise Aggregate Approximation (PAA), Segmented Means (SMEAN) and Mean-Standard deviation (MS), prove to be very effective in reducing data dimensionality by partitioning dimensions into subsets and extracting aggregate values from each dimension subset. These partition-based techniques have many advantages including very efficient multi-phased pruning while being simple to implement. They, however, are not adaptive to different characteristics of data in diverse applications. In this study, a unified framework for these partition-based techniques is proposed and the issue of dimension partitions is examined in this framework. An investigation of the relationships of query selectivity and the dimension partition schemes discovers indicators which can predict the performance of a partitioning setting. Accordingly, a greedy algorithm is designed to effectively determine a good partitioning of data dimensions so that the performance of the reduction technique is robust with regard to different datasets. The fourth contribution is an effective similarity search technique in the database of point sets. In the conventional model, an object corresponds to a single vector. In the proposed study, an object is represented by a set of points. In general, this new representation can be used in many real-world applications and carries much more local information, but the retrieval and learning problems become very challenging. The Hausdorff distance is the common distance function to measure the similarity between two point sets, however, this metric is sensitive to outliers in the data. To address this issue, a novel similarity function is defined to better capture the proximity of two objects, in which a one-to-one mapping is established between vectors of the two objects. The optimal mapping minimizes the sum of distances between each paired points. The overall distance of the optimal matching is robust and has high retrieval accuracy. The computation of the new distance function is formulated into the classical assignment problem. The lower-bounding techniques and early-stop mechanism are also proposed to significantly accelerate the expensive similarity search process. The classification problem over the point-set data is called Multiple Instance Learning (MIL) in the machine learning community in which a vector is an instance and an object is a bag of instances. The fifth contribution is to convert the MIL problem into a standard supervised learning in the conventional vector space. Specially, feature vectors of bags are grouped into clusters. Each object is then denoted as a bag of cluster labels, and common patterns of each category are discovered, each of which is further reconstructed into a bag of features. Accordingly, a bag is effectively mapped into a feature space defined by the distances from this bag to all the derived patterns. The standard supervised learning algorithms can be applied to classify objects into pre-defined categories. The results demonstrate that the proposal has better classification accuracy compared to other state-of-the-art techniques. In the future, I will continue to explore my research in large-scale data analysis algorithms, applications and system developments. Especially, I am interested in applications to analyze the massive volume of online data.

The proliferation of massive data sets across many domains and the need to gain meaningful insights from these data sets highlight the need for advanced data retrieval techniques. Because I/O cost dominates the time required to answer a query, sequentially scanning the data and evaluating each data object against query criteria is not an effective option for large data sets. An effective solution should require reading as small a subset of the data as possible and should be able to address general query types. Access structures built over single attributes also may not be effective because 1) they may not yield performance that is comparable to that achievable by an access structure that prunes results over multiple attributes simultaneously and 2) they may not be appropriate for queries with results dependent on functions involving multiple attributes. Indexing a large number of dimensions is also not effective, because either too many subspaces must be explored or the index structure becomes too sparse at high dimensionalities. The key is to find solutions that allow for much of the search space to be pruned while avoiding this ‘curse of dimensionality’. This thesis pursues query performance enhancement using two primary means 1) processing the query effectively based on the characteristics of the query itself and 2) physically organizing access to data based on query patterns and data characteristics. Query performance enhancements are described in the context of several novel applications including 1) Optimization Queries, which presents an I/O-optimal technique to answer queries when the objective is to maximize or minimize some function over the data attributes, 2) High-Dimensional Index Selection, which offers a cost-based approach to recommend a set of low dimensional indexes to effectively address a set of queries, and 3) Multi-Attribute Bitmap Indexes, which describes extensions to a traditionally single-attribute query processing and access structure framework that enables improved query performance.

Data sensing and retrieval in WSNs have a great applicability in military, environmental, medical, home and commercial applications. In query-based WSNs, a user would issue a query with QoS requirements in terms of reliability and timeliness, and expect a correct response to be returned within the deadline. Satisfying these QoS requirements requires that fault tolerance mechanisms through redundancy be used, which may cause the energy of the system to deplete quickly. This dissertation presents the design and validation of adaptive fault tolerant QoS control algorithms with the objective to achieve the desired quality of service (QoS) requirements and maximize the system lifetime in query-based WSNs. We analyze the effect of redundancy on the mean time to failure (MTTF) of query-based cluster-structured WSNs and show that an optimal redundancy level exists such that the MTTF of the system is maximized. We develop a hop-by-hop data delivery (HHDD) mechanism and an Adaptive Fault Tolerant Quality of Service Control (AFTQC) algorithm in which we utilize "source" and "path" redundancy with the goal to satisfy application QoS requirements while maximizing the lifetime of WSNs. To deal with network dynamics, we investigate proactive and reactive methods to dynamically collect channel and delay conditions to determine the optimal redundancy level at runtime. AFTQC can adapt to network dynamics that cause changes to the node density, residual energy, sensor failure probability, and radio range due to energy consumption, node failures, and change of node connectivity. Further, AFTQC can deal with software faults, concurrent query processing with distinct QoS requirements, and data aggregation. We compare our design with a baseline design without redundancy based on acknowledgement for data transmission and geographical routing for relaying packets to demonstrate the feasibility. We validate analytical results with extensive simulation studies. When given QoS requirements of queries in terms of reliability and timeliness, our AFTQC design allows optimal "source" and "path" redundancies to be identified and applied dynamically in response to network dynamics such that not only query QoS requirements are satisfied, as long as adequate resources are available, but also the lifetime of the system is prolonged.

In this dissertation, we propose service-oriented sensor-actuator networks (SOSANETs) as a new paradigm for building the next generation of customizable, open, interoperable sensor-actuator networks. In SOSANETs, nodes expose their capabilities to applications in the form of service profiles. A node's service profile consists of a set of services (i.e., sensing and actuation capabilities) that it provides and the quality of service (QoS) parameters associated with those services (delay, accuracy, freshness, etc.). SOSANETs provide the benefits of both application-specific SANETs and generic SANETs. We first define a query model and an architecture for SOSANETs. The proposed query model offers a simple, uniform query interface whereby applications specify sensing and actuation queries independently from any specific deployment of the underlying SOSANET. We then present μRACER (Reliable Adaptive serviCe-driven Efficient Routing), a routing protocol suite for SOSANETs. μRACER consists of three routing protocols, namely, SARP (Service-Aware Routing Protocol), CARP (Context-Aware Routing Protocol), and TARP (Trust-Aware Routing Protocol). SARP uses an efficient service-aware routing approach that aggressively reduces downstream traffic by translating service profiles into efficient paths. CARP supports QoS by dynamically adapting each node's routing behavior and service profile according to the current context of that node, i.e. number of pending queries and number and type of messages to be routed. Finally, TARP achieves high end-to-end reliability through a scalable reputation-based approach in which each node is able to locally estimate the next hop of the most reliable path to the sink. We also propose query optimization techniques that contribute to the efficient execution of queries in SOSANETs. To evaluate the proposed service-oriented architecture, we implemented TinySOA, a prototype SOSANET built on top of TinyOS with uRACER as its routing mechansim. TinySOA is designed as a set of layers with a loose interaction model that enables several cross-layer optimization options. We conducted an evaluation of TinySOA that included a comparison with TinyDB. The obtained empirical results show that TinySOA achieves significant improvements on many aspects including energy consumption, scalability, reliability and response time.

Recent advances in MEMS (micro-electro-mechanical systems) and radio technology has enabled development of low-cost wireless sensor networks (WSNs). Due to their ease of deployment and ad hoc connectivity, WSNs are emerging as a promising tool for a wide range of applications. Each sensor node is equipped with programmable computing, multiple-parameter sensing and wireless communication capability. Sensor nodes are however, constrained in terms of available resources such as energy, storage and computation. Such limitations make it really challenging to realize a reliable WSN infrastructure that can efficiently process different types of user queries. The objective of this dissertation is to develop energy-efficient mechanisms for enabling query processing in WSNs, despite unreliable nature of the wireless medium. The first part of this dissertation focuses on designing energy-efficient architectures for processing different kinds of user queries. Queries in WSNs can be broadly classified as location-based queries and attribute-based queries. To enable processing of long-running location-based queries, the recent trend is to evaluate queries within the WSN, so as to reduce the overall communication and energy consumption of the WSN. The in-network query processing architecture proposed in this dissertation determines optimal placement of query operators within a WSN in a decentralized manner and also adapts to continual changes in network and data properties. On the other hand, the recent trend in processing attribute-based queries is employing data-centric storage schemes that eliminate the need for flooding the WSN. In this dissertation, a novel data-centric storage scheme has been developed to determine rendezvous points for storing individual attributes depending on their correlation with other attributes. Both analytical and simulation studies have been performed to identify the conditions under which the proposed architecture is useful. The second part of this dissertation focuses on designing mechanisms for ensuring reliable and timely delivery of the sensed data. WSNs are generally deployed in inhospitable terrains and consist of a dense deployment of sensor nodes. Furthermore, wireless communication is inherently unpredictable and error-prone. Hence, it is imperative to design an efficient medium access control (MAC) protocol that facilitates guaranteed delivery of data over unreliable wireless links. In this dissertation, such an on-demand reliable MAC protocol has been proposed and its superior performance in terms of reliability, latency and scalability has been demonstrated. Furthermore, we have also proposed another MAC protocol that is both energy-efficient and reliable. The energy-efficiency of the proposed MAC protocol has been achieved by switching the sensor nodes to sleep mode when they are not involved in data communication. However in doing so, measures have been taken to avoid problems like overemitting, excessive latency and frequent changes of the radio state. Thus, our proposed MAC protocol reliably delivers sensed data with minimum power consumption, thereby attempting to reach the desirable objectives of WSNs.

Efficient query processing is an important technique which makes the database technology practical. Databases usually have sets of semantic integrity constraints to regulate their consistent and nonredundant status. These constraints can also be utilized in processing queries. We consider two types of commonly used semantic constraints – implication constraints and referential constraints, for the purpose of such semantic query processing. The main issues of semantic query processing considered in this work include detecting inconsistent queries, deciding the containment relationship between queries (with respect to a set of semantic integrity constraints), detecting redundant selection-conditions and redundant joins in queries, and providing intelligent answers to recursive queries. We also consider two important related problems: minimizing conjunctive queries and deciding redundant implication constraints. Different from other existing works on semantic query optimization (SQO), we study the issues based on a new general treatment of implication and referential constraints. First of all, one central problem in this respect is identified, and we call it the IRC-refuting problem, which is to decide whether a conjunctive query always produ ces an empty relation on database instances satisfying a given set of implication and referential constraints. A necessary and sufficient condition is given to the IRC-refuting problem. (For the decidability of the problem, we assume that the referential constraints are acyclic. Based on this result, the semantics-based containment problem and the redundant implication constraint problem are shown to be polynomially equivalent to the IRC-refuting problem (under the acyclic assumption); and the redundant selection-condition and redundant join problems are shown to be polynomially reducible to the IRC-refuting problem. We also study the issue of efficiency within this approach, and give sufficient conditions for reducing the complexity in some special cases. Moreover we show how to use the results on the (semantics-based) containment problem in constructing intelligent answers to a class of recursive queries in deductive databases.