Bloomier Filters: A second look Export

@misc{citeulike:2974098, abstract = {A 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.}, archivePrefix = {arXiv}, author = {Charles, Denis and Chellapilla, Kumar}, citeulike-article-id = {2974098}, citeulike-linkout-0 = {http://arxiv.org/abs/0807.0928}, citeulike-linkout-1 = {http://arxiv.org/pdf/0807.0928}, day = {6}, eprint = {0807.0928}, keywords = {bloomier, boom, filters}, month = {Jul}, posted-at = {2009-02-24 15:28:33}, priority = {2}, title = {Bloomier Filters: A second look}, url = {http://arxiv.org/abs/0807.0928}, year = {2008} }

TY - ELEC ID - citeulike:2974098 L3 - citeulike-article-id:2974098 N2 - A 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. TI - Bloomier Filters: A second look KW - bloomier KW - boom KW - filters AU - Charles, Denis AU - Chellapilla, Kumar PY - 2008/Jul/06/ UR - http://arxiv.org/abs/0807.0928 ER -