Building a dict/list of lists
What would you think of

match_iter = izip(*valid_lists)
rid2 = defaultdict(list)
for qfx, rid, fx, fs, fk in match_iter:
    rid2[rid].append(qfx, fx, fs, fk)


Seems like that might cut the time in the final loop by almost 50%. The extraction from match_iter doesn't change, so it will take the same amount of time. The append will take about the same amount of time as one of the appends you're already doing. Since two appends will be eliminated, I think the time they're taking will go away.