A storage device includes a memory and a processor. The processor is configured to store data items for a host in respective logical addresses, to identify a first subset of the logical addresses as frequently-accessed logical addresses and a second subset of the logical addresses as rarely-accessed logical addresses, to manage the frequently-accessed logical addresses separately from the rarely-accessed logical addresses, to receive from the host an indication of one or more logical addresses, which are used for storing data that is identified by the host as having been deleted by a user, and to add the logical addresses indicated by the host to the rarely-accessed logical addresses.