Change search
ReferencesLink to record
Permanent link

Direct link
Compressing main memory index lists
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

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.

Place, publisher, year, edition, pages
2015. , 31 p.
IT, 15059
National Category
Engineering and Technology
URN: urn:nbn:se:uu:diva-264273OAI: diva2:859712
Educational program
Bachelor Programme in Computer Science
Available from: 2015-10-08 Created: 2015-10-08 Last updated: 2015-10-08Bibliographically approved

Open Access in DiVA

fulltext(557 kB)127 downloads
File information
File name FULLTEXT01.pdfFile size 557 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 127 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 346 hits
ReferencesLink to record
Permanent link

Direct link