# What do you call a "non-probabilistic Bloom Filter"?

One of my coworkers came up with a nice technique to solve a problem and I feel like it must already have a name. I just don't don't know how to figure out what it is.

It is a technique for caching easy answers for a subset of an input domain before falling back to an expensive computation. In that respect it reminds me of the semantics of a Bloom Filter or the pre-optimization idea of a Karnaugh Map.

Simple description w/ pseudocode:

// Determine whether "foo" is true with respect to the given ComplexThingy,
//   for the inputs bar and baz

boolean isFoo(ComplexThingy t, A a, B b):
// Let's say A and B are enums, or ints in a limited range, etc.
return expensive_computation(t, a, b)


// Alternative implementation w/ enhanced ComplexThingy for which
//   "trivial" cases (i.e. those that can ignore all but one dimension of the
//   input space) have been precomputed and stored in a simple bit array

boolean isFoo(ComplexThingyV2 t, A a, B b):
if t.quickPosLookup[a]
return true
if t.quickNegLookup[b]
return false
return expensive_computation(t, a, b)


Hopefully I've been able to convey that clearly. Thanks for your time!

• The general approach you're describing sounds like memoization.
– usul
Jul 16, 2016 at 23:45
• Thanks @usul, I considered this, but I think this is different enough that just calling it memoization would be misleading. (1) it's not saving the result of the function for the exact inputs. (2) it's precomputing rather than lazy-computing. Jul 17, 2016 at 0:44
• @leoger, you have mentioned it. This is, basically, the caching mechanism. Jul 4, 2019 at 16:21