New Feature Selection Methods Boost MinHash Classifiers Across Five Real-World Tasks

MinHash has become a workhorse of large-scale data analysis because it can estimate the similarity between enormous datasets with remarkable storage and computational efficiency. The sketching algorithm generates independent hash-based features that act as unbiased estimators of the Jaccard similarity, allowing systems to compare documents, files and biological sequences without ever holding the full objects in memory. Yet those same properties have long posed a problem for machine learning practitioners: the nominal, independent nature of MinHash features defeats many conventional feature selection methods, leaving classifiers to digest every hashed attribute even when only a fraction carries useful signal.

A new study by Tomer Panker and Nir Nissim, published in Knowledge and Information Systems, presents what the authors describe as the first systematic exploration of feature selection strategies tailored specifically to MinHash-based classifiers. The researchers propose four methods: a statistical approach, an inter-class dissimilarity method, an intra-class similarity method, and a hybrid approach that combines them. Each is explicitly designed to exploit the nominal and independent character of MinHash features rather than assuming the continuous, correlated structure that traditional selection techniques expect.

The paper also introduces a novel feature aggregation strategy that combines the MinHash outputs of multiple sketches to strengthen classifier performance. The authors are candid about a theoretical trade-off: applying feature selection to MinHash-derived datasets does not preserve the Jaccard similarity that the sketches were designed to estimate. Their response is pragmatic. Rather than maintaining exact similarity properties, their sole objective is to improve machine-learning classifier performance through an intelligent selection of the most beneficial MinHash-based features, a direction they describe as relatively underexplored in the existing literature.

To test the approach, the team evaluated the methods on five diverse real-world tasks: unknown malware detection in Linux volatile memory, COVID-19 diagnosis from chest X-rays, virus DNA categorization, fake news detection, and malicious PDF identification. The evaluation showed that the proposed methods generally outperform widely used feature selection techniques for nominal data, with statistically significant improvements observed in the majority of experimental settings. Those gains were associated with improved generalization performance, reduced model complexity, and lower storage requirements, meaning the selected feature subsets made models that generalize better while remaining smaller and cheaper to store.

The authors caution that the improvements are not uniform across all datasets and configurations, indicating sensitivity to dataset characteristics and classifier choice. The scope of the work is also deliberately bounded: the objective is to enhance the performance of MinHash-based classifiers for a given MinHash dataset, not to identify the optimal classifier for a given learning task. The focus, they write, lies in improving the applicability and effectiveness of existing learning algorithms when they leverage MinHash-derived features, rather than in pursuing the theoretical upper bound of classification performance.

Within that scope, the experimental results show that the methods improve classifiers’ generalization capabilities under the MinHash hyperparameter settings evaluated across the five domains. The authors further report that similar improvements were observed under alternative sketch configurations tested in a second experiment, suggesting the benefit is not an artifact of one particular parameterization of the sketching process.

The practical significance lies in the tension the paper identifies. MinHash features are attractive precisely because they are cheap to produce and store at scale, but their independence and nominal structure mean that standard feature selection tools, which often rely on distributional assumptions or correlation measures, lose their effectiveness. By designing selection criteria that respect the sketch’s statistical properties, the new methods aim to keep the storage and computational advantages of MinHash while trimming away hashed features that contribute little to classification decisions.

The five evaluation domains span markedly different data types, from volatile memory images and radiographs to genomic sequences and text documents, giving the results breadth across application areas. The reported pattern of statistically significant gains in most, but not all, settings provides an honest picture of where the approach helps and where dataset characteristics or classifier choice may limit its benefit. For practitioners deploying MinHash pipelines in security screening, medical imaging triage, or content verification, the study offers a documented route to smaller models with better generalization under the tested configurations.

The work positions itself as a step toward making sketch-based learning more efficient rather than a claim of universal superiority. By framing the contribution as improving existing algorithms on MinHash-derived features, the authors leave open the broader question of optimal classification performance for any given task. What the evidence supports is narrower but concrete: four feature selection methods and an aggregation strategy that, across five real-world tasks and the evaluated sketch settings, delivered statistically significant improvements in the majority of experiments while reducing model complexity and storage demands.

Subject of Research: Feature selection strategies designed for MinHash-based classifiers to improve performance and generalization

Article Title: Feature selection strategies for improving MinHash-based classifiers’ performance and generalization

Article References: Panker, T., & Nissim, N. (2026). Feature selection strategies for improving MinHash-based classifiers’ performance and generalization. Knowledge and Information Systems, 68(1), Article 303. https://doi.org/10.1007/s10115-026-02922-y

Image Credits: AI Generated

DOI: 10.1007/s10115-026-02922-y

Keywords: MinHash, feature selection, machine learning, Jaccard similarity, malware detection, COVID-19 diagnosis, fake news detection, virus DNA categorization, malicious PDF detection, data sketching, classifier generalization, Feature