Efficient in-memory, list-based text inversion

Abstract

When building a large inverted file index on a system with effectively unlimited memory, performance may be constrained by RAM latency. To optimise speed requires an understanding of the non-uniform memory access characteristics of modern systems. We address three main techniques for improving the performance of an in-memory, list-based inverted file indexer: List chunking, in-chunk postings compression, and use of virtual memory "Large Pages". We compare performance of dynamic chunking schemes capable of adapting to the Zipf-like distribution of term frequencies. Using a data set with 8.5 billion word occurrences, we find that the techniques are cumulative. Chunking almost halves the memory required for linked lists, while dramatically reducing the number of cache-line reads required to traverse the lists; In-chunk compression further halves the memory footprint, though it does not make much difference to speed; Large pages reduce the inefficiency of page table walks and speed up both phases of index building. Show more