Inferring Insertion Times in Bloom Filters

Bloom filters are extremely useful in dealing with streaming data, but are easy to misuse. We first illustrate pitfalls in using Bloom Filters, and show how to generalize our techniques to infer insertion times. We introduce inferential filters, which integrate priors and information latent in filters to make optimal query-specific decisions.

We illustrate our approach on Time-Decaying Bloom Filters, which are probabilistic structures to test membership on recently inserted items. As new items are inserted, memory of older items decays. Incorrect query responses, however, will penalize the application using the filter. Current filters may only be tuned to static penalties, and ignore much information latent in the filter. While our methods are general, we focus here on inferential time-decaying filters, and show how to support novel query types and sliding window queries with varying error penalties.

We have developed inferential versions of the existing Timing Bloom Filter and Generalized Bloom Filter. Our experiments on real and synthetic datasets show that when penalties are dynamic and prior probabilities are known, these filters reduce penalties for incorrect responses to sliding-window queries by up to 70%.
Chinya V Ravishankar is Professor of Computer Science at the Marlan and Rosemary Bourns College of Engineering at UC Riverside. Ravishankar's current research and teaching focus is in the fields of Data Management as well as Computer Security. In the past, he has worked and taught in a wide range of areas, including Distributed Systems, Networking, and Programming Languages.

Prof. Ravishankar has served as Associate Dean for at the Marlan and Rosemary Bourns College of Engineering for the past 14 years. His current portfolio covers Research and Graduate Education. His earlier previous portfolio covered Undergraduate Education.

Before moving to UCR in 1999, Prof. Ravishankar was on the faculty of the EECS Department at the University of Michigan, Ann Arbor, between 1986"”1999. He holds a PhD in Computer Sciences from the University of Wisconsin"”Madison, and a bachelor's degree in Chemical Engineering from the Indian Institute of Technology (IIT) Bombay.