Searching for Maximal Holes in Databases

I’ll be giving a presentation, open to the public, tomorrow on my research.

Here is my abstract:

The problem of finding maximal empty rectangles in a set of points in 2D and 3D space has been well studied, and efficient algorithms exist to identify maximal rectangles in 2D space. 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. We compare existing methods and suggest a novel technique to discover interesting maximal empty hyper-rectangles in cases where dimensionality and input size would otherwise make analysis impractical. Applications include big data analysis, recommender systems, automatic knowledge discovery, and query optimization.
Keywords: Maximal Empty Rectangle, Maximal Cuboid, Big Data

Curse of Dimentionality

I’ve been too busy to update this blog but I have an upcoming presentation on my research about holes in multi dimensional data where I plan to present a new algorithm that can quickly generate useful results.

One of the big problems is that (until now) there are no algorithms that scale well for finding empty hyper-rectangles.

This is related to something called “The curse of dimensionality”.

My wife is finishing up a drawing(she’s an artist) to include in my presentation and I’m to tired to keep working so I figured I’d post something about the curse here.

Here are some interesting lecture notes on The curse of dimensionality: