Efficient Data Structure and Algorithms for Sparse Integers, Sets and Predicates
Jean E. Vuillemin · 2009
We construct a natural number n > 1 by trichotomy n = g + xpd; xp= 22p, 0 les gp, 0p, applied recursively, and by systematically sharing nodes with equal integer value. The resulting integer decision diagram IDD is a directed acyclic graph DAG which represents n by s(n) nodes in computer memory. IDDs compete with bit arrays, which represent the consecutive bits of n within roughly 1(n) contiguous bits in memory. Unlike the binary length 1(n), the size s(n) is not monotonic. Most integers are dense: their size is near worst & average. The IDD size of sparse integers is arbitrarily smaller. Over dense numbers, the worst/average time/space complexity of IDDs arithmetic operations is proportional to that of bit arrays. Yet, equality testing is performed in unit time with IDDs and the time/space complexity of some operations (e.g. sign(n - m), n plusmn 2m, 22n) are (at least) exponentially better with IDDs than with bit arrays, even over dense operands. Over sparse operands, the time and space complexity of all ALU operations {cap , cup, oplus, +, -} are (in general) arbitrarily better with IDDs than bit-arrays. The coding powers of integers lets IDDs implement integer sets and predicates as well as arithmetics. The IDD package is a one shop alternative to 3 (and more) successful yet rather different packages for processing large numbers, dictionaries and Boolean functions. Performance levels are comparable over dense structures, and IDDs prove best in class over sparse structures.