Accelerating Ephemeral Approximate Nearest Neighbor Search by Progressive Index Construction
作者: Minhui Xie, Enrui Zhao, Yaxin Ma, Puqing Wu, Baotong Lu, Yuanhui Luo, Yongqiang Xiong, Jing Wang, Yunpeng Chai
2026-03摘要: 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.