Mining for empty spaces in large data sets

✍ Scribed by Jeff Edmonds; Jarek Gryz; Dongming Liang; Renée J. Miller

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 166 KB
• Volume: 296
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00738-7

✦ Synopsis

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 ÿnding all maximal empty rectangles in large, two-dimensional data sets. We introduce a novel, scalable algorithm for ÿnding 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 extend the algorithm to ÿnd all maximal empty hyper-rectangles in a multi-dimensional space. We consider the complexity of this search problem and present new bounds on the number of maximal empty hyper-rectangles. We brie y overview experimental results obtained by applying our algorithm to real and synthetic data sets and describe one application of empty-space knowledge to query optimization.