Integer Representations towards Efficient Counting in the Bit Probe Model

Gerth Stølting Brodal, Mark Greve, Vineet Pandey, and S. Srinivasa Rao

In Journal of Discrete Algorithms, volume 26, pages 34-44, 2014.

Abstract

We consider the problem of representing integers in close to optimal number of bits to support increment and decrement 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. We propose representations, called counters, with different trade-offs between the space used and the number of bits probed. A counter is space-optimal if it represents any integer 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. This is the first space-optimal representation which supports these operations by always reading strictly less than n bits. For redundant counters where we only need to represent integers in the range [0,...,L-1] for some integer L<2n using n bits, we define the space-efficiency of the counter as the ratio L/2n. We provide representations that achieve different trade-offs between the read/write-complexity and the efficiency.

We also examine the problem of representing integers to support addition and subtraction operations. We propose a representation of integers using n bits and with space efficiency at least 1/n, which supports addition and subtraction operations, improving the efficiency of an earlier representation by Munro and Rahman [Algorithmica, 2010]. We also show various trade-offs between the operation times and the space complexity.

Copyright notice

Copyright © 2013 by Elsevier Inc.. All rights reserved.

Online version

jda14.pdf (377 Kb)

DOI

10.1016/j.jda.2013.11.001

BIBTEX entry

@article{jda14,
  author = "Gerth St{\o}lting Brodal and Mark Greve and Vineet Pandey and S. Srinivasa Rao",
  doi = "10.1016/j.jda.2013.11.001",
  issn = "1570-8667",
  journal = "Journal of Discrete Algorithms",
  pages = "34-44",
  title = "Integer Representations towards Efficient Counting in the Bit Probe Model",
  volume = "26",
  year = "2014"
}

Other versions