Dynamic integer sets with optimal rank, select, and predecessor search

TY - GEN

T1 - Dynamic integer sets with optimal rank, select, and predecessor search

AU - Patrascu, M.

AU - Thorup, Mikkel

N1 - Conference code: 55

PY - 2014/12/7

Y1 - 2014/12/7

N2 - We present a data structure representing a dynamic set S of w-bit integers on a w-bit word RAM. With S = n and w ≥ log n and space O(n), we support the following standard operations in O(log n/log w) time: insert(x) sets S = S + {x}. delete(x) sets S = S {x}. predecessor(x) returns max{y S y < x}. rank(x) returns #{y y < x}. select (i) returns y with rank (y) = i, if any. Our O(log n/log w) bound is optimal for dynamic rank and select, matching a lower bound of Fredman and Saks [STOC'89]. When the word length is large, our time bound is also optimal for dynamic predecessor, matching a static lower bound of Beame and Fich [STOC'99] whenever log n/log w = O(log w/log log w). Technically, the most interesting aspect of our data structure is that it supports all the above operations in constant time for sets of size n = w O(1). This resolves a main open problem of Ajtai, Komlos, and Fredman [FOCS]. Ajtai et al. presented such a data structure in Yaofs abstract cell-probe model with w-bit cells/words, but pointed out that the functions used could not be implemented. As a partial solution to the problem, Fredman and Willard [STOC129;f90] introduced a fusion node that could handle queries in constant time, but used polynomial time on the updates. We call our small set data structure a dynamic fusion node as it does both queries and updates in constant time.

AB - We present a data structure representing a dynamic set S of w-bit integers on a w-bit word RAM. With S = n and w ≥ log n and space O(n), we support the following standard operations in O(log n/log w) time: insert(x) sets S = S + {x}. delete(x) sets S = S {x}. predecessor(x) returns max{y S y < x}. rank(x) returns #{y y < x}. select (i) returns y with rank (y) = i, if any. Our O(log n/log w) bound is optimal for dynamic rank and select, matching a lower bound of Fredman and Saks [STOC'89]. When the word length is large, our time bound is also optimal for dynamic predecessor, matching a static lower bound of Beame and Fich [STOC'99] whenever log n/log w = O(log w/log log w). Technically, the most interesting aspect of our data structure is that it supports all the above operations in constant time for sets of size n = w O(1). This resolves a main open problem of Ajtai, Komlos, and Fredman [FOCS]. Ajtai et al. presented such a data structure in Yaofs abstract cell-probe model with w-bit cells/words, but pointed out that the functions used could not be implemented. As a partial solution to the problem, Fredman and Willard [STOC129;f90] introduced a fusion node that could handle queries in constant time, but used polynomial time on the updates. We call our small set data structure a dynamic fusion node as it does both queries and updates in constant time.

KW - computational complexity

KW - data structures

KW - random-access storage

KW - data structure

KW - dynamic fusion node

KW - dynamic integer sets

KW - dynamic predecessor

KW - optimal rank

KW - polynomial time

KW - predecessor search

KW - w-bit integers

KW - w-bit word RAM

KW - Computational modeling

KW - Data structures

KW - Indexes

KW - Polynomials

KW - Probes

KW - Random access memory

KW - Standards

KW - dynamic data structures

KW - integer data structures

U2 - 10.1109/FOCS.2014.26

DO - 10.1109/FOCS.2014.26

M3 - Article in proceedings

SP - 166

EP - 175

BT - FOCS 2014

PB - IEEE

T2 - IEEE Annual Symposium on Foundations of Computer Science (FOCS)

Y2 - 18 October 2014 through 21 October 2014

ER -