LSM-tree based key-value stores are widely adopted as the data storage backend in modern big data applications. The LSM-tree grows with data ingestion, by either adding levels with fixed level capacities (dubbed as vertical scheme) or increasing level capacities with fixed number of levels (dubbed as horizontal scheme). The vertical scheme leads the trend in recent system designs in RocksDB, LevelDB, and WiredTiger, whereas the horizontal scheme shows a decline in being adopted in the industry. The growth scheme profoundly impacts the LSM system performance in various aspects such as read, write and space costs. This paper attempts to give a new insight into a fundamental design question -- how to grow an LSM-tree to attain more desirable performance? Our analysis highlights the limitations of the vertical scheme in achieving an optimal read-write trade-off and the horizontal scheme in managing space cost effectively. Building on the analysis, we present a novel approach, Vertiorizon, which combines the strengths of both the vertical and horizontal schemes to achieve a superior balance between lookup, update, and space costs. Its adaptive design makes it highly compatible with a wide spectrum of workloads. Compared to the vertical scheme, Vertiorizon significantly improves the read-write performance trade-off. In contrast to the horizontal scheme, Vertiorizon greatly extends the trade-off range by a non-trivial generalization of Bentley and Saxe's theory, while substantially reducing space costs. When integrated with RocksDB, Vertiorizon demonstrates better write performance than the vertical scheme, while incurring about six times less additional space cost compared to the horizontal scheme.

There is a proliferation of applications requiring the management of large-scale, evolving graphs under workloads with intensive graph updates and lookups. Driven by this challenge, we introduce Poly-LSM , a high-performance key-value storage engine for graphs with the following novel techniques: (1) Poly-LSM is embedded with a new design of graph-oriented LSM-tree structure that features a hybrid storage model for concisely and effectively storing graph data. (2) Poly-LSM utilizes an adaptive mechanism to handle edge insertions and deletions on graphs with optimized I/O efficiency. (3) Poly-LSM exploits the skewness of graph data to encode the key-value entries. Building upon this foundation, we further implement Aster , a robust and versatile graph database that supports Gremlin query language facilitating various graph applications. In our experiments, we compared Aster against several mainstream real-world graph databases. The results demonstrate that Aster outperforms all baseline graph databases, especially on large-scale graphs. Notably, on the billion-scale Twitter graph dataset, Aster achieves up to 17x throughput improvement compared to the best-performing baseline graph system.

We study the problem of Quality-of-Service (QoS)-Aware Personalized PageRank (PPR) computation. Existing studies mostly focus on improving the PPR query processing time. However, the query processing time alone may not reflect the service quality in real-world PPR-based systems. The query response time can be a more service-relevant measure in many applications such as the online game service of Tencent and the related-pin recommendation module of Pinterest. We make the first attempt at studying QoS-Aware PPR computation and present Quota, a system that adapts the state-of-the-art PPR algorithms to a given environment for minimizing query response time. Equipped with mathematical tools including queuing theory, algorithmic complexity analysis, and constrained optimization, Quota is designed to adapt itself to a wide spectrum of workloads. We conduct extensive experiments on real datasets and show that Quota can reduce the query response time compared with state-of-the-art PPR algorithms, often by a significant margin.

Mainstream LSM-tree-based key-value stores face challenges in optimizing performance for point lookup, range lookup, and update operations concurrently due to their constrained configurations. They typically follow fixed patterns to specify the level capacity and the number of sorted runs per-level. This confines their designs to a restricted space, limiting opportunities for broader optimizations. To address this challenge, we consider a more flexible configuration that enables independent adjustments of the number of runs per-level, size ratio, and Bloom filter settings at each LSM-tree level. By carefully analyzing the cost of each operation based on the new design space, we unveil two critical insights for optimizing the tradeoff among the three operations. Firstly, achieving efficient point lookup requires a large last level. Secondly, there is a specific correlation between the number of runs per level and size ratio that is advantageous for overall update and range lookup performance. Based on these insights, we introduce Moose, a structure delivering an impressive overall performance for point lookup, range lookup, and update concurrently. Furthermore, we also introduce a new framework, Smoose, to navigate the design space for adapting specific workloads. We implemented Moose and Smoose on top of RocksDB and experimental results demonstrate that our proposed approach outperforms state-of-the-art LSM-tree structures across diverse workloads.

Location search in spatial services such as online maps nowadays is usually based on criteria filtering methods. Due to its algorithmic design, the traditional method only searches for one target location per query, ignoring the relation among multiple objects. In large-scale tasks of finding a number of targets, it is particularly inconvenient as users are required to specify each criterion. To address this issue, we present Example Searcher, a system that allows users to search more efficiently in such tasks. Example Searcher adopts a novel way of location search that allows rich and interactive user inputs and searches for multiple target locations simultaneously. The system is powered by the state-of-the-art spatial search algorithm LORA, which efficiently performs spatial queries and searches for a set of locations that are similar to the given input examples as a whole. An introduction video of Example Searcher is available at: https://sites.google.com/view/examplesearcher.

LSM-trees are widely adopted as the storage backend of key-value stores. However, optimizing the system performance under dynamic workloads has not been sufficiently studied or evaluated in previous work. To fill the gap, we present RusKey, a key-value store with the following new features: (1) RusKey is a first attempt to orchestrate LSM-tree structures online to enable robust performance under the context of dynamic workloads; (2) RusKey is the first study to use Reinforcement Learning (RL) to guide LSM-tree transformations; (3) RusKey includes a new LSM-tree design, named FLSM-tree, for an efficient transition between different compaction policies -- the bottleneck of dynamic key-value stores. We justify the superiority of the new design with theoretical analysis; (4) RusKey requires no prior workload knowledge for system adjustment, in contrast to state-of-the-art techniques. Experiments show that RusKey exhibits strong performance robustness in diverse workloads, achieving up to 4x better end-to-end performance than the RocksDB system under various settings.

Given a source node s and a target node t in a graph G, the Personalized PageRank (PPR) from s to t is the probability of a random walk starting from s terminates at t. PPR is a classic measure of the relevance among different nodes in a graph, and has been applied in numerous real-world systems. However, existing techniques for PPR queries are not robust to dynamic real-world graphs, which typically have different evolving speeds. Their performance is significantly degraded either at a lower graph evolving rate (e.g., much more queries than updates) or a higher rate. To address the above deficiencies, we propose Agenda to efficiently process, with strong approximation guarantees, the single-source PPR (SSPPR) queries on dynamically evolving graphs with various evolving speeds. Compared with previous methods, Agenda has significantly better workload robustness, while ensuring the same result accuracy. Agenda also has theoretically-guaranteed small query and update costs. Experiments on up to billion-edge scale graphs show that Agenda significantly outperforms state-of-the-art methods for various query/update workloads, while maintaining better or comparable approximation accuracies.

Distributed vertex-centric graph systems, or VC-systems, have achieved tremendous success in the industry. A common usage pattern of VC-systems is multi-processing, or the concurrent processing of multiple unit tasks. Example multi-processing includes answering multiple single-source shortest path queries on a graph. However, concurrent processing of all the unit tasks may overload the system with excessive memory usage, leading to intolerable system delays. To ad-dress the important challenge, we present V C- Tune, a system with a convenient interface to help practitioners orchestrate the unit tasks for improving the overall performance within the system limit. This demonstration allows the audience to interact with our system to explore the configuration space of multi-processing in VC-systems and compare different sys-tem configurations. In addition, we embed into the system an automatic configuration search algorithm, which can directly recommend to the practitioners a suitable configuration that gives a satisfactory system performance. An introduction video is at (https://sites.google.com/view/vc-tune-video).

Recent advances in data processing have stimulated the demand for learning graphs of very large scales. Graph Neural Networks (GNNs), being an emerging and powerful approach in solving graph learning tasks, are known to be difficult to scale up. Most scalable models apply node-based techniques in simplifying the expensive graph message-passing propagation procedure of GNN. However, we find such acceleration insufficient when applied to million- or even billion-scale graphs. In this work, we propose SCARA, a scalable GNN with feature-oriented optimization for graph computation. SCARA efficiently computes graph embedding from node features, and further selects and reuses feature computation results to reduce overhead. Theoretical analysis indicates that our model achieves sub-linear time complexity with a guaranteed precision in propagation process as well as GNN training and inference. We conduct extensive experiments on various datasets to evaluate the efficacy and efficiency of SCARA. Performance comparison with baselines shows that SCARA can reach up to 100x graph propagation acceleration than current state-of-the-art methods with fast convergence and comparable accuracy. Most notably, it is efficient to process precomputation on the largest available billion-scale GNN dataset Papers100M (111M nodes, 1.6B edges) in 100 seconds.

Given a source node s and a target node t in a graph G, the Personalized PageRank (PPR) from s to t is the probability of a random walk starting from s terminates at t. PPR is a classic measure of the relevance among different nodes in a graph, and has been applied in numerous real-world systems. However, existing techniques for PPR queries are not robust to dynamic real-world graphs, which typically have different evolving speeds. Their performance is significantly degraded either at a lower graph evolving rate (e.g., much more queries than updates) or a higher rate.