Data structures for storing small sets in the bitprobe model. / Radhakrishnan, Jaikumar; Shah, Smit; Shannigrahi, Saswata.
Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings. PART 2. ed. 2010. p. 159-170 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6347 LNCS, No. PART 2).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Data structures for storing small sets in the bitprobe model
AU - Radhakrishnan, Jaikumar
AU - Shah, Smit
AU - Shannigrahi, Saswata
PY - 2010/11/22
Y1 - 2010/11/22
N2 - We study the following set membership problem in the bit probe model: given a set S from a finite universe U, represent it in memory so that membership queries of the form "Is x in S?" can be answered with a small number of bitprobes. We obtain explicit schemes that come close to the information theoretic lower bound of Buhrman et al. [STOC 2000, SICOMP 2002] and improve the results of Radhakrishnan et al. [ESA 2001] when the size of sets and the number of probes is small. We show that any scheme that stores sets of size two from a universe of size m and answers membership queries using two bitprobes requires space Ω(m 4/7). The previous best lower bound (shown by Buhrman et al. using information theoretic arguments) was Ω(√m). The same lower bound applies for larger sets using standard padding arguments. This is the first instance where the information theoretic lower bound is found to be not tight for adaptive schemes. We show that any non-adaptive three probe scheme for storing sets of size two from a universe of size m requires Ω(√m) bits of memory. This extends a result of Alon and Feige [SODA 2009] to small sets.
AB - We study the following set membership problem in the bit probe model: given a set S from a finite universe U, represent it in memory so that membership queries of the form "Is x in S?" can be answered with a small number of bitprobes. We obtain explicit schemes that come close to the information theoretic lower bound of Buhrman et al. [STOC 2000, SICOMP 2002] and improve the results of Radhakrishnan et al. [ESA 2001] when the size of sets and the number of probes is small. We show that any scheme that stores sets of size two from a universe of size m and answers membership queries using two bitprobes requires space Ω(m 4/7). The previous best lower bound (shown by Buhrman et al. using information theoretic arguments) was Ω(√m). The same lower bound applies for larger sets using standard padding arguments. This is the first instance where the information theoretic lower bound is found to be not tight for adaptive schemes. We show that any non-adaptive three probe scheme for storing sets of size two from a universe of size m requires Ω(√m) bits of memory. This extends a result of Alon and Feige [SODA 2009] to small sets.
UR - http://www.scopus.com/inward/record.url?scp=78349261949&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-15781-3_14
DO - 10.1007/978-3-642-15781-3_14
M3 - Conference contribution
AN - SCOPUS:78349261949
SN - 3642157807
SN - 9783642157806
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 159
EP - 170
BT - Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings
T2 - 18th Annual European Symposium on Algorithms, ESA 2010
Y2 - 6 September 2010 through 8 September 2010
ER -
ID: 49849657