Scaling manifold learning through sparse matrix reformulation

Manifold-based re-ranking is an established class of post-retrieval refinement algorithms, with extensive application in Content-Based Image Retrieval (CBIR). Despite its effectiveness, its adoption is limited by inherent computational and memory demands. These methods typically rely on dense N x N similarity matrices (where N is the dataset size), imposing an O(N^2) memory footprint that leads to out-of-memory (OOM) failures on commodity hardware for large-scale datasets. This hardware constraint restricts state-of-the-art re-ranking to specialized computing facilities, raising significant deployment barriers. To address this limitation, we present a sparse linear algebra reformulation that substantially reduces the memory overhead of manifold-based re-ranking. We map the update rules onto three primitives: Sparse General Matrix-Matrix Multiplication (SpGEMM), the Hadamard product, and sorted row merging. By exploiting the inherent sparsity of ranked lists via the Compressed Sparse Row (CSR) format, we reduce spatial complexity from O(N^2) to O(NL), without approximating the underlying manifold calculations. To achieve this in practice without intermediate density explosion, we develop: (1) a custom pruning kernel that integrates top-L selection directly into the accumulation phase; (2) a row-split parallel construction strategy that eliminates synchronization overhead; and (3) a specialized memory allocator using Transparent Huge Pages and cache-line padding, designed to reduce TLB pressure and false sharing on multi-core architectures. We validate this reformulation on two representative algorithms from the Unsupervised Distance Learning Framework (UDLF): Cartesian Product Re-ranking (CPRR) and Local Hypergraph Re-ranking (LHRR). This validation demonstrates that the sparse reformulation enables execution on a consumer 8 GB laptop for a dataset of 160,000 images, while a dense representation would require approximately 102 GB of RAM. For the most complex algorithm evaluated, peak memory consumption remains approximately 256 MB with L = 400. On high-memory servers, the reduction in total instructions yields speedups of up to 2.4x on larger datasets, confirming that the approach does not reduce performance relative to the dense baseline on large-scale datasets. Overall, the reformulation transforms spatial complexity into a tunable metric strictly bounded by the list length L and neighborhood size K, decoupling the memory footprint from the total dataset size.

Abstract (portuguese)

O re-ranqueamento baseado em variedades é uma classe consolidada de algoritmos de refinamento pós-recuperação, com ampla aplicação na Recuperação de Imagens Baseada em Conteúdo (CBIR). Apesar de sua eficácia, sua adoção é limitada pelas demandas computacionais e de memória intrínsecas. Esses métodos dependem tipicamente de matrizes de similaridade densas N × N (onde N é o tamanho do dataset), impondo um footprint de memória O(N2) que resulta em falhas por insuficiência de memória (Out-of-Memory - OOM) em hardware de consumo para datasets de grande escala. Essa limitação de hardware restringe o re-ranqueamento no estado da arte a infraestruturas de computação especializadas, criando barreiras significativas de implantação. Para contornar essa limitação, apresenta-se uma reformulação em álgebra linear esparsa que reduz substancialmente o overhead de memória do re-ranqueamento baseado em variedades. Mapeiam-se as regras de atualização em três primitivas: Multiplicação Matriz-Matriz Geral Esparsa (SpGEMM), o produto de Hadamard e a intercalação ordenada de linhas. Ao explorar a esparsidade intrínseca das listas ranqueadas por meio do formato Compressed Sparse Row (CSR), reduz-se a complexidade espacial de O(N2) para O(NL), sem realizar aproximações nos cálculos da variedade subjacente. Para alcançar esse resultado na prática sem a explosão intermediária de densidade, desenvolveu-se: (1) um kernel de poda customizado que integra a seleção dos top-L elementos diretamente na fase de acumulação; (2) uma estratégia de construção paralela com divisão por linhas que elimina o overhead de sincronização; e (3) um alocador de memória especializado utilizando Transparent Huge Pages e preenchimento de linhas de cache, projetado para reduzir a pressão no TLB e o falso compartilhamento em arquiteturas multi-core. Valida-se essa reformulação em dois algoritmos representativos do Unsupervised Distance Learning Framework (UDLF): o Cartesian Product Re-ranking (CPRR) e o Local Hypergraph Re-ranking (LHRR). Essa validação demonstra que a reformulação esparsa viabiliza a execução em um laptop de consumo de 8 GB para um dataset de 160.000 imagens, enquanto a representação densa exigiria aproximadamente 102 GB de RAM. Para o algoritmo mais complexo avaliado, o consumo de memória em pico permanece em aproximadamente 256 MB com L = 400. Em servidores de alta memória, a redução no total de instruções gera speedups de até 2.4× em datasets maiores, confirmando que a abordagem não reduz o desempenho em relação ao baseline denso em datasets de grande escala. No geral, a reformulação transforma a complexidade espacial em uma métrica ajustável estritamente limitada pelo comprimento da lista L e pelo tamanho da vizinhança K, desacoplando o footprint de memória do tamanho total do dataset.

Keywords

High performance computing , Information retrieval , Computer memory system , Matrices , Parallel algorithms , Computação de alto desempenho , Recuperação da informação , Sistemas de memoria de computadores , Matrizes (Matematica) , Algorítmos paralelos

Language

English

Citation

BOCCES, André Tomitan. Scaling manifold learning through sparse matrix reformulation. 2026. Dissertação (Mestrado em Ciência da Computação) – Instituto de Geociências e Ciências Exatas, Universidade Estadual Paulista (UNESP), Rio Claro, 2026.