Unlike traditional computing platforms (such as desktops and servers), mobile platforms provide a volatile running environment for apps where the state of an app may get destroyed and recreated frequently, either by runtime configuration changes (e.g., changing the phone orientation) or by limited resources available on the device (e.g., low memory). When the app state is not saved and restored appropriately, the app restarts may cause a wide range of runtime issues, ranging from loss of user progress and poor responsiveness to malfunctioned UI and app crashes. The goal of this thesis is to address the fundamental issue of state management for mobile apps. To achieve the above goal, this thesis proposes a runtime system and a novel static analysis.

First, it studies a large number of real-world mobile apps, a high percentage of them fail to handle restarts appropriately, posing a great challenge to mobile computing. To address the state issues caused by app restarts, this thesis explores two orthogonal directions: (i) a system-oriented solution and (ii) an application-oriented solution.

In the first direction, it aims to prevent apps from restarting by developing a restart-free runtime system, called RuntimeDroid, which completely avoids the needs of configuration-related app restarts. The purpose of restarts in the existing runtime system is to load resources for the new configuration (e.g., a layout for the portrait mode). RuntimeDroid achieves this by automatically identifying and "hot"-loading the resources while the app is running.

In the other direction, this thesis approaches the state issues with a more direct solution -- first, identify the necessary app state, then automatically preserve it at runtime. More specifically, it first uses static analysis to systematically reason about the app source code and the associated resource files to find the critical program variables and properties of GUI elements that are necessary to be preserved. Then, it leverages automatic code generation techniques to insert the state saving and restoring routines to the app code. As a result, a tool (named LiveDroid) can precisely identify and preserve the app state in real-world Android apps, which not only ensures the state correctness during app restarts but also makes the app restarts more responsive.

Besides the above, this thesis also proposes the static user transaction graph (SUTG), which leverages static analysis to encode operations of interests in the form of a graph. SUTG can serve as the basis for a variety of mobile app testing tools, such as latency profiling and state testing in the presence of asynchronous threads. As a result, the automated tools help developers to identify performance bottlenecks and incorrect state handling in their apps.

Semi-structured data, like JSON, XML, and their derivatives, are essential in modern computing infrastructures, from cloud computing and microservice to NoSQL data stores and Internet of Things (IoT). However, existing software often fails to process such types of data in a scalable way due to their nested structures and the lack of effective data-level parallelism. The goal of this thesis is mainly to address two fundamental scalability issues in semi-structured data processing. First, how can semi-structured data analytics effectively leverage the abundant hardware parallelism that are offered by modern computer architectures (e.g., multi-cores and SIMD operations)? Second, how can semi-structured data analytics improve the data access efficiency (i.e., locality) and reduce the memory consumption when handling large semi-structured datasets? To answer these questions, this thesis proposes a series of parallelization techniques and streaming computation models dedicated to semi-structured data.

More specifically, this thesis first proposes a grammar-aware parallelization (GAP) scheme for XPath query evaluation, which leverages the data grammar (e.g., DTD file for XML) to prune unnecessary paths during the enumerative execution. Then, it designs a streaming model for querying JSON data, which jointly compiles JSON grammar and JSONPath queries into a dual-stack pushdown automaton, and adopts a customized GAP scheme for its parallelization. Next, to effectively utilize both fine-grained (bitwise and SIMD) parallelism and coarse-grained (multi-core) parallelism, this thesis proposes a new design of bitwise structural index construction that is able to build leveled bitmaps for a single large JSON record in parallel, thanks to a set of parallelization techniques specialized to JSON structures. Finally, this thesis combines the ideas of bitwise index construction and the stream processing model, which brings in a novel on-demand parsing technique that can intelligently skip parsing irrelevant substructures of a JSON record based on the given JSON queries. All the above techniques have been systematically evaluated with real-world datasets and standard JSON/XML queries, and have demonstrated significant performance benefits over the existing solutions, in terms of both query evaluation time and memory consumption.

Parallelism is key for designing and implementing high-performance data analytics on modern processors. However, many data processing routines cannot be executed in parallel, due to the sequential nature of their underlying computation models. This dissertation focuses on an important class of sequential data processing routines that are driven by or can be modeled as finite-state machines (FSMs). It proposes a series of speculation-based parallelization and modeling techniques to improve the parallelism and scalability of FSM-based computations. Moreover, it successfully applies the FSM-based speculative parallelization to non-FSM computations, significantly expanding the applicability of the proposed techniques.

More specifically, we first introduce multi-level speculation by integrating the instruction-level and SIMD-level parallelism into the existing multicore-level speculative parallelization. We then systematically model the scalability of speculative FSM parallelization and point out its limitations. To address them, we design two novel optimizations: path fusion and higher-order speculation, which together bring the scalability to another level for FSMs that are conventionally hard to parallelize effectively. Finally, we demonstrate that, with rigorous static analysis, we can precisely model bitstream computations with FSMs, hence solve their parallelization with existing FSM parallelization techniques.

Graph analytics is fundamental in unlocking key insights by mining large volumes of highly connected data. However, comparing to many other data analytics, it is difficult to perform graph analytics efficiently on modern computers due to three reasons. First, the structures of graphs are often highly irregular. For example, a small portion of vertices may own a large number of neighbors while most vertices have very few neighbors. The structure irregularity leads to computation irregularity, resulting in workload imbalance among worker threads. Second, real-world graphs tend to be large. It is oftentimes impractical to find individual machines with memory capacity that can accommodate such large graphs entirely, not to mention accelerators (like GPUs) which have more limited memory capacity. Third, it remains open questions how graph processing systems should be designed for emerging graph analytics, which often involves the tradeoff among multiple key factors, such as data locality, amount of parallelism, and computation redundancy.

This thesis aims to address the above three challenges of graph processing under some specific contexts. First, it focuses on improving the performance of graph analytics on modern highly-parallel processors -- GPUs. Note that GPUs are conventionally designed for regular computations. To address the irregularity of graph computations, this thesis proposes a graph transformation technique that can convert irregular graphs into regular ones while preserving the correctness of the graph analytics. Second, this thesis further examines the performance bottleneck in processing oversized graphs that cannot fit into the memory of GPUs. It finds that the data movement between CPU and GPU is very costly. To address the issue, this thesis proposes a subgraph extraction technique which can dynamically extract the active parts of the graph in each processing iteration -- they are usually small enough to fit into the GPU memory. Finally, this thesis looks into an underexplored yet important graph application -- large-scale program analysis, and proposes to systematically exploit the design space of a graph system for this new application in order to realize its full potential.

Developing scalable and efficient graph systems to support low-latency streaming analysis and high-throughput concurrent query evaluation poses significant challenges. This thesis proposes solutions to address these challenges.

Existing streaming graph systems require prior knowledge of queries; otherwise, they fall back to expensive full query evaluations. The proposed Tripoline system overcomes this by applying principles similar to triangle inequalities in Euclidean geometry, generalizing them for various vertex-specific graph problems. This allows the reuse of existing query results to accelerate new queries. Tripoline achieves a speedup of up to $41.5\times$ compared to traditional streaming graph engines.

Another limitation of streaming graph analysis is that when changes to the graphs become large, the incremental graph computation starts running slower than the full query evaluation. Moreover, present incremental graph algorithms cannot handle edge weight updates elegantly, resorting to a sub-optimal two-phase process. The proposed IncBoost addresses these scalability issues with algorithmic enhancements and system-level optimizations. It employs a novel bottom-up dependency tracing technique to identify vertices affected by edge updates without accessing the graph data. It introduces a direct method for handling edge weight updates. IncBoost scales to handle large update batches with sizes of 30\% to 50\% of the graph and achieves up to a $4.9\times$ speedup over RisGraph.

To enhance the efficiency of a query processing system, concurrent query processing is used for higher throughput. However, efficiency is often hampered by misaligned graph traversals, causing unfavorable last-level cache misses. A runtime system called Glign is developed to address this issue by automatically aligning graph traversals for concurrent queries. Glign features novel optimizations at three levels: (1) the intra-iteration alignment effectively reduces memory footprint for graph traversals; (2) the inter-iteration alignment enlarges the overlapping of vertices for better-shared graph access; (3) a query batch formation strategy predicts query subsets with better affinity for batching. Glign outperforms the state-of-the-art concurrent graph processing systems, achieving speedups of up to $4.7\times$.

To improve the system throughput of graph-based approximate nearest neighbor search (ANNS), this dissertation explores the design of graph construction and search phases, particularly with temporal information. The proposed graph construction algorithm considers the correlation between input queries and the final answers in the time dimension. A fully parameterized best-first search algorithm is also designed for flexible performance tuning. These techniques improve query throughput by up to $1.9\times$ compared to the state-of-the-art {DiskANN} while maintaining recall. Additionally, the constructed graph size can be reduced by up to 30\% without compromising query quality.