In the current era of data-intensive applications, the demand for high-performance, cost-effective storage solutions is paramount. This paper introduces a Space-Performance Cost Model for key-value store, designed to guide cost-effective storage configuration decisions. The model quantifies the trade-offs between performance and storage costs, providing a framework for optimizing resource allocation in large-scale data serving environments. Guided by this cost model, we present Tier-Base, a distributed key-value store developed by Ant Group that optimizes total cost by strategically synchronizing data between cache and storage tiers, maximizing resource utilization and effectively handling skewed workloads. To enhance cost-efficiency, TierBase incorporates several optimization techniques, including pre-trained data compression, elastic threading mechanisms, and the utilization of persistent memory. We detail TierBase's architecture, key components, and the implementation of cost optimization strategies. Extensive evaluations using both synthetic benchmarks and real-world workloads demonstrate TierBase's superior cost-effectiveness compared to existing solutions. Furthermore, case studies from Ant Group's production environments showcase TierBase's ability to achieve up to 62% cost reduction in primary scenarios, highlighting its practical impact in large-scale online data serving.

Approximate K Nearest Neighbor (AKNN) search in high-dimensional spaces is a critical yet challenging problem. In AKNN search, distance computation is the core task that dominates the runtime. Existing approaches typically use approx-imate distances to improve computational efficiency, often at the cost of reduced search accuracy. To address this issue, the state-of-the-art method, ADSampling, employs random projections to estimate approximate distances and introduces an additional distance correction process to mitigate accuracy loss. However, ADSampling has limitations in both effectiveness and generality, primarily due to its heavy reliance on random projections for distance approximation and correction. Motivated by this, we leverage data distribution to improve distance approximation via orthogonal projection, thereby ad-dressing the effectiveness limitation of ADSampling; we also adopt a data-driven approach to distance correction, decoupling the correction process from the distance approximation process, thereby overcoming the generality limitation of ADSampling. Ex-tensive experiments demonstrate the superiority and effectiveness of our method. In particular, compared to ADSampling, our method achieves a speedup of 1.6 to 2.1 times on real-world datasets while providing higher accuracy. In addition, our method shows superior performance in Ant Group image search scenarios and has been integrated into their search engine.

Log data is a vital resource for capturing system events and states. With the increasing complexity and widespread adoption of modern software systems and IoT devices, the daily volume of log generation has surged to tens of petabytes, leading to significant collection and storage costs. To address this challenge, lossless log compression has emerged as an effective solution, enabling substantial resource savings without compromising log information. In this paper, we first conduct a characterization study on extensive public log datasets and identify four key observations. Building on these insights, we propose LogLite, a lightweight, plug-and-play, streaming lossless compression algorithm designed to handle both TEXT and JSON logs throughout their life cycle. LogLite requires no predefined rules or pre-training and is inherently adaptable to evolving log structures. Our evaluation shows that, compared to state-of-the-art baselines, LogLite achieves Pareto optimality in most scenarios, delivering an average improvement of up to 67.8% in compression ratio and up to 2.7X in compression speed.

Approximate nearest neighbor search (ANNS) is a fundamental problem in vector databases and AI infrastructures. Recent graph-based ANNS algorithms have achieved high search accuracy with practical efficiency. Despite the advancements, these algorithms still face performance bottlenecks in production, due to the random memory access patterns of graph-based search and the high computational overheads of vector distance. In addition, the performance of a graph-based ANNS algorithm is highly sensitive to parameters, while selecting the optimal parameters is cost-prohibitive, e.g., manual tuning requires repeatedly re-building the index. This paper introduces VSAG , an open-source framework that aims to enhance the in production performance of graph-based ANNS algorithms. VSAG has been deployed at scale in the services of Ant Group, and it incorporates three key optimizations: ( i) efficient memory access : it reduces L3 cache misses with pre-fetching and cache-friendly vector organization; ( ii) automated parameter tuning : it automatically selects performance-optimal parameters without requiring index rebuilding; ( iii) efficient distance computation : it leverages modern hardware, scalar quantization, and smartly switches to low-precision representation to dramatically reduce the distance computation costs. We evaluate VSAG on real-world datasets. The experimental results show that VSAG achieves the state-of-the-art performance and provides up to 4× speedup over HNSWlib (an industry-standard library) while ensuring the same accuracy.

Machine-generated data is rapidly growing and poses challenges for data-intensive systems, especially as the growth of data outpaces the growth of storage space. To cope with the storage issue, compression plays a critical role in storage engines, particularly for data-intensive applications, where a high compression ratio and efficient random access are essential. However, existing compression techniques tend to focus on general-purpose and data block approaches, but overlook the inherent structure of machine-generated data and hence result in low compression ratios or limited lookup efficiency. To address these limitations, we introduce the Pattern-Based Compression (PBC) algorithm, which specifically targets patterns in machine-generated data to achieve Pareto-optimality in most cases. Unlike traditional data block-based methods, PBC compresses data on a per-record basis, facilitating rapid random access. Our experimental evaluation demonstrates that PBC, on average, achieves a compression ratio twice as high as the state-of-the-art techniques while maintaining competitive compression and decompression speeds. We also integrate PBC to a production database system and achieve improvements on both comparison ratio and throughput.

The computation of k-lower envelope is a classical problem and has been very well studied for main memory non-indexed data. In this paper, we study the problem from the database perspective and present the first algorithm which utilizes the presence of the index and achieves access optimality, i.e., it accesses a node of the index only if the correctness of the results cannot be guaranteed without accessing this node. We also demonstrate the applications of k-lower envelope in ranking systems. Let an object be called valuable if it is one of the top-k objects according to at least one linear scoring function. In this paper, we answer the following important questions that may be asked by different users: 1) I am not sure what scoring function I should use, therefore, return me the set of valuable objects so that I can select an object I like the most; 2) How can I modify the attributes (e.g., price) of my product such that it becomes a valuable object; 3) What are the preference functions for which a given object is among the top-k objects. These three questions are formalized and called k-snippet, k-depth contour and reverse top-k query, respectively. We propose a unified framework to solve these queries by utilizing k-lower envelope as a common foundation. Our main algorithm is access optimal for k-snippet and k-lower envelope computation. We also demonstrate its access optimality for the k-depth contour problem when k is smaller than the minimum number of objects in any leaf node of the index structure. Our algorithms outperform state-of-the-art algorithms by more than an order of magnitude in terms of both CPU and I/O cost.

Top-k pairs and top-k objects queries have received significant attention by the research community. In this paper, we present the first approach to answer a broad class of top-k pairs and top-k objects queries over sliding windows. Our framework handles multiple top-k queries and each query is allowed to use a different scoring function, a different value of k, and a different size of the sliding window. Furthermore, the framework allows the users to define arbitrarily complex scoring functions and supports out-of-order data streams. For all the queries that use the same scoring function, we need to maintain only one K-skyband. We present efficient techniques for the K-skyband maintenance and query answering. We conduct a detailed complexity analysis and show that the expected cost of our approach is reasonably close to the lower bound cost. For top-k pairs queries, we demonstrate the efficiency of our approach by comparing it with a specially designed supreme algorithm that assumes the existence of an oracle and meets the lower bound cost. For top-k objects queries, our experimental results demonstrate the superiority of our algorithm over the state-of-the-art algorithm.

A traditional query returns a set of objects that satisfy user defined criteria at the time query was issued. The results are based on the values of objects at query time and may be affected by outliers. Intuitively, an object better meets the user's needs if it persistently satisfies the criteria, i.e., it satisfies the criteria for majority of the time in the past T time units. In this paper, we propose a measure named loyalty that reflects how persistently an object satisfies the criteria. Formally, the loyalty of an object is the total time (in past T time units) it satisfies the query criteria. In this paper, we study top-k loyalty queries over sliding windows that continuously report k objects with the highest loyalties. Each object issues an update when it starts satisfying the criteria or when it stops satisfying the criteria. We show that the lower bound cost of updating the results of a top-k loyalty query is O(logN), for each object update, where N is the number of updates issued in last T time units. We conduct a detailed complexity analysis and show that our proposed algorithm is optimal. Moreover, effective pruning techniques are proposed to improve the efficiency. We experimentally verify the effectiveness of the proposed approach by comparing it with a classic sweep line algorithm.

Top-k pairs queries have received significant attention by the research community. k-closest pairs queries, k-furthest pairs queries and their variants are among the most well studied special cases of the top-k pairs queries. In this paper, we present the first approach to answer a broad class of top-k pairs queries over sliding windows. Our framework handles multiple top-k pairs queries and each query is allowed to use a different scoring function, a different value of k and a different size of the sliding window. Although the number of possible pairs in the sliding window is quadratic to the number of objects N in the sliding window, we efficiently answer the top-k pairs query by maintaining a small subset of pairs called K-sky band which is expected to consist of O(K log(N/K)) pairs. For all the queries that use the same scoring function, we need to maintain only one K-sky band. We present efficient techniques for the K-sky band maintenance and query answering. We conduct a detailed complexity analysis and show that the expected cost of our approach is reasonably close to the lower bound cost. We experimentally verify this by comparing our approach with a specially designed supreme algorithm that assumes the existence of an oracle and meets the lower bound cost.

This paper proposes a novel window operator, pattern-based window, for data stream processing. By using pattern-based windows, user-specified complex events can be extracted from data streams under the framework of continuous query language (CQL), which integrates the current data stream processing and event stream processing. In this paper, the pattern-based window is formally defined and the query language of pattern-based windows is designed. A simple pattern matching algorithm is introduced to show logical expression of the query language. We also give simple examples to show the usage of the query language by using pattern-based windows.