Log-Structured-Merge-tree (LSM-tree) has been extensively adopted because of its exceptional write efficiency and high space utilization. Compaction is invoked periodically in LSM-tree based key-value(LSM KV) systems to maintain good system performance. As the size of LSM-KV grows, large-scale compaction is now frequently seen. Compaction throughput significantly degrades with larger inputs, leading to frequent write stalls and decrement in overall write throughput. This paper proposes STEM, a stream-based compaction framework with FPGA to address this issue. A clean-cut algorithm is introduced to enable streaming-based compaction for large-scale data. With a multi-unit pipeline and dynamic pipeline schedule, STEM can handle large-scale compaction tasks efficiently. Based on the experiment result, the compaction throughput of STEM can achieve$27\times$on average and up to$35\times$improvement compared with the current RocksDB compaction,$2.09\times$to$2.27\times$improvement compared with the state-of-the-art FPGA accelerator.

Deep-learning-based compressor has received interests recently due to much improved compression ratio. However, modern approaches suffer from long execution time. To ease this problem, this paper targets on cutting down the execution time of deep-learning-based compressors. Building history-dependencies sequentially (e.g., recurrent neural networks) is responsible for long inference latency. Instead, we introduce transformer into deep learning compressors to build history-dependencies in parallel. However, existing transformer is too heavy in computation and incompatible to compression tasks.

Recent works on learned index open a new direction for the indexing field. The key insight of the learned index is to approximate the mapping between keys and positions with piece-wise linear functions. Such methods require partitioning key space for a better approximation. Although lots of heuristics are proposed to improve the approximation quality, the bottleneck is that the segmentation overheads could hinder the overall performance. This paper tackles the approximation problem by applying a distribution transformation to the keys before constructing the learned index. A two-stage Normalizing-Flow-based Learned index framework (NFL) is proposed, which first transforms the original complex key distribution into a near-uniform distribution, then builds a learned index leveraging the transformed keys. For effective distribution transformation, we propose a Numerical Normalizing Flow (Numerical NF). Based on the characteristics of the transformed keys, we propose a robust After-Flow Learned Index (AFLI). To validate the performance, comprehensive evaluations are conducted on both synthetic and real-world workloads, which shows that the proposed NFL produces the highest throughput and the lowest tail latency compared to the state-of-the-art learned indexes.

In this work, we propose a GPU-accelerated algorithm for frequent pattern(FP) mining without candidate generation. We observe that the existing FP-growth algorithm has critical characteristics unsuitable for GPU, including the tree data structure, deep recursion and heavy dynamic memory allocations. By utilizing iterative execution and collectively allocating memory on GPU, our proposed method significantly reduce the latency caused by large memory allocations of original FP-growth. Experiment results show that our solution outperforms baselines, including sequential FP-growth with CPU only and existing GPU-accelerated Apriori and FP-growth, on various data sets with a significant speedup, from several times to hundred times.

In this paper, we propose a method to realize the Barabási-Albert (BA) model for generating large scale-free networks with preferential attachment. To our knowledge, the existing implementations of the BA model are still not very efficient because they failed to manage the temporary data of the network generating process properly by ignoring the inherent power law degree distribution property. To address this problem, we propose to leverage data structures including a prefix sum max heap and index arrays, which can competently manage nodes with different amount of connections. The proposed method is also friendly to the computing system with non-volatile memory (NVM) as main memory. Reducing long-latency write operations is the key to improve the efficiency of NVM, while the proposed method can ultimately save not only read operations but also significant amount of writes. We compare our proposed method with the baseline methods by generating networks of size from 102nodes to 108nodes. Experiment results show that the proposed method can save up to 50% of write counts. Furthermore, when using the phase change memory, a new byte-addressable non-volatile memory, as main memory, the proposed method can be almost two times faster.

For many applications with spatial data management such as Geographic Information Systems (GIS), block-oriented access over flash memory could introduce a significant number of node updates. Such node updates could result in a large number of out-place updates and garbage collection over flash memory and damage its reliability. In this paper, we propose a very different approach which could efficiently handle fine-grained updates due to R-tree index access of spatial data over flash memory. The implementation is done directly over the flash translation layer (FTL) without any modifications to existing application systems. The feasibility of the proposed methodology is demonstrated with significant improvement on system performance, overheads on flash-memory management, and energy dissipation.

An important mobile application is to provide users information in a real-time fashion over a mobile network, such asthose for news updates and traffic information. The contents of such information are often highly dynamic, and its validity maychange with time rapidly. It is the best benefit of users if the most recent data can be received by users on time. Informationupdates, which capture the most recent status of interested objects in the external environment, must be done continuously andin a real-time fashion to refresh the values of the corresponding data items in the information servers. However, mobilenetworks are often unreliable, and the available bandwidth is usually very limited. If the rate of information update is too high,the total system workload will be very heavy, and, as a result, the completion times of updates and the validity of many dataitems might be seriously affected. On the other hand, if the update rate is low, the uncertainty level of data validity might behigh, and the external consistency cannot be maintained [1]. In addition to the unreliable mobile network, the mobility ofclients complicates the design of a mobile information system. Queries from mobile clients could have some location-dependent properties. For example, the result of a query might depend on the current location of the originating client. Timingconstraints are often implicitly associated with the processing of queries.In this paper, we introduce a system prototype called

The paper proposes methodologies to control the access of B-tree-indexed data in a batch and real time fashion. Algorithms are proposed to insert, query, delete, and rebalance B-tree-indexed data based on non real time algorithms (P.M. Kerttu et al., 1996) and the idea of priority inheritance (L. Sha et al., 1990). We propose methodologies to reduce the number of disk I/Os to improve the system performance without introducing more priority inversion. The performance of our methodologies was evaluated by a series of experiments, for which we have some encouraging results.