Methods and arrangements for discovering entity types for a set of records. A set of records is input, with each record comprising attributes with associated attribute values. The records are grouped into candidate entity types in view of at least one of: the attribute values of the records, at least one domain ontology and at least one dimension hierarchy. An interestingness measure of each candidate entity type is calculated, via estimating interestingness based on at least one factor selected from the group consisting of: a correlation between attribute values of records, a number of attributes, a log of queries issued to a server, and an average group size for candidate entity types. At least one candidate entity type is validated based on the calculated interestingness measures. Other variants and embodiments are broadly contemplated herein.