License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.38
URN: urn:nbn:de:0030-drops-69952
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6995/
Go to the corresponding LIPIcs Volume Portal

Garg, Mohit ; Radhakrishnan, Jaikumar

Set Membership with Non-Adaptive Bit Probes

pdf-format:
LIPIcs-STACS-2017-38.pdf (0.5 MB)

Abstract

We consider the non-adaptive bit-probe complexity of the set membership problem, where a set S of size at most n from a universe of size m is to be represented as a short bit vector in order to answer membership queries of the form "Is x in S?" by non-adaptively probing the bit vector at t places. Let s_N(m,n,t) be the minimum number of bits of storage needed for such a scheme. In this work, we show existence of non-adaptive and adaptive schemes for a range of t that improves an upper bound of Buhrman, Miltersen, Radhakrishnan and Srinivasan (2002) on s_N(m,n,t). For three non-adaptive probes, we improve the previous best lower bound on s_N(m,n,3) by Alon and Feige (2009).

BibTeX - Entry

@InProceedings{garg_et_al:LIPIcs:2017:6995,
  author =	{Mohit Garg and Jaikumar Radhakrishnan},
  title =	{{Set Membership with Non-Adaptive Bit Probes}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte ValleĢe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6995},
  URN =		{urn:nbn:de:0030-drops-69952},
  doi =		{10.4230/LIPIcs.STACS.2017.38},
  annote =	{Keywords: Data Structures, Bit-probe model, Compression, Bloom filters, Expansion}
}

Keywords: Data Structures, Bit-probe model, Compression, Bloom filters, Expansion
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI