Techniques to store and manipulate collocation matrices

I suggest you try dictionaries of dictionary approach. Since list have an O(n) lookup time, while Dictionaries offer O(log n) lookup time.
NLTK has sparse vector encoding which is implemented as a python dict

scipy.sparse has many classes to deal with this sort of matrix. The idea is that you first use their lol (list of lists) representation to build the matrix, and then convert to a compact (there is more than one option) when using it, for fast access.

I have a similar problem but in my scenario, I need to write once such a matrix and than read it many times in a memory-limited web-server. Instead of using a DB-based approach, I created one dict for each row in the matrix and pickle-dumped the dict as a line in a plain data file. I also keep a separate poor man's index file which keeps the file positions of the lines for each word. That index can be kept in memory as a dict of words->file positions. When I have to lookup a vector, I lookup the position, seek to the current byte of data file and read one line and pickle.load it.

Something like that helps me to index the lines of a big matrix file which contains the row's label as the first field.

def index_write(data_file):        
    f = open(data_file)
    pos = f.tell()
    n = 0
    while True:
        line = f.readline().strip() 
        if line == "":
            break
        n += 1            
        key = line.split()[0] # First field is the row label
        print key,pos            
        pos = f.tell() # read current position