Approximate nearest neighbor search (ANNS) is a widely used technique in data retrieval, yet its performance is often compromised by the presence of outliers, which can significantly distort the indexing structure and retrieval results. To address this issue, we propose BraveANN, a memory-disk hybrid vector indexing and search system designed to improve robustness against outliers while maintaining low latency. The core of BraveANN is our newly proposed clustering approach, RKM, which utilizes exponential tilting to perform robust k-means clustering. While RKM improves outlier robustness by positioning centroids further away from outliers, it introduces challenges of speed and imbalance in index construction. To mitigate these issues, we propose an accelerated algorithm, FastRKM, and a balanced algorithm, BalanceRKM, which enhance BraveANN by speeding up index construction and reducing latency. Our experimental results consistently demonstrate that our method outperforms SOTA methods in both effectiveness and efficiency across eight real-world datasets and six metrics. Specifically, on billion-scale datasets, BraveANN achieves up to a 3.14-5.48% improvement in recall compared to other memory-disk hybrid methods. Moreover, as the proportion of outliers increases, BraveANN exhibits a slower decline in recall, highlighting its robustness. Compared to memory-based methods, BraveANN significantly reduces memory usage while ensuring high recall and low latency.
