Not exactly an answer but would one of the two sparse formats discussed here be close to what you are looking for (CSX and SELL-C-sigma)? From my very shallow understanding of those formats they try to exploit dense patterns within the sparse matrix, thus constructing indexing for fast access of sub-blocks.