FedVS: Towards Federated Vector Similarity Search with Filters

Vectors are used to represent unstructured data with their embeddings and associated attributes. Similarity search over large-scale vector datasets has gained significant interest from both industry and academia. It aims to identify the k nearest neighbors to a query object from vectors that satisfy a given attribute filter constraint. Despite its popularity, most solutions focus on single-sourced data and overlook the need for vector retrieval across federated datasets. To fill this gap, we introduce a new problem, federated vector similarity search with filters, which enables privacy-preserving vector retrieval over multi-sourced data held by mutually untrusted providers. While some solutions can be adapted, they struggle with low recall, excessive search latency, or high communication cost. To address these challenges, we propose FedVS, a privacy-preserving framework enhanced with indexing and pruning based on Trusted Execution Environment (TEE). We also provide a comprehensive theoretical analysis, including complexity, security, and approximation guarantees for recall. Moreover, we deploy our solution over real-world vector databases and conduct extensive experiments. The results demonstrate that our solution outperforms state-of-the-art methods in both effectiveness and efficiency.