Storing matrices on disk for efficient row and column retrieval (Q1064062)

We study the problem of storing a matrix on disk where the cost for retrieving a row or column is the number of different pages containing elements of that row or column and the cost of a matrix is the sum of the cost for retrieving each row and column. We give a non-obvious, nontrivial lower bound on the cost and one algorithm that asymptotically achieves this bound if the page size is in a given set of integers, and another that achieves it if not.