Devices and methods for classification of low relevance records in a database are disclosed. A method includes: in response to a request to delete a selected database record, generating a vector representation of the selected record, deleting the selected record in the database, and storing the vector representation of the deleted selected record; in response to the storing the vector representation of the deleted selected record, determining a cluster from which the vector representation has a shortest determined distance, among a plurality of clusters into which a plurality of vector representations of deleted records is partitioned; determining a distance between a record in the database and a nearest cluster among the plurality of clusters into which the plurality of vector representations of deleted records is partitioned; and in response to the record being within a predetermined distance of the nearest cluster, determining that the record is a deletion candidate record.