Bloom maps for big data
David Talbot · 2010
The ability to retrieve a value given a key is fundamental in computer science. Unfortunately as the a priori set from which keys are drawn grows in size, any exact data structure must use more space per key. This motivates our interest in approximate data structures. We consider the problem of succinctly encoding a map to support queries with bounded error when the distribution over values is known. We give a lower bound on the space required per key in terms of the entropy of the distribution over values and the error rate and present a generalization of the Bloom filter, the Bloom map, that achieves the lower bound up to a small constant factor. We then develop static and on-line approximation schemes for frequency data that use constant space per key to store frequencies with bounded relative error when these follow a power law. Our on-line construction has constant expected update complexity per observation and requires only a single pass over a data set. Finally we present a simple framework for using a priori knowledge to reduce the error rate of an approximate data structure with one-sided error. We evaluate the data structures proposed here empirically and use them to construct randomized language models that significantly reduce the space requirements of a state-of-the-art statistical machine translation system. iii Acknowledgements This thesis would not have seen the light of day without a love of language and numbers that I picked up at an early age from my parents. Lacking most of the relevant skills for my chosen field, it would never have been completed without my brother’s patient help with the most basic of mathematical concepts. My adviser, Miles Osborne, provided me with invaluable critical input throughout my time at Edinburgh, while at least giving me the impression that he trusted me to know what I was doing. Finally, for helping me maintain a semblance of sanity, at least for public display, my biggest thanks goes to my best friend Daisuke. iv Declaration I declare that this thesis was composed by myself, that the work contained herein is my own except where explicitly stated otherwise in the text, and that this work has not been submitted for any other degree or professional qualification except as specified.