In this paper, we propose a generalization of the MDL
principle, called GMDL, and show that GMDL leads to fewer regions
than MDL, and hence more concise ``answers'' returned to the user.
The key idea is that a region may
contain ``don't care'' cells (up to a global maximum), if these
``don't care'' cells help to form bigger summary regions, leading
to a more concise overall summary.  We study the problem of generating
minimal region descriptions under the GMDL principle for two
different scenarios. In the first, all dimensions of the data space
are spatial. In the second scenario, all dimensions are categorical
and organized in hierarchies. We propose region finding
algorithms for both scenarios and evaluate their run time and
compression performance using detailed experimentation.
Our results show the effectiveness of the GMDL principle and
the proposed algorithms.