Comment by mbrubeck

"Combinatorial Sketching" is a surprising technique that does something close to this:

http://people.csail.mit.edu/asolar/papers/asplos06-final.pdf