Mining for Empty Rectangles in Large Data Sets

Jeff Edmonds, Jarek Gryz, Dongming Liang, Renee J. Miller

Many data mining approaches focus on the discovery of similar (and
frequent) data values in large data sets.  We present an alternative,
but complementary approach in which we search for empty regions in the
data.  We consider the problem of finding maximal empty rectangles in
large, two dimensional data sets.  We introduce a novel, scalable
algorithm for finding all such rectangles.  The algorithm achieves
this with a single scan over a sorted data set and requires only a
small bounded amount of memory.  We also describe briefly one
potential application of this knowledge to query optimization.