Methods and systems are provided for enhanced data loss prevention. The enhanced data loss prevention may be applied to data that is structured and/or semi-structured data, with the data comprising a plurality of records and a plurality of categories, with each record comprising a plurality of fields, each of which being associated with a different one of the plurality of categories. The enhanced data loss prevention may comprise selecting a subset of records of the data, with the selected subset comprising at least two records having between then one or more records not included in the subset. The fields of the selected subset may be scanned for sensitive information, and a likelihood to contain the sensitive information may be computed for each category based on the scanning. A subset of categories may be selected based on the computed likelihoods, and the sensitive information in the selected subset may be searched.