Scalable Alignment Kernels via Space-Efficient Feature Maps

Yasuo Tabei, Yoshihiro Yamanishi, Rasmus Pagh

Abstract

Alignment kernels are highly accurate for sequence classification but suffer from quadratic scaling and high memory requirements for feature maps. We present SFMEDM, a method combining Edit Sensitive Parsing (ESP) with space-efficient Random Fourier Features (RFFs). By utilizing $t$-wise independent hash functions, SFMEDM reduces memory complexity from $O(dD)$ to $O(d)$, enabling the classification of millions of strings on standard hardware where previous methods required terabytes of RAM.

Introduction

The challenge of sequence classification is central to bioinformatics, natural language processing, and cheminformatics. Alignment kernels, which compute similarity based on optimal structural alignments, provide superior accuracy but are hindered by $O(N^2)$ computational complexity. Approximation techniques like Random Fourier Features (RFFs) map inputs to a $D$-dimensional space to enable linear-time learning. However, for strings, the input dimension $d$ (often the size of a k-mer dictionary) is extremely large. Storing the $d \times D$ projection matrix becomes the primary bottleneck, often requiring terabytes of RAM for large $D$. This "memory wall" has effectively barred alignment kernels from the era of Big Data.

Methodology

The authors introduce SFMEDM (Space-efficient Feature Maps for Edit Distance with Moves), which uses a two-step approach to bridge the gap between discrete sequence data and continuous kernel methods.

1. Edit Sensitive Parsing (ESP)

Instead of standard edit distance, which is computationally expensive, SFMEDM uses ESP to embed strings into a high-dimensional integer space. ESP is unique because it approximates "edit distance with moves"—meaning it accounts for substrings being moved around, not just single-character changes. It builds a hierarchical representation where similar substrings are mapped to similar nodes in a tree.

Hierarchical structure of Edit Sensitive Parsing (ESP) for string embedding.

2. Space-Efficient Feature Maps (SFMs)

The core innovation is the realization that the theoretical guarantees of RFFs hold even if the "randomness" is generated by simple hash functions. Standard RFFs require storing a massive matrix of random numbers. By using 2-wise independent hash functions, SFMEDM generates the necessary random values on-the-fly during computation. This collapses the memory requirement from $O(dD)$ down to $O(d)$, making it independent of the output dimension $D$.

Experimental Results

The authors evaluated SFMEDM on five diverse, large-scale datasets, including Protein/DNA sequences, Amazon reviews (Music/Sports), and a massive "Compound" dataset containing over 1.3 million bioactive compounds.

Memory and time efficiency of SFMEDM compared to standard feature maps across multiple datasets.

Extreme Memory Savings

On the "Sports" dataset, a standard feature map (FMEDM) would have required 1.1 Terabytes of RAM to achieve high accuracy. SFMEDM achieved the same results using only 280 Megabytes. As shown in the figures, SFMEDM's memory usage remains constant even as the projection dimension $D$ increases, whereas competing methods scale linearly.

Superior Scalability and Accuracy

SFMEDM successfully processed the 1.3-million-string "Compound" dataset in about 9 hours. Traditional kernels like GAK or LAK either timed out or crashed due to memory limits on much smaller datasets. In terms of AUC (Area Under the Curve), SFMEDM consistently outperformed other scalable approximations like D2KE and CGK. Its accuracy improved as the dimension $D$ increased—a luxury made possible only by its space efficiency.

Conclusion

SFMEDM breaks the memory wall for alignment kernels, allowing high-accuracy string classification at the scale of millions of sequences. By rethinking how randomness is stored and utilized, the authors provide a scalable bridge between discrete sequence data and continuous kernel methods. Future work may extend this approach to more complex bioinformatics tasks and natural language processing applications where string similarity remains a bottleneck.

Summary updated

BibTeX
@inproceedings{tabei2019scalable,
  author = {Yasuo Tabei and Yoshihiro Yamanishi and Rasmus Pagh},
  title = {{Scalable Alignment Kernels via Space-Efficient Feature Maps}},
  booktitle = {ICDM},
  year = {2019},
  doi = {10.1109/icdm.2019.00166},
}
Figure