1. A selectivity estimation system, comprising: a user interface component that obtains at least one search query; and a query component that estimates the number of data incidents in a data store that resemble the search query based at least in part on a pre-specified similarity function, and criteria defined by the search query.