Non-volatile memory (NVM), as an emergingstor age technology, offers several advantageous features for OLTP engines, including byte-addressability, high capacity, low energy consumption, and data persistence across power failures. Despite these benefits, the current mainstream OLTP engines still commonly adopt a hybrid architecture that deeply couples DRAM with NVM, which results in a complex system architecture and high recovery costs. In this paper, we aim to construct a highly available, stable, and recoverable OLTP engine that guarantees ACID properties through anagile system architecture. We introduce AKV (Agile Key-Value), an NVM-only OLTP storage engine designed to provide effective space utilization, high throughput, and fast failure recovery. AKV addresses the challenges of NVM space management, write redundancy, and concurrency control with two novel techniques: dual-version concurrency control and circular dual-version storage. Experimental results demonstrate that AKV achieves higher throughput (up to 69.7%) and faster recovery (up to 54×) compared to existing storage engines in most scenarios of the TPC-C benchmarks. Additionally, the codebase of AKV (4k+ lines) is more concise than that of SOTA OLTP engines like Zen (8k+ lines) and Falcon (11k+ lines). In addition, this study innovatively proposes a read abort optimization strategy based on dynamic version changes. The experimental results show that this strategy can significantly reduce the transaction abort rate of AKV in specific workload scenarios while maintaining stable system throughput, achieving a maximum reduction of up to 73% in the abort count.

A k-biplex is an induced subgraph of a bipartite graph which requires every vertex on the one side disconnecting at most k vertices on the other side. Enumerating all maximal k-biplexes in a bipartite graph is a fundamental operator in bipartite graph analysis and finds applications in various domains, including community detection, online recommendation, and fraud detection in finance networks. The state-of-the-art solutions for maximal k-biplex enumeration suffer from efficiency issues as k increases (k ≥ 2), with the time complexity of O(m 2 n ), where n (m) denotes the number of vertices (edges) in the bipartite graph. To address this issue, we propose two theoretically and practically efficient enumeration algorithms based on novel branching techniques. Specifically, we first devise a new branching rule as a fundamental component. Building upon this, we then develop a novel branch-and-bound enumeration algorithm to efficiently enumerate maximal k-biplexes. We prove that our algorithm achieves a worst-case time complexity of O(mα k n ), where α k < 2, thus significantly improving the time complexity compared to previous algorithms. To enhance the performance, we further propose an improved enumeration algorithm based on a novel pivot-based branching rule. Theoretical analysis reveals that our improved algorithm has a time complexity of O(mβ k n ), where β k is strictly less than α k . In addition, we also present several non-trivial optimization techniques, including graph reduction, upper-bounds based pruning, and ordering-based optimization, to further improve the efficiency of our algorithms. Finally, we conduct extensive experiments on 6 large real-world bipartite graphs to evaluate the efficiency and scalability of the proposed solutions. The results demonstrate that our improved algorithm achieves up to 5 orders of magnitude faster than the state-of-the-art solutions.

Benchmarking is crucial for evaluating a DBMS, yet existing benchmarks often fail to reflect the varied nature of user workloads. As a result, there is increasing momentum toward creating databases that incorporate real-world user data to more accurately mirror business environments. However, privacy concerns deter users from directly sharing their data, underscoring the importance of creating synthesized databases for benchmarking that also prioritize privacy protection. Differential privacy (DP)-based data synthesis has become a key method for safeguarding privacy when sharing data, but the focus has largely been on minimizing errors in aggregate queries or downstream ML tasks, with less attention given to benchmarking factors like query runtime performance. This paper delves into differentially private database synthesis specifically for benchmark publishing scenarios, aiming to produce a synthetic database whose benchmarking factors closely resemble those of the original data. Introducing PrivBench , an innovative synthesis framework based on sum-product networks (SPNs), we support the synthesis of high-quality benchmark databases that maintain fidelity in both data distribution and query runtime performance while preserving privacy. We validate that PrivBench can ensure database-level DP even when generating multi-relation databases with complex reference relationships. Our extensive experiments show that PrivBench efficiently synthesizes data that maintains privacy and excels in both data distribution similarity and query runtime similarity.

Mining cohesive subgraphs and communities is a fundamental problem in network analysis and has drawn much attention in the last decade. Most existing cohesive subgraph models mainly consider the structural cohesion but ignore the subgraph significance. In this article, we formulate a new model, called statistically significant clique, to mine significant cohesive subgraphs in large vertex-labeled graphs. A statistically significant clique is a complete subgraph with a significance value exceeding a given threshold. The subgraph significance is evaluated by a widely used metric called chi-square statistic. We study the problem of enumerating all maximal statistically significant cliques. The problem is proved to be NP-hard. We propose an efficient branch-and-bound algorithm with several elegant pruning strategies to solve our problem. We conduct extensive experiments on seven large real-world datasets to show the practical efficiency of our algorithms. We also conduct a case study to evaluate the effectiveness of our proposed model.

The shortest path distance and related concepts lay the foundations of many real-world applications in road network analysis. The shortest path count has drawn much research attention in academia, not only as a closeness metric accompanying the shorted distance but also serving as a building block of centrality computation. This paper aims to improve the efficiency of counting the shortest paths between two query vertices on a large road network. We propose a novel index solution by organizing all vertices in a tree structure and propose several optimizations to speed up the index construction. We conduct extensive experiments on 14 real-world networks. Compared with the state-of-the-art solution, we achieve much higher efficiency on both query processing and index construction with a more compact index.

Structural clustering is a fundamental graph mining operator which is not only able to find densely-connected clusters, but it can also identify hub vertices and outliers in the graph. Previous structural clustering algorithms are tailored to deterministic graphs. Many real-world graphs, however, are not deterministic, but are probabilistic in nature because the existence of the edge is often inferred using a variety of statistical approaches. In this paper, we formulate the problem of structural clustering on probabilistic graphs, with the aim of finding reliable clusters in a given probabilistic graph. Unlike the traditional structural clustering problem, our problem relies mainly on a novel concept called reliable structural similarity which measures the probability of the similarity between two vertices in the probabilistic graph. We develop a dynamic programming algorithm with several powerful pruning strategies to efficiently compute the reliable structural similarities. With the reliable structural similarities, we adapt an existing solution framework to calculate the structural clustering on probabilistic graphs. Comprehensive experiments on five real-life datasets demonstrate the effectiveness and efficiency of the proposed approaches.

Recently, we have seen the unprecedented development in unmanned aerial vehicles (UAVs) from different aspects. Accordingly, an increasing number of applications have emerged based on UAVs. Among which, placing UAVs as Aerial Base Stations (ABSs) has received considerable interest in both the industrial and academic community. Existing solutions focus on the optimization of the UAV deployment problem for static user topology using the control information obtained from the Terrestrial Base Station (TBS), that makes hard for the controller to make real-time decisions. To break this stalemate, we propose a SemI-DistributEd system, named SIDE, for the UAV self-deployment. In SIDE, we introduce a mechanical equilibrium based approach, named EMech, via which the UAV positions are self-adapted according to users' attraction (e.g., user distance and traffic demand) within their transmission range. To facilitate the EMech, we propose a fine-grained area splitting strategy, termed KDivision, that partitions the service area in accordance with the user density. Finally, an area merging technique, namely RMerge, is exploited to approximately optimize the positions of the UAVs assisted by an Utility Function that strikes a balance amid the network performance and economic cost. We conduct field experiments to validate the feasibility of EMech. Extensive simulation results show that the proposed SIDE finds the optimal number of assigned UAVs, which not only reduces the cost of the system significantly, but also improves the achievable rate up to 74.6% compared to the existing solutions while consuming almost the same energy level.

Conflagration is one of the major disasters that threatens human life and property. If the proper action is not taken in detecting the symptom of conflagration events ahead of time, the number of such disasters will keep increasing. An effective solution in this context will alleviate many fire-related global problems to a great extent. Although fire detectors are not available in many places, WiFi networks are increasingly prevalent nowadays. Motivated by the previous works that used WiFi signals for the purpose of environment monitoring and activity recognition, we make an attempt to use WiFi signals to detect fire. Through several experiments, we find that fire influences the transmission of wireless signals uniquely, and consequently it affects the amplitude and phase of the resultant Channel State Information (CSI). Based on this observation, in this paper, we propose a device-free fire detection system, namely Wi-Fire, using commercial WiFi devices. To the best of our knowledge, this is the first work that leverages CSI of radio frequency (RF) signal to detect fire events using existing wireless infrastructure without requiring any additional device. We implement our proposed system on desktop computers equipped with commercial 802.11n network interface cards (NICs). Comprehensive experiments have been conducted for different scenarios in different environments to verify the effectiveness of our proposed system. The results verify that the fire detection accuracy of this training-based system is up to 96.67% on average.