The essential goal is to minimize the number of arrays that you actually search, no matter how you go about searching or representing them.

This was my thought too; with that many items to cross-compare, doing various "cheats" to cut down on how many you actually need to search is profitable. Even something as simple as just keeping counts of the number of 1's in each array can give you a real cheap method of asking "is it possible that these two arrays are the same?"

You'll get false positives (probably a lot of them), but you can guarantee no false negatives, so that can chop orders of magnitude off the problem. With a 15,000-element array, you know there's some number between 0 and 15000 1's; if they're evenly distributed (which they won't be even close, but it's a starting point to guess) then you're immediately dropping from "test these 5 million" to "test these 333", which is a huge speedup. Even if the distribution is off by an order or two of magnitude, dropping to 3 or 30,000 comparisons is a giant gain from 5 million.

Then adding some additional cheap to store/compare (maybe not necessarily calculate, but you may be able do this at the same time as the arrays get built for minimal added expense) hints like the leftmost-1-index or rightmost-1-index or longer-run-of-1's or some other thing meaningful to your data set, can chop that down even further. At what point the diminishing returns start hurting you is situation specific; it would take knowing your data and possibly some experimentation to find it.

In essence, these sort of universe-narrowing tricks can be seen as variations on the theme of Bloom filters. A quick glance at cpan shows up some Bloom filter implementations, but it's hard to say whether they're well suited to this particular type/scale of usage. But they may on deeper investigation prove to be so...