Because we do not know how large the postings list of a term will be when
we first encounter it, we allocate space for a short postings list initially and
double the space each time it is full (lines 8–9). This means that some memory
is wasted, which counteracts the memory savings from the omission of
termIDs in intermediate data structures. However, the overall memory requirements
for the dynamically constructed index of a block in SPIMI are
still lower than in BSBI.
Each call of SPIMI-INVERT writes a block to disk, just as in BSBI. The last
step of SPIMI (corresponding to line 7 in Figure 4.2; not shown in Figure 4.4)
is then to merge the blocks into the final inverted index.