Large language model (LLM) training is prone to anomalies due to its long duration and large scale, which can lead to significant performance degradation or even training crashes. Due to the synchronization nature of LLM training, anomalies exhibit the cascading effect, making their diagnosis challenging. Existing approaches rely on collecting communication operator information via code instrumentation, which yields only coarse-grained monitoring data and requires modifications to training code or communication libraries. We propose Pulse, a fine-grained, non-intrusive, and easy-to-deploy monitoring system. Our key idea is to enable fine-grained monitoring via traffic measurement. Pulse conducts microsecond-level RDMA traffic measurement on NICs, and transforms flow-level measurements into communication operator measurements, thereby enabling fine-grained and non-intrusive monitoring. We deploy Pulse on a testbed with 64 H200 GPUs and evaluate its anomaly localization capability under common failure scenarios. Pulse achieves machine-level localization in 10 out of 12 scenarios, while existing methods succeed in only 4 and even misdiagnose 2 of the remaining scenarios. Additionally, Pulse achieves over 90% precision and 100% recall, supports up to 2000 concurrent RDMA flow measurements per NIC, and imposes negligible overhead on training performance, making it a practical solution for real-world LLM training environments.

Blazing fast RDMA technology revolutionizes modern distributed systems and propels them to offload performance-critical data paths onto this network fabric. Designing an RDMA-optimized data path needs to clear a main hurdle—non-scalable distributed locks. Through a performance dissection of existing lock schemes, we find that software-based lock request ordering and polling-based lock ownership transfer scale poorly, leading to high NIC contention and heavy network congestion. To resolve these bottlenecks, this paper proposes StreamLock, a scalable lock primitive that co-designs the distributed lock protocol with fast RDMA networks. The core of StreamLock is a novel shared stream abstraction with two mechanisms: (i) scalable request ordering by repurposing the line-speed packet receiving provided by modern NICs; (ii) peer-to-peer notification to achieve one-round-trip-time lock ownership transfer. We implement StreamLock with off-the-shelf RDMA NICs and compare it with state-of-the-art distributed locks. Comprehensive experimental results showcase that StreamLock outperforms them significantly.

Range-top-k queries retrieve the top-k elements within an arbitrary subrange of a large array and are a key primitive in real-time analytics. Unlike one-shot top-k selection, practical deployments issue large volumes of queries over varying and often overlapping ranges, frequently interleaved with streaming updates. In this setting, applying conventional GPU top-k kernels per query is inefficient: each query triggers range rescans or O(n)-scale passes that overwhelm HBM bandwidth, thrash on-chip caches, and provide little reuse across overlapping windows.

Large Language Model (LLM) inference has emerged as a fundamental paradigm, however, variations in output length cause severe workload imbalance in the decode phase, particularly for long-output reasoning tasks. Existing systems, such as PD disaggregation architectures, rely on static prefill-to-decode scheduling, which often results in SLO violations and OOM failures under evolving decode workloads. In this paper, we propose STAR, a decode rescheduling system powered by length prediction to anticipate future workloads. Our core contributions include: (1) A lightweight and continuous LLM-native prediction method that leverages LLM hidden state to model remaining generation length with high precision (reducing MAE by 49.42%) and low overhead (cutting predictor parameters by 93.28%); (2) A rescheduling solution in decode phase with a dynamic balancing mechanism that integrates current and predicted workloads, reducing P99 TPOT by 75.1% and achieving 2.63 × higher goodput.

Training large language models faces frequent interruptions due to various faults, demanding robust fault-tolerance. Existing backup-free methods, such as redundant computation, dynamic parallelism, and data rerouting, each incur performance penalties, whether from ongoing overhead, lengthy reconfigurations, or post-recovery inefficiencies. We propose Chameleon, an adaptive fault-tolerant system that intelligently selects optimal recovery strategies when a failure occurs. Chameleon achieves this through a unified performance model, expedient execution plan search, accurate performance estimation, and efficient communication optimizations. Experiments on a 32-card cluster show that Chameleon maintains a performance gap of within 11.00% between post-recovery and failure-free training, while preserving model convergence and efficient memory usage. Compared to state-of-the-art methods, Chameleon achieves up to 1.229x and 1.355x higher average throughput than Oobleck and Recycle, respectively.

Complex event recognition (CER) refers to identify-ing specific patterns composed of several primitive events in event stores. Since full-scanning event stores to identify primitive events that hold query constraint conditions incurs costly I/O overhead, a mainstream and practical approach is to use index techniques to obtain these events. However, prior index-based approaches suffer from significant I/O and sorting overhead when processing the query with high predicate selectivity or long query window, which leads to high query latency. To address this issue, we propose ACER, a Range Bitmap-based index, to accelerate CER. Firstly, ACER achieves a low index space overhead by grouping the events with the same type into a cluster and compressing the cluster data, reducing I/O overhead when reading indexes. Secondly, ACER builds Range Bitmaps for queried attributes and ensures that the events of each cluster in the index block are chronologically ordered. Then, ACER can always obtain ordered query results for a specific event type through merge operations, avoiding sorting overhead. Most importantly, ACER avoids unnecessary disk accesses in indexes and events via window-wise filtering, thus reducing the I/O overhead further. Lastly, we propose an enhanced version of ACER (ACER-E) by optimizing the read/write operation of index blocks and variable query order. Our extensive experiments demonstrate that ACER and ACER-E reduce the query latency by up to one order of magnitude compared with SOTA techniques.

As a complementary solution for Mobile Edge Computing (MEC), Unmanned Aerial Vehicles (UAVs) can temporarily provide reliable and flexible offloading services when edge servers are damaged or unavailable. However, existing UAV-assisted MEC systems suffer from issues such as uneven resource allocation, low utilization efficiency, load imbalance, and poor dynamic adaptability, affecting service quality. Moreover, sensitive user equipment (UE) information faces leakage during the computational process of UAVs. How to jointly optimize the scheduling of servers and UAVs for task offloading and resource allocation without compromising UEs' privacy remains a significant challenge. Thus, this paper proposed a privacy-preserving auction framework (namely Prizty) by considering the trajectory of UAVs, their constrained energy and computational capabilities, and the variability in UE distribution. Prizty employs a combinatorial obfuscation method to protect UEs' privacy and links bidding prices to computational resources and energy characteristics. It calls the sub-algorithm WPA to determine the winners by balancing social costs and utility. Theoretical analysis demonstrates that Prizty satisfies truthfulness and individual rationality while maintaining scalability for large-scale resource allocation problems. Extensive experiments on real-world datasets validate Prizty's effectiveness in critical metrics, including offload rate, average service latency, energy consumption, and social cost.

API recommendation is a crucial task in code intelligence, aiming to suggest suitable APIs for programming queries. Recent efforts have integrated Large Language Models (LLMs) into this task. However, these methods overlook the compatibility between recommended APIs and fail to fully utilize the factual knowledge of APIs. Moreover, these prompting-only methods are limited by the insufficient domain-specific knowledge of LLMs. In this article, we propose a novel fine-tuning method, KDRAR, designed to leverage knowledge-driven reasoning with LLMs for compatible and interpretable API recommendation. To fully utilize the factual knowledge, we introduce a dual matching strategy that leverages both function descriptions and keyword matching to retrieve candidate APIs. To handle compatibility, we translate compatibility information into descriptive knowledge, which is integrated into the recommendation process. Furthermore, we adopt a distilled fine-tuning strategy: a student LLM is trained via distillation from a teacher LLM to perform step-by-step reasoning for enhanced recommendation and explanation. By considering both function matching and compatibility information, the knowledge-driven reasoning not only improves API recommendation accuracy but also provides reasonable explanations for the recommendations. Experimental results show that our method significantly outperforms baseline methods on API recommendation tasks across multiple API domains.

This is an erratum for the article “Knowledge-Driven Reasoning for Compatible and Interpretable API Recommendation via Teacher LLM Distillation” published in ACM Trans. Inf. Syst. 44, 1, Article 27 (December 2025), 30 pages.

In modern GPU-centric clusters, large-scale AI training relies on two distinct communication domains: a high-bandwidth intra-node domain using proprietary interconnects (e.g., NVLink), and a scale-out inter-node network domain (e.g., RDMA). We observe that the widely-used ring algorithm, often create a significant load imbalance across these domains. This leads to the counter-intuitive scenario where the expensive, high-bandwidth intra-node domain becomes a performance bottleneck, while the inter-node network remains underutilized. This inefficiency is further exacerbated by the disparity in bandwidth provisioning: inter-node network bandwidth is generally more cost-effective and accessible, whereas intra-node bandwidth is often proprietary and more costly to scale. To address this fundamental imbalance, we propose RAIL, aimed at resolving the intra-node bottleneck by strategically rearranging inter-GPU communication paths. This rebalancing ensures that traffic loads are appropriately matched with the distinct transmission capabilities of each domain, thereby maximizing overall communication performance. RAIL incorporates a Load Distributing Strategy (LDS) that can accurately partition physical nodes into logical nodes based on the a transmission capabilities of both domains, shifting excess traffic from the overloaded intra-node domain to the underutilized network domain. Additionally, the Intra-Rail Strategy (IRS) leverages topological characteristics to ensure optimal communication paths through the network domain between logical nodes. Our evaluation demonstrates that RAIL effectively mitigates congestion and achieves a 30.7% average increase in collective communication bus bandwidth compared to the widely-used NCCL solution.

With the increasing migration of business operations to the cloud, cloud service providers are facing a growing demand for faster database synchronization across diverse network conditions. Thus, compression methods are predominantly employed over the synchronized database binlog files to reduce the volume of data to be transmitted across the network. However, previous solutions typically rely on using one single compression method. This can result in data compression rates failing to align well with network bandwidth, causing data to wait for compression or transmission, thereby leading to inferior performance. To address the above issues, we propose a fine-grained hybrid adaptive compression system that (1) parses binlog files into multiple fine-grained blocks, and (2) applies a hybrid combination of multiple compression methods to seamlessly align compression speed with the network bandwidth. We have conducted extensive evaluations which demonstrate that, compared to the cutting-edge compression methods like ZSTD, LZ4, and Snappy, our approach can cut down the average latency by 66% and improve the synchronization throughput by 2.45×.

Monotonic graph algorithms, such as shortest path, BFS, and reachability, are fundamental to graph analytics and are widely used across domains. Recent systems employ pruning techniques to accelerate the processing of these algorithms. However, state-of-the-art monotonic graph engines are restricted to in-memory execution and cannot scale to graphs that exceed main memory capacity. In contrast, existing out-of-core graph engines are designed for general-purpose workloads and lack effective pruning mechanisms tailored to monotonic graph algorithms. To bridge this gap, we present Gem, an out-of-core graph engine designed for monotonic graph algorithms. Gem introduces a PageRank-based graph sketch that captures key topological features inmemory with minimal preprocessing overhead. Building on this sketch, we propose a novel graph abstraction that enables the direct derivation of tight bounds for monotonic graph algorithms, supporting effective pruning at both the vertex and partition levels. Comprehensive evaluations on six real-world datasets, including the 42.5-billion-edge ClueWeb graph, show that Gem significantly outperforms existing systems. It achieves up to 135.40× speedup over GridGraph and 12.58× over Wonderland in out-of-core settings, and also delivers substantial improvements in other modes: up to 10.41× over RisGraph in memory and 20.64× over CGgraph out-of-GPU memory.

Learned indexes, which model key-value data structures by machine learning models, have been extensively studied. However, the fastest immutable learned indexes (e.g., RMI) do not provide the same tight lookup bounds as classical indexes such as B-trees. There are learned indexes that provide tight bounds (e.g., PGM) but those fall short in query performance. This gives rise to an interesting open question: whether there exists a learned index that simultaneously achieves state-of-the-art empirical performance and matching complexity? In this paper, we give a positive answer to this standing problem.We propose two new online model-building policies: (1) simplifying distribution by the adoption of a proper granularity (i.e., grouping multiple keys together for model-building) and (2) actively tuning distribution through key repositioning. Additionally, we introduce a general framework that combines these two policies for performance optimization under a given memory budget. We put everything together to design VEGA, a learned index that simultaneously achieves competitive theoretical and empirical performance compared to state-of-the-art learned indexes. We conducted extensive evaluations, demonstrating VEGA achieves both better lookup and building performance.

Range filters can check whether a queried range is non-empty within a key set, with no false negatives and a low false positive rate. However, existing range filters fail to address recurring false positives in skewed or adversarial queries. In this paper, we propose Hourglass, an adaptive range filter that defends against recurring false positives through lightweight hybrid encoding and semi-sorted adaptivity. Hourglass partitions keys into prefixes, stored in a semi-sorted cuckoo filter, and suffixes, encoded using hybrid encoding schemes based on their sparsity. By preserving the order of fingerprints, the semi-sorted cuckoo filter improves space efficiency. Additionally, Hourglass introduces a new adaptivity strategy that updates fingerprints without violating the semi-sorting order. Further, Hourglass introduces a correlation-aware space allocation model to optimize space across varying key-query correlation degrees. The evaluations show that Hourglass outperforms state-of-the-art range filters under adversarial workloads, achieving a 9.8-35.4X lower false positive rate. Moreover, they demonstrate that Hourglass delivers robust performance on both synthetic and real-world datasets, as well as under varying key-query correlation degrees.

Approximate membership query (AMQ) data structures can approximately determine whether an element exists in a given dataset. They are widely used in parallel and distributed systems (e.g., high-performance databases, distributed cache systems, and bioinformatics systems) to avoid unnecessary dataset accesses, thereby accelerating massive data processing. For AMQ data structures used in the above systems, achieving high throughput, low false positive rate, and large capacity objectives simultaneously is critical but challenging. Porting AMQ data structures from DRAM to persistent memory makes it possible to achieve the above three objectives simultaneously, but this porting is not a trivial task. Specifically, existing AMQ data structures generate numerous random accesses and/or sequential writes on persistent memory, resulting in poor throughput. Therefore, in the conference version of this paper, we proposed a novel AMQ data structure called wormhole filter, which achieves high throughput on persistent memory, thereby achieving the above three objectives simultaneously. In this journal version, we extend our prior work by introducing parallel wormhole filters to enhance parallel performance. Additionally, we integrate parallel wormhole filters into the LevelDB database system to show that porting AMQ data structures to persistent memory significantly improves system endto-end throughput. Theoretical analysis and experimental results show that wormhole filters significantly outperform state-of-theart AMQ data structures. For example, wormhole filters achieve 12.06× insertion throughput, 1.98× positive lookup throughput, and 8.82× deletion throughput of the best competing baseline.

Approximate membership query (AMQ) data structures can approximately determine whether an element is in the set with high efficiency. They are widely used in distributed systems, database systems, bioinformatics, IoT applications, data stream mining, etc. However, the memory consumption of AMQ data structures grows rapidly as the data scale grows, which limits the system's ability to process a massive amount of data. The emerging persistent memory provides a close-to-DRAM access speed and terabyte-level capacity, facilitating AMQ data structures to handle massive data. Nevertheless, existing AMQ data structures perform poorly on persistent memory due to intensive random accesses and/or sequential writes. Therefore, we propose a novel AMQ data structure called wormhole filter, which achieves high performance on persistent memory by reducing random accesses and sequential writes. In addition, we reduce the number of log records for lower recovery overhead. Theoretical analysis and experimental results show that wormhole filters significantly outperform competitive state-of-the-art AMQ data structures. For example, wormhole filters achieve 23.26× insertion throughput, 1.98× positive lookup throughput, and 8.82× deletion throughput of the best competing baseline.

Stream processing jobs often require elastic scaling in response to dynamically changing loads. In recent years, the development of serverless technology has provided new potential for elastic scaling of stream processing jobs. However, directly implementing stream processing jobs to serverless platforms faces many challenges such as program complexity, high latency and load imbalance. In this paper, we propose an efficient stream processing system under serverless environment. Our system provides a high-level programming interface and can automatically determine the parallelism under the current load through a non-linear model. Additionally, it reduces the latency and increases the throughput of stream processing jobs through decentralized orchestration and soft affinity scheduling policies. We conducted a series of experiments to evaluate the performance of our system. The experimental results show that our system effectively improves the throughput and reduces the latency of stream processing jobs under serverless environment compared with the widely-used scheduling and orchestration methods used in serverless environment.

In this paper, we consider the problem of approximate membership testing problem on skewed network traffic traces, in which some hot or popular items repeat frequently. Previous solutions suffer from either high false positive rates or low lookup throughput. To address this problem, we propose a variant of the cuckoo filter, enhanced with a hotness-aware suffix cache. We note that a false positive item must have a matched fingerprint in the cuckoo filter, and propose to reduce false positives by memorizing them, but with their suffixes only. For each false positive item, we apply a linear-congruential-based hash function and then divide the hash value into three parts: the bucket index to be accessed in the cuckoo filter, the fingerprint to be stored in the cuckoo filter, and the suffix to be cached. Combining the three parts, we propose RCF that can uniquely identify a hot false positive item, which thus reduces hot false positives. Our evaluation results indicate that RCF significantly outperforms non-adaptive filters on skewed data traces. Given the same memory size, it achieves a much lower false positive ratio without sacrificing its lookup throughput. Compared with adaptive filters, RCF provides a competitive false positive ratio while offering a considerably higher lookup throughput.

Complex event recognition (CER) refers to identifying specific patterns composed of several primitive events in event stores. Since full-scanning event stores to identify primitive events holding query constraint conditions will incur costly I/O overhead, a mainstream and practical approach is using index techniques to obtain these events. However, prior index-based approaches suffer from significant I/O and sorting overhead when dealing with high predicate selectivity or long query window (common in real-world applications), which leads to high query latency. To address this issue, we propose ACER, a Range Bitmap-based index, to accelerate CER. Firstly, ACER achieves a low index space overhead by grouping the events with the same type into a cluster and compressing the cluster data, alleviating the I/O overhead of reading indexes. Secondly, ACER builds Range Bitmaps in batch (block) for queried attributes and ensures that the events of each cluster in the index block are chronologically ordered. Then, ACER can always obtain ordered query results for a specific event type through merge operations, avoiding sorting overhead. Most importantly, ACER avoids unnecessary disk access in indexes and events via two-phase filtering based on the window condition, thus alleviating the I/O overhead further. Our experiments on six real-world and synthetic datasets demonstrate that ACER reduces the query latency by up to one order of magnitude compared with SOTA techniques.

Index structures are powerful tools for improving query performance and reducing disk access in database systems. Multi-dimensional indexes, in particular, are used to filter records effectively based on multiple attributes. Classical multi-dimensional index structures, such as KD-Tree, Quadtree, and R-Tree, have been widely used in modern databases. However, advancements in hardware and algorithms have led to the emergence of new types of multi-dimensional index structures. In this paper, we begin by reviewing classical multi-dimensional indexes. Next, we explore the approaches that leverage modern hardware features, such as Solid-State Drive, Non-Volatile Memory, Dynamic Random Access Memory, and Graphics Processing Unit, to improve the performance of multi-dimensional indexes in various aspects. Then, we investigate the novel work of multi-dimensional indexes that apply state-of-the-art machine learning techniques. Finally, we discuss the challenges and future research directions for multi-dimensional indexing methods.

Charger placement is an important problem in improving the quality of service in wireless rechargeable sensor networks. This paper studies the problem ofWireless ChArger PlacemeNt with Multiple (Directional) Antennas (WANDA). The problem is described as follows: given a set of wireless chargers equipped with multiple directional antennas and a set of wireless rechargeable sensors, determine the chargers' positions and orientations to maximize the overall charging utility. According to the relative positional relationship between the antennas, the problem is classified into Relative Orientation Fixed (WANDA-ROF) and Relative Orientation Unfixed (WANDA-ROU) situations. To address WANDA, we present a piecewise constant function to approximate the nonlinearity of charging power and propose an area discretization technique to reduce the infinite solution space to a limited one without performance loss. Then, we prove the monotonic submodularity of WANDA, and present a$\frac{1}{2}-\epsilon$approximation algorithm for the ROF situation and a$\frac{1}{2}-\epsilon$approximation algorithm for the ROU situation, all run in polynomial time. Finally, we conduct extensive simulation and experiments to show that our algorithms outperform comparison algorithms by at least 16% for ROF situation and 12% for ROU situation.

Truck-drone systems, wherein trucks carrying drones drive to pre-planned positions and then free drones equipped with cameras to monitor a known number of objects with reported positions, have been used for various scenarios. An object's quality of monitoring (QoM) by a camera is defined as a function of camera focal length and monitoring distance. Improving the QoM would help downstream tasks, including object detection and recognition. The monitoring utility is the fusion of all the QoMs of an object from multiple cameras. This paper optimizes theDeploymentOfTrucksAndDrones forObject monitoring (DOTADO) problem,i.e., deploying a truck-drone system, where each drone is equipped with a varifocal camera, to maximize the overall monitoring utility for all objects. Firstly, we model the hybrid system and define monitoring quality and utility. Then, we discretize the solution space into deployment strategies with performance bound. To select deployment strategies, we prove the submodularity of the problem and propose a two-level greedy algorithm with a bounded approximation ratio. Finally, we devise an optimal method to adjust the strategy for energy saving and communication improvement without losing monitoring utility. We perform both simulations and field experiments to verify the proposed framework.

Nowadays, there exists a lot of cross-region data transmission demand on the cloud. It is promising to use serverless computing for data compressing to save the total data size. However, it is challenging to estimate the data transmission time and monetary cost with serverless compression. In addition, minimizing the data transmission cost is non-trivial due to the enormous parameter space. This paper focuses on this problem and makes the following contributions: 1) We propose empirical data transmission time and monetary cost models based on serverless compression. It can also predict compression information, e.g., ratio and speed using chunk sampling and machine learning techniques. 2) For single-task cloud data transmission, we propose two efficient parameter search methods based on Sequential Quadratic Programming (SQP) and Eliminate then Divide and Conquer (EDC) with proven error upper bounds. Besides, we propose a parameter fine-tuning strategy to deal with transmission bandwidth variance. 3) Furthermore, for multi-task scenarios, a parameter search method based on dynamic programming and numerical computation is proposed. We have implemented the system called Fluid-Shuttle, which includes straggler optimization, cache optimization, and the autoscaling decompression mechanism. Finally, we evaluate the performance of Fluid-Shuttle with various workloads and applications on the real-world AWS serverless computing platform. Experimental results show that the proposed approach can improve the parameter search efficiency by over$3\times $compared with the state-of-art methods and achieves better parameter quality. In addition, our approach achieves higher time efficiency and lower monetary cost compared with competing cloud data transmission approaches.

Finding special items in data streams, like heavy hitters, top-$k$items, and persistent items, has always been a hot topic in the field of network measurement. While data streams nowadays are usually high-dimensional, most prior works optimize data structures to accurately find special items according to a certain primary dimension and yield little insight into the correlations between dimensions, where the dimension can be a single data dimension or a combination of multiple data dimensions. Therefore, we propose to find special quadratic elements in data streams to reveal the close correlations between the primary and secondary dimensions. Here, both the primary and secondary dimensions are selected according to specific application purposes. Based on the special items mentioned above, we extend our problem to three applications related to heavy hitters, top-$k$, and persistent items, and design a generic framework DUET to process them. We analyze the error bound of our algorithm theoretically and conduct extensive experiments on four publicly available data sets. Our experimental results show that DUET can achieve 3.5 times higher throughput and three orders of magnitude lower average relative error than cutting-edge algorithms. Moreover, we propose an optimized framework based on DUET, namely O-DUET, to further improve the estimation accuracy. We also discuss a hardware-version DUET and deploy it on Tofino.

The approximate membership query (AMQ) data structure is a kind of space-efficient probabilistic data structure. It can approximately indicate whether an element exists in a set. The AMQ data structure has been widely used in network measurements, network security, network caching,etc. Resizing is an extensively utilized operation of the AMQ data structure, but it can lead to system performance degradation. We summarize two main problems that lead to such degradation. Specifically, one of them is that the resizing operation can block other operations, while the other one is that the throughput of AMQ structures will deteriorate after multiple resizing operations due to more computation cost. However, existing related work cannot alleviate both of them. Therefore, we propose a novel AMQ data structure called bamboo filters, which can alleviate the two problems simultaneously. Bamboo filters can insert, look up, and delete an element in constant time. They can also dynamically resize in a fine-grained way. Furthermore, we propose space utilization adaptive bamboo filters that adaptively trigger resizing operations according to the space utilization, thereby achieving lower average memory consumption. Experimental results show that our scheme significantly outperforms state-of-the-art work. Especially, bamboo filters achieve 2.12$\times$lookup throughput of the logarithmic dynamic cuckoo filter.

Approximate membership query (AMQ) data structures can efficiently indicate whether an element exists in a data set. Therefore, they are widely used in data mining applications such as IoT streaming data mining, anomaly detection, duplicate detection, record linkage, and community discovery. The data amount to be processed in real-world applications often changes frequently and dynamically. Thus, before using the AMQ data structures, it is necessary to configure their capacity to the maximum number of elements that will be stored during runtime. We observe that when the number of elements stored in an AMQ data structure is lower than its capacity, a significant amount of space is wasted, making the false positive rate much higher than expected. To tackle this problem, we propose the variable-length encoding framework. It dynamically adjusts the encoding length of each element according to the number of elements stored in the AMQ data structure. Based on this design, the variable-length encoding framework can make full use of the memory space allocated to AMQ data structures, thereby improving the space efficiency and reducing the false positive rate. In addition, as a general encoding scheme, the variable-length encoding framework can be widely used in different types of AMQ data structures. Theoretical analysis and evaluation results show that AMQ data structures using the variable-length encoding framework have significantly lower false positive rates compared with state-of-the-art AMQ data structures. For example, when the load factor is 25%, the variable-length encoding framework can reduce the false positive rate of AMQ data structures by 88.15% on average (up to 99.40%).

The constantly evolving demands of modern applications pose increasingly higher requirements for key-value (KV) stores, especially when dealing with update-intensive workloads. RocksDB, an LSM-tree-based KV store, has designed a merge operator to optimize update throughput by directly recording the partially modified value fields. However, this operator negatively affects read performance because it will result in the multiple coexistences of partial values for the same key, which thus requires multiple seeks. To address these issues, we propose a KV-store MoonKV designed for update-intensive workload, which implements Logical and Vertical Compaction techniques to efficiently and timely merge partial values, thereby minimizing their coexistence in the LSM-tree. Besides, MoonKV introduces an NVM-based Index and Estimate Search to enhance search efficiency, leveraging high-speed NVM. By incorporating the above techniques, MoonKV significantly reduces the number of partial keys required to search when reading the value of a specific key. Finally, our evaluation shows that MoonKV achieves a 1.6$\times$ −3.2$\times$ throughput improvement compared with other KV stores, such as RocksDB, BlobDB, and MatrixKV, under update-intensive workloads.

With the rapid development of big data technology, big data systems are more and more used to process SQL query jobs. However, intricate big data system parameters have big effects on the quality of service for big data query performance. Moreover, the types of query jobs and data sizes of data sets are diversified, which have different optimal parameters for best running performance. There exist high complexity and difficulties in tuning the big data system parameters for efficient query job execution. To address this issue, we propose Magpie, an efficient big data query tuning system based on the genetic algorithm with customized pruning strategies. The experimental results show that the proposed approaches can reduce big data query job execution time by 35.5% on average compared with the cuttingedge big data system parameter tuning methods.

Approximate query processing (AQP) is one of the key techniques to cope with big data querying problem on account that it obtains approximate answers efficiently. To address non-trivial sample selection and heavy sampling cost issues in AQP, we propose ShadowAQP, an efficient and accurate approach based on attribute-oriented sample size allocation and data generation. We select samples according to group-by and join attributes, and determine the sample size for each group of unique value combinations to improve query accuracy. We design a conditional variational autoencoder model with automatic table data encoding and model update strategies. To further improve accuracy and efficiency, we propose a set of extensions, including parallel multi-round sampling aggregation, data outlier-aware sampling, and dimension reduction optimization. Evaluation results on diversified datasets show that, compared with SOTA approaches, ShadowAQP achieves 5.8× query speed performance improvement on average (up to 12.8×), while reducing query error by 74% on average (up to 95%) at the same time.

Bloom filter is an efficient data structure for filtering negative keys (keys not in a given set) with substantially small space. However, in real-world applications, there widely exist vulnerable negative keys, which will bring high costs if not being properly filtered, especially when positive keys are added/deleted dynamically. Such problem gets more severe when keys within one set are dynamically added or deleted. Recently, there are works focusing on handling such (vulnerable) negative keys by incorporating learning techniques. These learning-based filters fail to work as the learning techniques can hardly handle incremental insertions or deletions. To address the problem, we proposeSeeSawCountingFilter (SSCF), which is innovated with encapsulating the vulnerable negative keys into a unified counter array named seesaw counter array, and dynamically modulating (or varying) the applied hash functions to guard the encapsulated keys from being misidentified. Moreover, we design ada-SSCF to handle the scenarios where the vulnerable negative keys cannot be obtained in advance. We extensively evaluate our SSCF, which shows that SSCF outperforms the cutting-edge filters by$3\times$on averages regarding accuracy while ensuring a low operation latency. All source codes are in (SSCF-authors).

Several recent works have studied mobile charging under the “one-to-many” charging pattern where a single charger can charge multiple devices simultaneously. However, most of them focus on path planning and charging time allocation, but overlook the underlying dependence of the charging efficiency on initial deployment positions of chargers. This paper studies the problem ofPlacing directional wIreless chargers withLimited mObiliTy (PILOT), that is, maximize the overall charging utility for a set of static rechargeable devices on a 2D plane by determining deployment positions, stop positions and orientations, and portions of time for all deployed chargers that can move in a limited area after their deployment. To the best of our knowledge, we are the first to study placement of mobile directional chargers under the “one-to-many” pattern. To address PILOT, we propose a$(\frac{1}{2}-\epsilon)$-approximation algorithm. First, we present a method to approximate nonlinear charging power of chargers, and further propose an approach to construct Maximal Covered Set uniform subareas to reduce the infinite continuous search space for stop positions and orientations to a finite discrete one. Second, we present geometrical techniques to further reduce the infinite solution space for candidate deployment positions to a finite one without performance loss, and transform PILOT to a mixed integer nonlinear programming problem. Finally, we propose a linear programming based greedy algorithm to address it. Simulation and experimental results show that our algorithm outperforms six comparison algorithms by$19.74 \% \sim 500.01 \%$.

Virtualized network functions (VNFs) enable software applications to replace traditional middleboxes, which are more flexible and scalable in the network service provision. This paper focuses on ensuring Service Availability via Failure Elimination (SAFE) using VNF scaling, that is, given the resource requirements of VNF instances, finding an optimal and robust instance consolidation strategy, which can recover from one instance failure quickly. To address the above problem, we present a framework based on rounding and dynamic programming. First, we discretize the range of resource requirements into several sub-ranges, and thus the number of instance types becomes a constant. Second, we further reduce the number of instance types by gathering several small instances into a bigger one. Third, we propose an algorithm built on dynamic programming to solve the instance consolidation problem with a limited number of instance types. Finally, we set up a testbed to profile the functional relationship between the resource and the throughput for different types of VNFs, and conduct simulations to validate our theoretical results according to profiling results. The simulation results show that our algorithm outperforms the standby deployment model by 27.33% on average in terms of the number of servers required. Furthermore, SAFE has marginal overheads, around 7.22%, compared to the instance consolidation strategy without VNF backup consideration.

Nowdays, it is prevalent to train deep learning models in cloud-native platforms that actively leverage containerization and orchestration technologies for high elasticity, low and flexible operation cost, and many other benefits. However, it also faces new challenges and our work is focusing on those related to I/O throughput for training, including complex data access, lack of matching dynamic I/O requirement, and inefficient I/O resource scheduling across different jobs. We proposeFluid, a cloud-native platform that provides DL training jobs with high-level data abstraction calledFluid Datasetto access training data from heterogeneous sources with elastic data acceleration. In addition, it comes with an on-the-fly cache system autoscaler that can match the online training speed and increase the number of cache replicas adaptively to alleviate I/O bottlenecks. To improve the overall performance of multiple DL jobs, Fluid co-orchestrate the data cache and DL jobs by arranging job scheduling in an appropriate order and can also schedule data cache and DL jobs on the same node to realize cache affinity. Experimental results show significant performance improvement of each individual DL job which uses dynamic computing resources with Fluid. For scheduling multiple DL jobs with same datasets, Fluid achieves around 2x performance speedup when integrated with existing widely-used and cutting-edge scheduling solutions through the appropriate job scheduling order. Besides, the cache affinity scheduling policy also improves job execution performance significantly. Fluid is now an open source project hosted by Cloud Native Computing Foundation (CNCF) with many production adopters.

Nowdays, it is prevalent to train deep learning (DL) models in cloud-native platforms that actively leverage containerization and orchestration technologies for high elasticity, low and flexible operation cost, and many other benefits. However, it also faces new challenges and our work is focusing on those related to I/O throughput for training, including complex data access with complicated performance tuning, lack of cache capacity with specialized hardware to match its high and dynamic I/O requirement, and inefficient I/O resource sharing across different training jobs. We propose Fluid, a cloud-native platform that provides DL training jobs with a data abstraction called Fluid Dataset to access training data from heterogeneous sources in a unified manner with transparent and elastic data acceleration powered by auto-tuned cache runtimes. In addition, it comes with an on-the-fly cache system autoscaler that can intelligently scale up and down the cache capacity to match the online training speed of each individual DL job. To improve the overall performance of multiple DL jobs, Fluid can co-orchestrate the data cache and DL jobs by arranging job scheduling in an appropriate order. Our experimental results show significant performance improvement of each individual DL job which uses dynamic computing resources with Fluid. In addition, for scheduling multiple DL jobs with same datasets, Fluid gives around 2x performance speedup when integrated with existing widely-used and cutting-edge scheduling solutions. Fluid is now an open source project hosted by Cloud Native Computing Foundation (CNCF) with adopters in production including Alibaba Cloud, Tencent Cloud, Weibo.com, China Telecom, etc.

The approximate membership query (AMQ) data structure is a kind of space-efficient probabilistic data structure. It can approximately indicate whether an element exists in a set. The AMQ data structure has been widely used in database indexing, network security, IoT applications, etc. Resizing is an extensively utilized operation of the AMQ data structure, but it can lead to system performance degradation. We summarize two main problems that lead to such degradation. Specifically, one of them is that the resizing operation can block other operations, while the other is that the performance of AMQ structures will deteriorate after multiple resizing operations. However, existing related work cannot alleviate both of them. Therefore, we propose a novel AMQ data structure called bamboo filter, which can alleviate the two problems simultaneously. Bamboo filters can insert, search and delete an element in constant time. Moreover, bamboo filters can dynamically resize in a fine-grained way according to the number of contained elements. Experimental results show that bamboo filters significantly outperform state-of-the-art resizable AMQ data structures in insertion, lookup, and deletion operations. For example, bamboo filters achieve$\mathbf{2.46}\times$lookup throughput of the dynamic cuckoo filter, on average.

The limitation on the flight range motivates a hybrid monitoring system, wherein trucks carrying drones drive to pre-planned positions and then free drones for task execution. While the flight range limitation is mitigated, it is challenging to determine the destination of trucks and drones and set airborne cameras. This paper optimizes the joint Deployment of trUcks and dronEs for objecT monitoring (DUET), that is, deploy a set of trucks where each truck carries drones, and each drone is equipped with a varifocal camera such that the overall monitoring utility for target objects is maximized. To tackle the DUET problem, we first model the hybrid system and monitoring utility; then, discretize the solution space of DUET with performance bound. In this way, the problem is transformed into a two-level combinatorial optimization problem satisfying submodularity. To address it, a two-level greedy algorithm with $\frac{{{{(e - 1)}^2}}}{{e(2e - 1)}} \cdot (1 - \varepsilon )$ approximation ratio is proposed to select deployment strategies. After the strategy selection, an optimal method is devised to carefully adjust the strategy for energy saving and communication improvement without loss of monitoring utility. Both simulations and field experiments are conducted to evaluate the proposed framework, which outperforms baseline algorithms on monitoring utility by at least 28.4% and 40%, respectively.

This paper studies the problem of Wireless ChArger PlacemeNt with Multiple (Directional) Antennas (WANDA). Given a set of wireless chargers wherein each charger is equipped with multiple directional antennas and a set of wireless rechargeable sensors, determining the chargers' positions and the antennas' orientations, such that the overall charging utility is maximized. To address WANDA, we first present a piecewise constant function to approximate the nonlinear relationship between charging power and charging distance. Then, we propose an area discretization technique to reduce the infinite solution space to a limited one without performance loss. Next, we present approximation algorithms for both Relative Orientation Fixed (WANDA-ROF) and Relative Orientation Unfixed (WANDA-ROU) situations. For WANDA-ROF, we propose a Maximum Coverage Set extraction method that transforms WANDA-ROF into the problem of maximizing a monotone submodular function subject to a partition matroid constraint and then present a$1/2 -\epsilon$approximation algorithm. For WANDA-ROU, we construct a candidate position set for each charger to limit the searching space. Then, we propose a novel two-level submodular optimization scheme to address it, which achieves an approx-imation ratio of 1/6 - ∊. Simulation and experimental results show that our algorithms outperform comparison algorithms by at least 22%.

Bloom filter is an efficient data structure for filtering negative keys (keys not in a given set) with substantially small space. However, in real-world applications, there widely exist vulnerable negative keys, which will bring high costs if not being properly filtered, especially when positive keys are added/deleted dynamically. To address the problem, we propose SeeSaw Counting Filter (SSCF), which is innovated with encapsulating the vulnerable negative keys into a unified counter array named seesaw counter array, and dynamically modulating (or varying) the applied hash functions to guard the encapsulated keys from being misidentified. Moreover, we propose ada-SSCF to handle the scenarios where the vulnerable negative keys cannot be obtained in advance. We extensively evaluate our SSCF, which shows that SSCF outperforms the cutting-edge filters by 3 × on averages regarding accuracy while ensuring a low operation latency. All source codes are in [2].

Deep learning (DL) is becoming increasingly popular in many domains, including computer vision, speech recognition, self-driving automobiles, etc. GPU can train DL models efficiently but is expensive, which motivates users to share GPU resource to reduce money costs in practice. To ensure efficient sharing among multiple users, it is necessary to develop efficient GPU resource management and scheduling solutions. However, existing ones have several shortcomings. First, they require the users to specify the job resource requirement which is usually quite inaccurate and leads to cluster resource underutilization. Second, when scheduling DL jobs, they rarely take the cluster network characteristics into consideration, resulting in low job execution performance. To overcome the above issues, we propose Liquid, an efficient GPU resource management platform for DL jobs with intelligent resource requirement estimation and scheduling. First, we propose a regression model based method for job resource requirement estimation to avoid users over-allocating computing resources. Second, we propose intelligent cluster network-efficient scheduling methods in both immediate and batch modes based on the above resource requirement estimation techniques. Third, we further propose three system-level optimizations, including pre-scheduling data transmission, fine-grained GPU sharing, and event-driven communication. Experimental results show that our Liquid can accelerate the job execution speed by 18% on average and shorten the average job completion time (JCT) by 21% compared with cutting-edge solutions. Moreover, the proposed optimization methods are effective in various scenarios.

Bloom filter is a compact memory-efficient probabilistic data structure supporting membership testing, i.e., to check whether an element is in a given set. However, as Bloom filter maps each element with uniformly random hash functions, few flexibilities are provided even if the information of negative keys (elements are not in the set) are available. The problem gets worse when the misidentification of negative keys brings different costs. To address the above problems, we propose a new Hash Adaptive Bloom Filter (HABF) that supports the customization of hash functions for keys. The key idea of HABF is to customize the hash functions for positive keys (elements are in the set) to avoid negative keys with high cost, and pack customized hash functions into a lightweight data structure named HashExpressor. Then, given an element at query time, HABF follows a two-round pattern to check whether the element is in the set. Further, we theoretically analyze the performance of HABF and bound the expected false positive rate. We conduct extensive experiments on representative datasets, and the results show that HABF outperforms the standard Bloom filter and its cutting-edge variants on the whole in terms of accuracy, construction time, query time, and memory space consumption (Note that source codes are available in [1]).

Abstract Nowadays, the financial securities investment and transaction are processed digitally. The securities companies have accumulated a large amount of financial data. Given that, quantitative analysis has become a common method for securities investors. However, as the scale of data continues to grow, data storing and processing have increasingly become a big challenge to financial quantitative analysts. First, most existing stand‐alone quantitative analysis systems are hard to accelerate data processing in a distributed way. Second, existing distributed computing frameworks such as Apache Spark demands financial quantitative analysts with expertise knowledge on distributed computing. Third, transition from traditional stand‐alone financial quantitative analysis (FQA) system to such distributed computing system often introduces learning efforts and development overheads. To solve these problems, we propose Alchemy, a distributed processing platform tailored for FQA with high‐level programming interface. Alchemy offers distributed computing service and provides a pipeline‐based programming model which shares many similarities with the traditional stand‐alone systems, reducing learning efforts for financial quantitative analysts. The performance of Alchemy is evaluated in both experimental environment and a real‐world production environment in Huatai Securites which is a leading financial company in China. The results show that Alchemy is able to achieve up to 300 times speedup compared against existing financial quantitative analysis systems.

Static program analysis has been widely applied along the whole process of the program development for bug detection, code optimization, testing, etc. Although researchers have made significant work in static program analysis, it is still challenging to perform sophisticated interprocedural analysis on large-scale modern software. The underlying reason is that interprocedural analysis for large-scale modern software is highly computation- and memory-intensive, leading to poor efficiency and scalability. In this article, we introduce an efficient distributed and scalable solution for sophisticated static analysis. Specifically, we propose a data-parallel algorithm and a join-process-filter computation model for the CFL-reachability-based interprocedural analysis. Based on that, an efficient distributed static analysis engine called BigSpa is developed, which is composed of an offline batch static program analysis system and an online incremental static program analysis system. The BigSpa system has high generality and can support all kinds of static analysis tasks that can be expressed as CFL reachability problems. The performance of BigSpa is evaluated on real-world large-scale software datasets. Our experiments show that the offline batch system can exceed an order of magnitude compared with the most advanced analysis tools available on performance, and for incremental analysis with small batch updates on the same data sets, the online analysis system can achieve near real-time response, which is very fast and flexible.

Finding or monitoring subgraph instances that are isomorphic to a given pattern graph in a data graph is a fundamental query operation in many graph analytic applications, such as network motif mining and fraud detection. Existing distributed methods are inefficient in communication. They have to shuffle partial matching results during the distributed multiway join. The partial matching results may be much larger than the data graph itself. To overcome the drawback, we develop the Batch-BENU framework for distributed subgraph enumeration on static data graphs. Batch-BENU executes a group of local search tasks in parallel. Each task enumerates subgraphs around a vertex in the data graph, guided by a backtracking-based execution plan. To handle large-scale data graphs that may exceed the memory capacity of a single machine, Batch-BENU stores the data graph in a distributed database. Each task queries adjacency sets of the data graph on demand, shuffling the data graph instead of partial matching results. To support incremental subgraph enumeration on dynamic data graphs, we propose the Streaming-BENU framework. Streaming-BENU turns the problem of enumerating incremental matching results into enumerating all matching results of incremental pattern graphs at each time step. We implement Batch-BENU and Streaming-BENU with the local database cache and the load balance optimization to improve their efficiency. Extensive experiments show that Batch-BENU and Streaming-BENU can scale to big graphs and complex pattern graphs. They outperform the state-of-the-art distributed methods by up to one and two orders of magnitude, respectively.

Given a small pattern graph and a large data graph, the task of subgraph enumeration is to find all the subgraphs of the data graph that are isomorphic to the pattern graph. The state-of-the-art distributed algorithms like SEED and CBF turn subgraph enumeration into a distributed multi-way join problem. They are inefficient in communication as they have to shuffle partial matching results that are much larger than the data graph itself during the join. They also spend non-trivial costs on constructing indexes for data graphs. Different from those join-based algorithms, we develop a new backtracking-based framework BENU for distributed subgraph enumeration. BENU divides a subgraph enumeration task into a group of local search tasks that can be executed in parallel. Each local search task follows a backtracking-based execution plan to enumerate subgraphs. The data graph is stored in a distributed database and is queried as needed. BENU only queries the necessary edges of the data graph and avoids shuffling partial matching results. We also develop an efficient implementation for BENU. We set up an in-memory database cache on each machine. Taking advantage of the inter-task and intra-task locality, the cache significantly reduces the communication cost with controllable memory usage. We conduct extensive experiments to evaluate the performance of BENU. The results show that BENU is scalable and outperforms the state-of-the-art methods by up to an order of magnitude.

The multi-way join query plays a fundamental role in many big data analytic scenarios. Recently, the hybrid join query is becoming increasingly important. However, the existing one-round and multi-round algorithms have limitations in the process of the hybrid query. In this paper, we present a novel hybrid structure-aware multi-way join algorithm called HyMJ, which combines the one-round and multi-round algorithms to compute the hybrid query efficiently. First, we propose the query structure graph (QSG) to represent the internal query structure of a given join query and the query structure decomposition tree (QSDT) to represent the structure-aware query plan. Each internal node of the QSDT denotes a subquery with a cyclic or acyclic query structure. Then, we design a graph contraction based algorithm to construct QSDT from QSG. Furthermore, to select the optimal join strategy for each subquery in the QSDT, we introduce a heuristic strategy selection model. Experimental results on Apache Spark reveal that HyMJ outperforms both the one-round and multi-round algorithms for hybrid multi-way join queries on real-world datasets.

In the big data era, data-intensive cluster computing systems like Hadoop, have gained much popularity, and YARN, the second generation of Hadoop becomes the general resource manager in the Hadoop ecosystem. In the distributed computing scenarios, data locality (scheduling tasks on where the data resides) is essential to the performance since higher data locality brings lower network transmission cost and higher throughput. However, we find that the native YARN scheduling mechanism has little data locality and the delay scheduling strategy leads to the long-tail effect while achieving data locality for in-memory computing scenarios. Therefore, in this paper we propose the push-based YARN scheduling mechanism for the in-memory computing environment. First, we classify the Resource Requests into various categories. Then, we prune the non-local Resource Requests to achieve fast datalocality in-memory computation. Finally, we push the left longtail Resource Requests to the data-locality nodes to avoid the long-tail effect. The experimental results demonstrate that the proposed scheduling mechanism achieves nearly 100% datalocality percentage comparing to the native YARN scheduling mechanism that only achieves 10% 20% data-locality percentage. Under the identical data-locality percentage, the proposed push based scheduling mechanism promotes nearly 20% throughput and reduces nearly 10% application running time comparing to the existing delay scheduling mechanism used in YARN.

Virtualized network functions (VNFs) enable software applications to replace traditional middleboxes, which is more flexible and scalable in the network service provision. This paper focuses on ensuring Service Availability via Failure Elimination (SAFE) using VNF scaling, that is, given the resource requirements of VNF instances, finding an optimal and robust instance consolidation strategy, which can recover from one instance failure quickly. To address the above problem, we present a framework based on rounding and dynamic programming. First, we discretize the range of resource requirements for VNF instances deployment into several sub-ranges, so that the number of instance types becomes a constant. Second, we further reduce the number of instance types by gathering several small instances into a bigger one. Third, we propose an algorithm built on dynamic programming to solve the instance consolidation problem with a limited number of instance types. We set up a testbed to profile the functional relationship between resource and throughput for different types of VNF instances, and conduct simulations to validate our theoretical results according to profiling results. The simulation results show that our algorithm outperforms the standby deployment model by 27.33% on average in terms of the number of servers required. Furthermore, SAFE has marginal overhead, around 7.22%, compared to instance consolidation strategy without VNF backup consideration.

Static program analysis is widely used in various application areas to solve many practical problems. Although researchers have made significant achievements in static analysis, it is still too challenging to perform sophisticated interprocedural analysis on large-scale modern software. The underlying reason is that interprocedural analysis for large-scale modern software is highly computation- and memory-intensive, leading to poor scalability. We aim to tackle the scalability problem by proposing a novel big data solution for sophisticated static analysis. Specifically, we propose a data-parallel algorithm and a join-process-filter computation model for the CFL-reachability based interprocedural analysis and develop an efficient distributed static analysis engine in the cloud, called BigSpa. Our experiments validated that BigSpa running on a cluster scales greatly to perform precise interprocedural analyses on millions of lines of code, and runs an order of magnitude or more faster than the existing state-of-the-art analysis tools.

Summary Multitiered storage systems, which are made up of heterogeneous devices, are widely used in distributed environments to accelerate the I/O performance of upper big data applications. It raises new challenges in efficient data migration through smart caching mechanisms among heterogeneous storage levels, such as MEM‐SSD‐HDD. To optimize the cache policy scheduling mechanism on the distributed tiered storage architecture, we proposed a general framework with five layers, including a tiered storage system layer, a cache migration policy layer, a cache policy adaptive scheduling layer, a data access pattern layer, and a big data application layer. The framework prototype has been designed and implemented on the widely used distributed hybrid storage system named Alluxio. To meet the demands of the big data application layer, on the one hand, we designed a couple of cache eviction policies and promotion policies covering various access patterns on the cache migration policy layer (several proposed eviction policies have been adopted by the Alluxio open‐source community). On the other hand, two adaptive cache policy scheduling algorithms for selecting appropriate policies in various scenarios are designed and implemented on the cache policy adaptive scheduling layer. The scheduling algorithms are designed based on the hit ratio statistics and data access pattern model prediction, respectively. Experimental results show that the proposed cache policies are very effective for various big data applications, such as Spark SQL. The proposed cache policy scheduling algorithms with various eviction policies can improve around 20% hit ratio than that with a single eviction policy.

Functional dependencies (FDs) play a very important role in many data management tasks such as schema normalization, data cleaning, and query optimization. Meanwhile, there are ever-increasing application demands for efficient FD discovery on large-scale datasets. Unfortunately, due to huge runtime and memory overhead, the existing single-machine FD discovery algorithms are inefficient for large-scale datasets. Recently, distributed data-parallel computing has become the de facto standard for large-scale data processing. However, it is challenging to design an efficient distributed FD discovery algorithm. In this paper, we present SmartFD, which is an efficient and scalable algorithm for distributed FD discovery. First, we propose a novel attribute sorting-based algorithm framework. Next, to discover all the FDs grouped by a given attribute, we propose an efficient distributed algorithm Attribute-centric Functional Dependency Discovery (AFDD). In AFDD, we design an Fast Sampling and Early Aggregation (FSEA) mechanism to improve the efficiency of distributed sampling and propose a memory-efficient index-based method for distributed FD validation. Moreover, AFDD employs an attribute-parallel method to accelerate the pruning-and-generation of candidate FDs. Furthermore, we propose an adaptive switching strategy between distributed sampling and distributed validation based on the unified time-based efficiency metric. Also, we employ a distributed probing based method to make the switching strategy more accurate. Experimental results on Apache Spark reveal that SmartFD outperforms the state-of-the-art single-machine algorithm HyFD and the existing distributed algorithm HFDD with 3.2×-44.9× and 2.5×-455.7× speedup respectively. Moreover, SmartFD achieves good row scalability and column scalability. Additionally, SmartFD has sub-linear node scalability.

Statistical machine translation (SMT) is an important research branch in natural language processing (NLP). Similar to many other NLP applications, large scale training data can potentially bring higher translation accuracy for SMT models. However, the traditional single-node SMT model training systems can hardly cope with the fast-growing amount of large scale training corpus in the big data era, which makes the urgent requirement of efficient large scale machine translation model training systems. In this paper, we propose Seal, an efficient, scalable, and end-to-end offline SMT model training toolkit based on Apache Spark which is a widely-used distributed data-parallel platform. Seal parallelizes the training process of the entire three key SMT models that are the word alignment model, the translation model, and the N -Gram language model, respectively. To further improve the performance of the model training in Seal, we also propose a number of system optimization methods. In word alignment model training, by optimizing the block size tuning, the overhead of IO operation and communication is greatly reduced. In translation model training, by well encoding the training corpus, the data size transferred over the network can be reduced significantly, thus improving the overall training efficiency. We also optimize the maximum likelihood estimation (MLE) algorithm to solve the data skew issue on the join operation which is adopted both in the translation model training and the language model training. The experiment results show that Seal outperforms the well-known SMT training system Chaski with about 5× speedup for word alignment model training. For the syntactic translation model and language model training, Seal outperforms the existing cutting-edge tools with about 9~18× speedup and 8~9× speedup on average, respectively. On the whole, Seal outperforms the existing distributed system with 4~6× speedup and the single-node system with 9~60× speedup on average respectively. Besides, Seal achieves near-linear data and node scalability.

In the big data era, machine learning optimization algorithms usually need to be designed and implemented on widely-used distributed computing platforms, such as Apache Hadoop, Spark, and Flink. However, these general distributed computing platforms themselves do not focus on parallelizing machine learning optimization algorithms. In this paper, we present a parallel optimization algorithm framework for scalable machine learning, and empirically evaluate the synchronous Elastic Averaging SGD (EASGD) and other distributed SGD-based optimization algorithms. First, we design a distributed machine learning optimization algorithm framework based on Apache Spark by adopting the parameter server. Then, we design and implement the widely-used distributed synchronous EASGD and several other popular SGD-based optimization algorithms, such as Adadelta and Adam, on top of the framework. In addition, we evaluate the performance of synchronous distributed EASGD compared with other distributed optimization algorithms based on the same framework. Finally, to explore the optimal settings of mini-batch size in large-scale distributed optimization, we further analyze the empirical linear scaling rule originally proposed in the single-node environment. Experimental results show that our parallel optimization algorithm framework achieves good flexibility and scalability. And, the distributed synchronous EASGD runs over the proposed framework gains a competitive convergence performance and is about 5.7% faster than other distributed SGD-based optimization algorithms. Experimental results also verified that the empirical linear scaling rule only holds well before the mini-batch size exceeds certain threshold on large-scale benchmarks in the distributed environment.

In the big data era, there are many demands for efficient and easy to use data replay services over large scale historical data. For example, stock security trading and on-line e-business services need historical data replay services to conduct system testing or ex-post review and analysis, just like replaying videos for security monitoring. Stream processing systems are designed for processing stream data, thus can not perform complex replay jobs over the static historical data. Database management systems support easy to use complex queries, but lack stream processing abilities. In this paper, we present a data replay model that combines the stream replay and complex query ability together, to allow the applications to replay large scale historical data from various data sources. First, to meet the demands of flexible replay semantics, we designed a set of easy to use replay operators to describe various replay behaviors and semantics. Users can use these operators to build up their complex replay jobs with diversified requirements. Then, we proposed a query mechanism to provide a flexible data loading service. Next, we presented the Penguin framework to support the proposed query-based replay model along with the replay operators. Penguin enables users to develop high-throughput and easy to use replay services over various large scale data sources with tunable replay speeds. To further improve the data replay performance, we proposed four system-level optimizations, including caching loading task results, cascading merging intermediate record queues, producing the replay queue in parallel, and caching remote file streams. Experimental results over replaying millions of records demonstrate that Penguin can achieve up to 4x and 144x speedup in data preparation and up to 16x and 9x speedup in replay speed compared to Apache Phoenix and Apache Hive respectively. As a case study, Penguin has been deployed in production environments of some Securities companies to provide online historical stock data replay services to large number of stock market users.

The multi-way join query has attracted considerable attention from research community for its importance in many big data analytic applications. For the multi-round multi-way join algorithm in distributed data-parallel platforms, the huge communication cost caused by shuffling large intermediate results over the network is the main bottleneck. The one-round multi-way join algorithm processes the join query in a single communication round, which can significantly reduce the communication cost in complex queries, including cyclic queries. However, the one-round method is not always superior to the multi-round method, because the intermediate result size of the multi-round method may the much smaller than the size of data shuffled in the one-round method. Therefore, it is challenging to choose the best multi-way join algorithm in practice. To solve this problem, in this paper, we present AutoMJ, an efficient framework for multi-way join queries. In AutoMJ, we propose a novel automatic join strategy selection model based on the size estimation of intermediate join results. AutoMJ chooses the multi-way join strategy with the minimal shuffle data size. In addition, we propose an optimized HyperCube algorithm for the one-round multi-way join. We have implemented the prototype of AutoMJ on the widely-used distributed data-parallel platform Apache Spark. Experiments show that for multi-way join queries with large intermediate results, the one-round join strategy can outperform the multi-round join strategy built in Spark SQL 1.2 - 159.3× faster. In contrast, the multi-round join strategy is 2.1 - 6.2× faster than the one-round method for the queries with small intermediate results. Experiments also show that the relative error of size estimation can be within 0.1 for the Twitter dataset and 0.25 for the Wikidata dataset. Furthermore, experiments verify that the automatic join strategy selection model is effective for choosing the optimal multi-way join algorithm.

Matrix multiplication is a dominant but very time-consuming operation in many big data analytic applications. Thus its performance optimization is an important and fundamental research issue. The performance of large-scale matrix multiplication on distributed data-parallel platforms is determined by both computation and IO costs. For existing matrix multiplication execution strategies, when the execution concurrency scales up above a threshold, their execution performance deteriorates quickly because the increase of the IO cost outweighs the decrease of the computation cost. This paper presents a novel parallel execution strategy CRMM (Concurrent Replication-based Matrix Multiplication) along with a parallel algorithm, Marlin, for large-scale matrix multiplication on data-parallel platforms. The CRMM strategy exploits higher execution concurrency for sub-block matrix multiplication with the same IO cost. To further improve the performance of Marlin, we also propose a number of novel system-level optimizations, including increasing the concurrency of local data exchange by calling native library in batch, reducing the overhead of block matrix transformation, and reducing disk heavy shuffle operations by exploiting the semantics of matrix computation. We have implemented Marlin as a library along with a set of related matrix operations on Spark and also contributed Marlin to the open-source community. For large-sized matrix multiplication, Marlin outperforms existing systems including Spark MLlib, SystemML and SciDB, with about 1.29×, 3.53× and 2.21× speedup on average, respectively. The evaluation upon a real-world DNN workload also indicates that Marlin outperforms above systems by about 12.8×, 5.1× and 27.2× speedup, respectively.

Matrix computation is the core of many massive data-intensive analytical applications such mining social networks, recommendation systems and nature language processing. Due to the importance of matrix computation, it has been widely studied for many years. In the Big Data ear, as the scale of the matrix grows, traditional single-node matrix computation systems can hardly cope with such large data and computation. Existing distributed matrix computation solutions are still not efficient enough, or have poor fault tolerance and usability. In this paper, we propose Marlin, an efficient distributed matrix computation library which is built on top of Spark. Marlin contains several distributed matrix operation algorithms and provides high-level matrix computation primitives for users. In Marlin, we proposed three distributed matrix multiplication algorithms for different situations. Based on this, we designed an adaptive model to choose the best approach for different problems. Moreover, to improve the computation performance, instead of naively using Spark, we put forward some optimizations including taking advantage of the native linear algebra library, reducing shuffle communication and increasing parallelism. Experimental results show that Marlin is over an order of magnitude faster than R (a widely-used statistical computing system) and the existing distributed matrix operation algorithms based on MapReduce. Moreover, Marlin achieves comparable performance to the specialized MPI-based matrix multiplication algorithm SUMMA but uses a general dataflow engine and gains common dataflow features such as scalability and fault tolerance.

In the era of big data, the volume of semantic data grows rapidly. The large scale semantic data contains a lot of significant but often implicit information that needs to be derived by reasoning. The semantic data reasoning is a challenging process. On one hand, the traditional single-node reasoning systems can hardly cope with such large amount of data due to the resource limitations. On the other hand, the existing large scale reasoning systems are not very efficient and scalable due to the complexity of reasoning process. In this paper, we propose Cichlid, an efficient distributed reasoning engine for the widely-used RDFS and OWL Horst rule sets. Cichlid is built on top of Spark. It implements parallel reasoning algorithms with the Spark RDD programming model. Further, we proposed the optimized parallel RDFS reasoning algorithm from three aspects, including data partition model, the execution order of reasoning rules and removing of duplicated data. Then, for the parallel OWL reasoning process, we optimized the most time-consuming parts, including large-scale data join, the transitive closure computation and the equivalent relation computation. In addition to above optimizations at the reasoning algorithm level, we also optimized the inner Spark execution mechanism by proposing an off-heap memory storage mechanism for RDD. This system-level optimization patch has been accepted and integrated into Apache Spark 1.0. The experimental results show that Cichlid is around 10 times faster on average than the state-of-the-art distributed reasoning systems for both large scale synthetic and real-world benchmarks. The proposed reasoning algorithms and engine also achieve excellent scalability and fault tolerance.

In the Big Data era, the ever-increasing RDF data have reached a scale in billions of triples and brought obstacles and challenges to single-node RDF data stores. As a result, many distributed RDF stores have been emerging in the Semantic Web community recently. However, currently published ones are either not enough efficient on performance or failed to achieve flexible scalability. In this paper, we propose Rainbow, a scalable and efficient RDF triple store. The RDF data indexing scheme in Rainbow is a hybrid one which is designed based on the statistical analysis of user query space. Further, to better support the hybrid indexing scheme, Rainbow adopts a distributed and hierarchical storage architecture that uses HBase as the scalable persistent storage and combines a distributed memory storage to speedup query performance. The RDF data in memory storage is partitioned by the consistent hashing algorithm to achieve the dynamic scalability. Experiments show that Rainbow outperforms typical existing distributed RDF triple stores, with excellent scalability and fault tolerance.

Artificial neural networks (ANNs) have been proved to be successfully used in a variety of pattern recognition and data mining applications. However, training ANNs on large scale datasets are both data-intensive and computation-intensive. Therefore, large scale ANNs are used with reservation for their time-consuming training to get high precision. In this paper, we present cNeural, a customized parallel computing platform to accelerate training large scale neural networks with the backpropagation algorithm. Unlike many existing parallel neural network training systems working on thousands of training samples, cNeural is designed for fast training large scale datasets with millions of training samples. To achieve this goal, firstly, cNeural adopts HBase for large scale training dataset storage and parallel loading. Secondly, it provides a parallel in-memory computing framework for fast iterative training. Third, we choose a compact, event-driven messaging communication model instead of the heartbeat polling model for instant messaging delivery. Experimental results show that the overhead time cost by data loading and messaging communication is very low in cNeural and cNeural is around 50 times faster than the solution based on Hadoop MapReduce. It also achieves nearly linear scalability and excellent load balancing.