Incremental all pairs similarity search for varying similarity thresholds
Amit C. Awekar, Nagiza F. Samatova, Paul Breimyer · 2009
All Pairs Similarity Search (APSS) is a ubiquitous problem in many data mining applications and involves finding all pairs of records with similarity scores above a specified threshold. In this paper, we introduce the problem of Incremental All Pairs Similarity Search (IAPSS), where APSS is performed multiple times over the same dataset by varying the similarity threshold. To the best of our knowledge, this is the first work that addresses the IAPSS problem. All existing solutions for APSS perform redundant computations by invoking APSS independently for each threshold value.