Compressing main memory index lists

Abstract: Index data structures are used in databases to get scalable access to rows in large tables for search conditions over indexed attributes. For each value of an indexed attribute, called the index key, the index associates a set of pointers, called the index list, to the rows where the value of the indexed attribute matches the key. If an index key over a very large collection has many duplicated values the index list can also become large. To make the indexes smaller and save space in main memory these index lists can be compressed. This thesis explores the benefits of using the state-of-the-art compression algorithm PForDelta to represent main-memory index lists compactly. PFordelta is used with two different implementations based on sequences of compressed arrays. The PForDelta implementations are compared with a naive linked list and a linked array implementation of index lists.