The continuous growth of the internet and the popularity of social networks have created a huge amount of social media data. This includes social networks like users' friendships, as well as users' contributed content such as tags, blogs, posts, tweets, and etc. In addition, other collaborating applications also generate large data, such as the versioned textual documents created in a collaborative authoring environment like Wikipedia. In a dynamic world, the social media data is continuously evolving with time. In December 2004, Facebook had about 1 million users; but by October 2012, Facebook has over 1 billion active users. The dynamically changing and rapidly growing data bring us critical challenges: how to store, how to query, and how to use it in different application domains. This dissertation examines four related problems. First, we consider the large historical evolving graphs created from a social network, and examined various temporal shortest-path queries (e.g., find the shortest-path between two nodes as of certain time in the past). For this environment we proposed an efficient storage model, and fast query processing algorithms that take advantage of appropriate speed-up indexing techniques. For second problem examined, deals with social tagging websites, where users post and share items like bookmarks, videos, photos etc., along with comments and tags. Within this environment, we presented a study of top-k search that utilizes the temporal information as well as a user's participation in multiple social networks; our results show an improved search performance. Third, we examined the problem of temporal top-k keyword search in versioned textual collections; we compared different approaches and proposed novel methods that utilize multi-version access methods to improve the search. Finally, we considered applications that support multi-version schema evolutions; we explored scenarios for branching and merging, and proposed efficient indexing structures along with query processing optimizations.

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 requires

specialized 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.

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.

Aggregation has been an important operation since the early days of relational databases. Today's Big Data applications bring further challenges when processing aggregation queries, demanding robust aggregation algorithms that can process large volumes of data efficiently in a distributed, share-nothing architecture. Moreover, aggregation on each node runs under a potentially limited memory budget (especially in multiuser settings). Despite its importance, the design and evaluation of aggregation algorithms has not received the same attention that other basic operators, such as joins, have received in the literature.

This dissertation revisits the engineering of efficient aggregation algorithms for use in Big Data platforms, considering both local and global aggregations. We firstly discuss the salient implementation details and precise cost models of several candidate local aggregation algorithms and present an in-depth experimental performance study to guide future Big Data engine developers. We show that the efficient implementation of the local aggregation operator for a Big Data platform is non-trivial and that many factors, including memory usage, spilling strategy, and I/O and CPU cost, should be considered. Then we show extended cost models that can precisely depict the cost of global aggregation plans, considering not only the local cost factors but also the network cost. We discuss a generic framework to describe a tree-structured global aggregation plan, and propose a cost-model based algorithm for efficiently finding the non-dominated global aggregation plans for different output properties, given the input data statistics and the global computation resources.

Furthermore, spatial and temporal information introduces more semantics to traditional aggregations, requiring specific efficient algorithms that could utilize the additional spatial and temporal information during the query processing. In the last part of the thesis we show a novel aggregation application for monitoring the top-k unsafe moving objects in a continuous data stream where the spatial and temporal information change. We show that such a query can be generalized as an extended aggregation operation where the grouping condition is unknown without looking at all valid data in the given query time window. We then propose I/O-efficient algorithms to answer such queries utilizing spatial and temporal index structures.

Identifying interesting objects from a large data collection is a fundamental problem for multi-criteria decision making applications.

In Relational Database Management Systems (RDBMS), the most popular complex query operators used to solve this type of problem are the Top-K selection operator and the Skyline operator.

Top-K selection is tasked with retrieving the k-highest ranking tuples from a given relation, as determined by a user-defined aggregation function.

Skyline selection retrieves those tuples with attributes offering (pareto) optimal trade-offs in a given relation.

Efficient Top-K query processing entails minimizing tuple evaluations by utilizing elaborate processing schemes combined with sophisticated data structures that enable early termination.

Skyline query evaluation involves supporting processing strategies which are geared towards early termination and incomparable tuple pruning.

The rapid increase in memory capacity and decreasing costs have been the main drivers behind the development of main-memory database systems.

Although the act of migrating query processing in-memory has created many opportunities to improve the associated query latency, attaining such improvements has been very challenging due to the growing gap between processor and main memory speeds.

Addressing this limitation has been made easier by the rapid proliferation of multi-core and many-core architectures.

However, their utilization in real systems has been hindered by the lack of suitable parallel algorithms that focus on algorithmic efficiency.

In this thesis, we study in depth the Top-K and Skyline selection operators, in the context of emerging parallel architectures.

Our ultimate goal is to provide practical guidelines for developing work-efficient algorithms suitable for parallel main memory processing.

We concentrate on multi-core (CPU), many-core (GPU), and processing-in-memory architectures (PIM), developing solutions optimized for high throughout and low latency.

The first part of this thesis focuses on Top-K selection, presenting the specific details of early termination algorithms that we developed specifically for parallel architectures and various types of accelerators (i.e. GPU, PIM).

The second part of this thesis, concentrates on Skyline selection and the development of a massively parallel load balanced algorithm for PIM architectures.

Our work consolidates performance results across different parallel architectures using synthetic and real data on variable query parameters and distributions for both of the aforementioned problems.

The experimental results demonstrate several orders of magnitude better throughput and query latency, thus validating the effectiveness of our proposed solutions for the Top-K and Skyline selection operators.

The main part of this dissertation considers how to scale interval join queries. To provide scalable query processing for such joins, we adapted five recently published overlapping interval join algorithms and modified them to work in a shared-nothing big data management system (AsterixDB) under a memory budget. We developed a cost model for each algorithm to predict when an algorithm will spill to disk (run out of memory). Our experimental evaluation shows that the cost models are accurate and can be used to pick the most efficient algorithm for the given input data. The adapted interval join algorithms are shown to scale for large datasets using both synthetic and real datasets. Finally, we further adapt these algorithms to support several new types of interval joins, specifically overlap and contains, as defined by Allen's interval algebra. We detail how to abstract the memory management from these algorithms.

As a by-product we also implemented a scalable parallel processor, namely Apache VXQuery, that extends a stack consisting of Hyracks, a parallel execution engine, and Algebricks, a language-agnostic compiler toolbox. VXQuery provides an implementation of the XQuery specifics (data model, data-model dependent functions and optimizations, and a parser). We describe the architecture of Apache VXQuery, its integration with Hyracks and Algebricks, and the XQuery optimization rules applied to the query plan to improve path expression efficiency and to enable query parallelism. An experimental evaluation using a real 500GB dataset with various XML selection, aggregation, and join queries shows that Apache VXQuery performs well both in terms of scale-up and speed-up.

This dissertation examines advanced pre-processing techniques and query algorithms for efficiently solving several practical, real-world route planning problems for personalized navigation in road networks. Unlike most prior research in this domain, where shortest paths are assumed to be static, this research supports dynamically-constrained shortest path queries in which the resulting solution paths can vary depending on each traveler's unique requirements. Specifically, this research is comprised of two parts, each focusing on a high-level class of constrained route planning problems in road networks. In the first part, we consider route planning problems with avoidance constraints, in which the route is required to avoid certain types of roads (e.g., toll roads, unpaved roads, etc.). In the second part, we consider route planning problems with detour constraints, in which the route is required to visit one or more categorical points of interest along the way (e.g., gas stations, coffee shops, etc.). We consider several specific sub-problems for each of these high-level problems and present extensive experimental results of our proposed algorithms on the continental road networks of North America and Europe (with over 50 million edges and 90 million edges, respectively).

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.

This thesis presents several new query processing techniques, called complex motion pattern queries, specifically designed for trajectories. First, it begins with the definition of flexible pattern query, a very powerful, yet easy to use motion pattern query which allows users to select trajectories based on specific events of interest. Flexible pattern query is described as regular expressions over a spatial alphabet that can be implicitly/explicitly "anchored" to the time domain. Moreover, it allows users to include variables in the pattern query, and thus greatly increase its expressive power. Second, the Spatio-Temporal Pattern System (STPS) is presented, which is an adaptation of flexible pattern query for mobile phone-call databases. These databases contain many millions of records with information about mobile phone calls, including the user's location, when the call was made/received, and duration of the call, among other information. The design of STPS takes into consideration the layout of the areas being covered by the cellular towers, as well as areas that label places of interest (e.g. neighborhoods, parks). Third, density-based pattern query is described for discovering trajectories that follow a pattern that captures the aggregate behavior of trajectories as groups. Several evaluation algorithms are presented for finding groups of trajectories that move together, i.e. within a predefined distance to each other for a continuous period of time. The last complex motion pattern query proposed in this thesis is for diversifying query results. The goal of this query is to build a result that contains relevant elements to the user's query and diverse elements to other elements in the result. This pattern query is useful when, for example, an exploratory query to a very large database leads to a vast number of answers in the result. Navigating through such a large result requires huge effort and users give up after perusing through the first few results, thus some interesting results hidden further down the result set can easily be missed. To overcome this problem, a generic framework for diversifying query results is presented. Two new evaluation methods, as well as several existing ones, are described and tested in the proposed framework. The efficiency and effectiveness of the proposed complex motion pattern queries are demonstrated through an extensive experimental evaluation.

Understanding moving object behaviors, also known as trajectory semantics, is an important problem that affects many decision making applications. Previous works typically identify such behaviors by using known landmarks, also termed as Regions of Interest (ROIs) (parks, museums, malls, etc.) that are geographically collocated with the trajectory. The main objective of this thesis is to identify trajectory semantics, by looking only at the trajectory data, i.e., without assuming pre-knowledge of ROIs.

We first present a new trajectory behavior, by defining the notion of dwell regions. A region R is a dwell region for a moving object O if, given a threshold distance d and duration t, every point of R remains within distance d of O for at least time t. Clearly, points within R are likely to be of interest to O. We present methods for determining dwell regions for both streaming and archived data. Next, we introduce a novel query that can be used to track conclaves (i.e., secret meetings) of a group of moving object. In this environment we assume only partial observations of the individual object movements, within the context of a local transportation network. This is a realistic assumption due to sparsely-distributed surveillance cameras or lack of observations in general. Given such limited observations we seek to infer the set of all possible conclaves. The third chapter of the thesis addresses ROI identification. An ROI is typically defined as a region where a large number of moving objects remain for at least a given time interval. Previous methods require sequential scanning of the entire dataset to find ROIs when the semantics (number of objects, time duration) change. Here, we propose a novel method based on object density, to efficiently identify ROIs with arbitrary semantics; this method scans the dataset only once.

We also revisit indexing of trajectories using Hilbert curves. Instead of using minimum bounding rectangles we present methods to use Hilbert curves to index trajectory polylines. Our method outperforms the state of the art methods for spatial range queries by two to fifteen times. Even though such transformation does not preserve the Euclidean distance, we show, that our approach can also be used to efficiently answer kNN queries.