Secure randomized data matching? This might be a dumb question but I will go for it. 

Let's say we have a data set $D$ consisting of sensitive data, and we want to be able to match if a new piece of data $S$ already exists in $D$ ($S\stackrel{?}{\in} D$) or not, and we want to be able to know which of the entries matches $S$ in $D$.

Our approach consisted of a 1-way cryptographic hash such as SHA256. However, since the dataset is relatively small (about 4 million rows) we can easily reproduce the full dataset and in effect "decode" the original meaning of the hash. 

So I was wondering if it exists and algorithm that takes two parameters 


$d,b$: is a pair of some sensitive data and 
$s_i$: a random salt $i$


a cryptographic algorithm $C$ and a comparator $M$ such that

$M(C(d, s_1), C(b, s_2)) = \text{true}$, if $d == b$, 

and 

$M(C(d, s_1), C(b, s_2)) = \text{false}$, if $d != b$

So does such an algorithm or anything similar exist?
I don't believe that it is possible given the requirements you've listed.

Let us consider an arbitrary $C, M$ that meets the requirement.  To reveal the entire database, what an attacker can do is compute $C(d,s)$ for every possible $d$ (about 4 million, as you said); then, he can use $M$ to compare that to every value you actually have - this reveals everything.

To make this a solvable problem, you need to modify some assumption somewhere.

One way to address this is to prohibit an attacker from evaluating $C$ himself; we can define $C(d) = HMAC_k(d)$ for some secret key $k$.  This is determanistic (and so $M$ is a simple bitstring compare; we're assuming that we want to publicly reveal precise matches anyways, and so that's not an issue).

Another way to address this is to prohibit an attacker from evaluating $M$ himself;. One way to do this is, for some large prime $p$ and generator of a large prime subgroup $g$, we can pick a secret exponent $k$; we'd publish $g$, $p$ and $K = g^k \bmod p$.  We'd define $C(d, s) = (K^s, g^{s+d})$; we can't check if a particular $C$ corresponds to a specific $d$ if the Diffie-Hellman problem is hard.  And, the comparison function $M( (K^s, g^{s+d}), (K^t, g^{t+b}))$ (which is the comparison of an encoded $d$ and an encoded $b$) would check if $(g^{s+d})^k \cdot K^t = (g^{t+b})^k \cdot K^s$; as $K=g^k$, this is equivalent to $g^{ks+kd} g^{kt} = g^{kt+kb}g^{ks}$ or $K^d = K^b$