I've spent a couple of days thinking about this and playing with alternative solutions, but nothing comes close to being a fast as what you're doing now.
The problem of course, is that what you're doing now trades truly huge amounts of space for its speed. And so we come back to the problem of how to avoid having to either:
And given the huge limits you are working with--30,000 X ranges from 0 .. 15,000,000--I don't see a solution. The presence of "inverted" ranges, in concert with the 15e6 overall range, defy all my attempts at a more compact representation. And I don't believe you'll beat Storable easily either.
In short. I have nothing to offer your original question beyond one possibility.
There is a data structure, QuadTree that might come close to achieving the performance of your current solution, but use far less memory. The problem is that writing such a solution in terms of Perl's existing data structures to achieve a pure perl solution isn't effective.
You would need to obtain a C-library and write a wrapper for it. And there is no guarantee that the solution would perform as well.
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.