Radhakrishnan, Jaikumar ; Shah, Smit ; Shannigrahi, Saswata (2010) Data structures for storing small sets in the bitprobe model Lecture Notes in Computer Science, 6347 . pp. 159-170. ISSN 0302-9743
![]()
|
PDF
- Author Version
160kB |
Official URL: http://www.springerlink.com/index/M134G26522762307...
Related URL: http://dx.doi.org/10.1007/978-3-642-15781-3_14
Abstract
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 Ω(m4/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.
Item Type: | Article |
---|---|
Source: | Copyright of this article belongs to Springer. |
ID Code: | 89494 |
Deposited On: | 27 Apr 2012 13:41 |
Last Modified: | 19 May 2016 04:02 |
Repository Staff Only: item control page