Working Papers Series
2026-03
One-Shot Traversal for Low-Latency SSD-based Tree Index
By: Yiheng Tong, Minhui Xie, Yuanhui Luo, Jing Liu, Ran Shu, Yongqiang Xiong, Yunpeng Chai
Abstract: SSD-based tree indexes (e.g., B+tree) have been widely adoptted in storage and database systems. Driven by modern high-performance SSDs, much prior work has focused on improving their overall throughput. However, when it comes to latency, such approaches still suffer from the inherent bottleneck of pointer chasing during index traversals, so query latency does not benefit directly from faster SSDs. In this paper, we propose Shortcut, a lightweight solution that transforms the conventional wisdom of inherent access dependency into one-shot traversal, thereby achieving low query latency.
Our key idea is to exploit intra-query parallelism by training per-level learned indexes as B+tree companion to predict the traversal path in advance, and issuing multiple concurrent I/O requests to prefetch all target nodes in a one-shot manner. The main challenge we deal with is the excessive memory overhead of the additional learned index, which originates not from the machine learning (ML) models, but from two essential structures in it: the key array (for last-mile search) and the value array (termed “mapping array”, for mapping model predictions to arbitrary node locations in the file). Shortcut eliminates two arrays through two techniques: Keyless Learning Method and Phantom Mapping Mechanism, and achieves nearly-zero memory overhead (∼0.6%). Evaluations on YCSB and TPC-C show that Shortcut can reduce end-toend query latency by 26.2% to 64.8%.
2026-03
Constructing Parameter-Optimal Graph ANNS Index with GArena
By: Puqing Wu, Minhui Xie, Hao Guo, Jie Yin, Sen Yang, Youyou Lu, Yunpeng Chai
Abstract: Graph-based Approximate Nearest Neighbor Search (GANNS) delivers exceptional query performance compared to other algorithms, but this efficiency comes at the cost of significantly longer construction time. Because index construction parameters can alter final query throughput by up to an order of magnitude, identifying the parameter-optimal configuration is essential for real-world deployments. Yet, this process is notoriously challenging: traditional tuning methods can take days or weeks due to the need for repeated, full graph rebuilds.
This paper introduces GArena, a GANNS constructor that accelerates optimal construct parameter search. Our key observation is that while different parameter settings yield distinct graph topologies, their construction processes exhibit over 70% redundancy in distance calculations. Though a naive
distance cache can eliminate this redundancy, it incurs prohibitive memory overhead (dozens of TB). Instead, GArena redesigns the tuning paradigm by launching multiple parallel graphs with different configurations and aligning their distance computation trajectories, thereby greatly enhancing the distance cache’s temporal locality. GArena can bound the cache size to only a few MB (fully resident in CPU cache). GArena also introduces a performance-potentialguided pruner to discard unpromising configurations early on small subsets. Evaluation shows that GArena can dramatically shrink the tuning process from a day down to minutes, while consistently identifying the optimal configuration.
2026-03
Accelerating Ephemeral Approximate Nearest Neighbor Search by Progressive Index Construction
By: Minhui Xie, Enrui Zhao, Yaxin Ma, Puqing Wu, Baotong Lu, Yuanhui Luo, Yongqiang Xiong, Jing Wang, Yunpeng Chai
Abstract: Emerging applications like AI chatbots, code assistants, and agentic workflows have created a growing need for ephemeral Approximate Nearest Neighbor Search (ANNS), where an ANN index must be constructed online over pre-unknown, ad-hoc, short-lived datasets. Traditional ANNS methods, designed for offline index construction on pre-known datasets, are ill-suited for such scenario: the monolithic, upfront index construction process imposes substantial latency on the user’s critical path, degrading the interactive experience.
This paper presents FleetANN, a system that accelerates ephemeral ANNS by pioneering a progressive index construction paradigm. FleetANN logically partitions the dataset into an already-indexed component (I-component) and an unindexed brute-force component (BF-component), separated by a conceptual cursor. In the background, FleetANN continuously advances this cursor by migrating vectors from BF-component into I-component, incrementally building the index. In the foreground, FleetANN can serve user queries immediately via a hybrid retrieval strategy, ensuring theoretically guaranteed recalls even with a partially constructed index. To mitigate the initial high cost of brute-force search, FleetANN introduces a history-guided pruning technique that exploits distance information from past queries to avoid unnecessary computations. Evaluation shows that FleetANN can avoid costly initial construction stall (up to hundreds of seconds) while ultimately achieving the same or even better query performance as a full ANNS index.
2026-03
Joint Auction in the Online Advertising Market
By: Zhen Zhang、Weian Li、Yahui Lei、Bingzhe Wang、Zhicheng Zhang、Qi Qi、Qiang Liu、Xingxing Wang
Abstract: Online advertising is a primary source of income for e-commerce platforms. In the current advertising pattern, the oriented targets are the online store owners who are willing to pay extra fees to enhance the position of their stores. On the other hand, brand suppliers are also desirable to advertise their products in stores to boost brand sales. However, the currently used advertising mode cannot satisfy the demand of both stores and brand suppliers simultaneously. To address this, we innovatively propose a joint advertising model termed “Joint Auction”, allowing brand suppliers and stores to collaboratively bid for advertising slots, catering to both their needs. However, conventional advertising auction mechanisms are not suitable for this novel scenario. In this paper, we propose JRegNet, a neural network architecture for the optimal joint auction design, to generate mechanisms that can achieve the
optimal revenue and guarantee (near-)dominant strategy incentive compatibility and individual rationality. Finally, multiple experiments are conducted on synthetic and real data to demonstrate that our proposed joint auction significantly improves platform’s revenue compared to the known baselines.