Bloomier Filters: A second look

Simple item page
dc.creatorCharles, Denis
dc.creatorChellapilla, Kumar
dc.date2008-07-06
dc.date.accessioned2026-07-07T09:48:44Z
dc.date.available2026-07-07T09:48:44Z
dc.descriptionA Bloom filter is a space efficient structure for storing static sets, where the space efficiency is gained at the expense of a small probability of false-positives. A Bloomier filter generalizes a Bloom filter to compactly store a function with a static support. In this article we give a simple construction of a Bloomier filter. The construction is linear in space and requires constant time to evaluate. The creation of our Bloomier filter takes linear time which is faster than the existing construction. We show how one can improve the space utilization further at the cost of increasing the time for creating the data structure.
dc.description13 Pages, 3 figures, to appear in ESA - 2008
dc.identifierhttps://arxiv.org/abs/0807.0928
dc.identifierhttp://arxiv.org/abs/0807.0928
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/164326
dc.subjectData Structures and Algorithms
dc.subjectE.1; E.2
dc.titleBloomier Filters: A second look
dc.typetext

Files

Collections

arXiv