Abstract
Approximate nearest neighbor search (ANNS) is a fundamental component of modern vector databases. However, real-world applications often require filtering results based on sequence patterns (e.g., specific amino acid motifs or code substrings) alongside vector similarity. Existing methods like pre-filtering or post-filtering often suffer from poor performance or low recall. We introduce VectorMaton, an automaton-based index that integrates pattern filtering with efficient vector search. By leveraging an Enhanced Suffix Automaton (ESAM) to map pattern equivalence classes to vector indices, VectorMaton achieves up to 10x higher query throughput and an 18x reduction in index size compared to state-of-the-art baselines.
Introduction: The Challenge of Pattern-Constrained Search
In many domains, vector similarity alone is insufficient. For instance, a biological scientist might seek proteins structurally similar to a query vector $v_q$ but restricted to those containing a specific motif like "AAA".
Traditional approaches to this problem typically fall into three categories, each with significant drawbacks:
- Pre-filtering: Identifying all sequences matching the pattern before performing a vector search. This becomes a bottleneck for common patterns.
- Post-filtering: Performing a global vector search and then filtering results. This often leads to poor recall if the desired pattern is rare among the top similarity matches.
- Brute-force Indexing: Building a separate index for every possible substring, which leads to a prohibitive $O(m^2)$ space complexity.
VectorMaton: An Enhanced Suffix Automaton Approach
VectorMaton addresses these limitations by combining an Enhanced Suffix Automaton (ESAM) with HNSW (Hierarchical Navigable Small World) graphs.
Core Innovation: ESAM and Equivalence Classes
A standard Suffix Automaton compactly represents all substrings of a text. VectorMaton enhances this structure by mapping automaton states to sets of vector IDs. The key insight is the use of equivalence classes: many distinct substrings appear in the same set of documents. By indexing these unique classes rather than every individual substring, VectorMaton significantly reduces redundancy.
Hybrid Indexing Strategies
To maintain a manageable index size, VectorMaton employs two primary strategies:
- Index Reuse: When the results of one pattern are a subset of another, the system "inherits" the larger graph, storing only the incremental differences.
- Skip-build: For patterns with very low selectivity (matching few sequences), the system avoids building a complex HNSW graph and instead utilizes a fast brute-force scan.
Experimental Evaluation
The authors evaluated VectorMaton across six diverse datasets, including biological sequences (SwissProt), code snippets (CodeSearchNet), and text embeddings (ArXiv, Spam).
Key Results
VectorMaton consistently outperforms traditional filtering methods across various pattern lengths and selectivity levels.
- Throughput: VectorMaton achieves up to 10x higher Query Per Second (QPS) compared to baselines like
pgvectorandElasticsearchat comparable accuracy levels. - Space Efficiency: By leveraging equivalence classes and index reuse, VectorMaton reduces index size by up to 18x compared to naive substring indexing.
- Scalability: On the massive SwissProt dataset, VectorMaton was the only index-based method capable of construction within standard memory limits, demonstrating its viability for large-scale production environments.
Conclusion and Future Directions
VectorMaton represents a significant step forward in bringing complex substring search capabilities to vector databases. By integrating the filter directly into the index structure via an enhanced automaton, it resolves the long-standing trade-off between search speed and filtering accuracy. Future work will focus on improving support for high-velocity dynamic updates and refining garbage collection for deleted items to maintain long-term index health.
Summary updated