VectorMaton: Efficient Vector Search with Pattern Constraints via an Enhanced Suffix Automaton

Haoxuan Xie, Chuan ShiarXiv 2026 · arXiv

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.

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".

Motivating example: Searching for proteins with structural similarity and specific sequence motifs.

Traditional approaches to this problem typically fall into three categories, each with significant drawbacks:

  1. Pre-filtering: Identifying all sequences matching the pattern before performing a vector search. This becomes a bottleneck for common patterns.
  2. 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.
  3. 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.

Performance comparison of VectorMaton against pre-filtering and post-filtering baselines.
  • Throughput: VectorMaton achieves up to 10x higher Query Per Second (QPS) compared to baselines like pgvector and Elasticsearch at 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

Abstract

Approximate nearest neighbor search (ANNS) has become a cornerstone in modern vector database systems. Given a query vector, ANNS retrieves the closest vectors from a set of base vectors. In real-world applications, vectors are often accompanied by additional information, such as sequences or structured attributes, motivating the need for fine-grained vector search with constraints on this auxiliary data. Existing methods support attribute-based filtering or range-based filtering on categorical and numerical attributes, but they do not support pattern predicates over sequence attributes. In relational databases, predicates such as LIKE and CONTAINS are fundamental operators for filtering records based on substring patterns. As vector databases increasingly adopt SQL-style query interfaces, enabling pattern predicates over sequence attributes (e.g., texts and biological sequences) alongside vector similarity search becomes essential. In this paper, we formulate a novel problem: given a set of vectors each associated with a sequence, retrieve the nearest vectors whose sequences contain a given query pattern. To address this challenge, we propose VectorMaton, an automaton-based index that integrates pattern filtering with efficient vector search, while maintaining an index size comparable to the dataset size. Extensive experiments on real-world datasets demonstrate that VectorMaton consistently outperforms all baselines, achieving up to 10x higher query throughput at the same accuracy and up to 18x reduction in index size.
BibTeX
@misc{xie2026vectormaton,
  author = {Haoxuan Xie and Chuan Shi},
  title = {{VectorMaton: Efficient Vector Search with Pattern Constraints via an Enhanced Suffix Automaton}},
  year = {2026},
  eprint = {2603.01525},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.01525},
  howpublished = {arXiv},
}
Figure