  We present the first algorithm for finding holes in high dimensional data
that runs in polynomial time with respect to the number of dimensions. Previous
algorithms are exponential. Finding large empty rectangles or boxes in a set of
points in 2D and 3D space has been well studied. Efficient algorithms exist to
identify the empty regions in these low-dimensional spaces. Unfortunately such
efficiency is lacking in higher dimensions where the problem has been shown to
be NP-complete when the dimensions are included in the input. Applications for
algorithms that find large empty spaces include big data analysis, recommender
systems, automated knowledge discovery, and query optimization. Our Monte
Carlo-based algorithm discovers interesting maximal empty hyper-rectangles in
cases where dimensionality and input size would otherwise make analysis
impractical. The run-time is polynomial in the size of the input and the number
of dimensions. We apply the algorithm on a 39-dimensional data set for protein
structures and discover interesting properties that we think could not be
inferred otherwise.
