What's the advantage of this over storing full public keys at specific intervals?

Also as you target a larger number of keys, your time spent scanning for the bit sequence increases, unless you use some smarter data structures (which would not be as small as 3.81mb anymore)