Bloom filters might provide an intelligent and scaling approach by "reusing bits for multiple rows". If your real application can tolerate some false positives, Bloom::Faster might be the ticket.

Reversing source and target arrays, redoing the comparison and comparing results should get rid of the false positives.

The effectiveness of all initial work depends on the probability of hits.