Integer Representations towards Efficient Counting in the Bit Probe Model

October 12, 2011 at 15:00 / diplomska soba FE

Gerth Stølting Brodal
MADALGO - Center for MAssive Data ALGOrithmics, Denmark


We consider the problem of representing numbers in close to optimal space and supporting increment, decrement, addition and subtraction operations efficiently. We study the problem in the bit probe model and analyse the number of bits read and written to perform the operations, both in the worst-case and in the average-case. A counter is space-optimal if it represents any number in the range [0,...,2n-1] using exactly n bits. We provide a space-optimal counter which supports increment and decrement operations by reading at most n-1 bits and writing at most 3 bits in the worst-case. To the best of our knowledge, this is the first such representation which supports these operations by always reading strictly less than n bits. For redundant counters where we only need to represent numbers in the range [0,...,L] for some integer L < 2n-1 using n bits, we define the efficiency of the counter as the ratio between L+1 and 2n. We present various representations that achievedifferent trade-offs between the read and write complexities and theefficiency. We also give another representation of integers that uses n + O(log n) bits to represent integers in the range[0,...,2n-1] that supports efficient addition and subtractionoperations, improving the space complexity of an earlier representation by Munro and Rahman [Algorithmica, 2010].

About lecturer

Gerth Stølting Brodal is an Associate Professor at the Department of Computer Science, Aarhus University, Denmark. He received his PhD in computer science in 1997 from the Aarhus University for the thesis ``Worst Case Efficient Data Structures''. From 1997 to 1998 he was a Post. Doc. in the group of Kurt Mehlhorn at the Max-Planck-Institute for Computer Science in Saarbrücken, Germany. From 1998-2005 he was affiliated with BRICS (Center for Basic Research in Computer Science) located at the Department of Computer Science, Aarhus University. Since 2004 he is an Associate Professor (tenured) at the Department of Computer Science, Aarhus University. Since March 2007 he is affiliated with MADALGO (Center for Massive Data Algorithmics), Aarhus University, founded by the Danish National Research Foundataion.

His main research interests are the design and analysis of algorithms and data structures. He has done work on fundamental data structures, including dictionaries and priority queues, persistent data structures, computational geometry, graph algorithms, I/O-efficient and cache-oblivious algorithms and data structures, string algorithms, and computational biology.