GAS: A Lightweight Framework for Filtered Search over Wide-Table Vectors
TL;DR
Graph with Adaptive Shortcuts (GAS), a framework that leverages historical query logs to build lightweight auxiliary structures, enhancing search efficiency over a single base graph with minimal overhead, and consistently outperforms existing general indexes in wide-table scenarios.
Abstract
Wide-table vectors, where each embedding is linked with numerous structured attributes, are prevalent in applications such as autonomous driving and multimodal data processing for large-model training. Efficiently retrieving semantically similar vectors under attribute filters is crucial for these tasks, a problem addressed by Filtered Approximate Nearest Neighbor Search (FANNS). Recent approaches follow two paradigms: (1) building per-attribute dedicated indexes that integrate attribute information, which incurs prohibitive build time and storage in wide-table settings; or (2) building an attribute-agnostic general index and applying predicates at query time, which often degrades search efficiency. Consequently, neither paradigm adequately supports wide-table scenarios. We aim to achieve good query performance with low upfront cost by incorporating information from many attributes into a single graph index, avoiding prohibitive overhead. Our key observation is that graph-traversal information from past queries can be reused to optimize future queries with the same filter attribute. Based on this insight, we devise Graph with Adaptive Shortcuts (GAS), a framework that leverages historical query logs to build lightweight auxiliary structures, enhancing search efficiency over a single base graph with minimal overhead. Extensive experiments on real-world datasets show that GAS consistently outperforms existing general indexes in wide-table scenarios, achieving up to 42.1× speedup on datasets with thousands of structured attributes.