Project ID:
RFP-2007-007
Title:
Classification of Bloom Filter variants,
and their suitability to various application domains
Summary:
Several Bloom Filter variants exist, including traditional, Counting,
Space-Code, Low-Power, Compressed, Bloomier, and others. They have
been applied to a variety of domains, including Spam detection, packet
classification, security, content summarization, measurement, and others.
However, we lack a comprehensive classification method to determine
which variants are most appropriate for the various application domains.
The question is, can a classification method be developed, that
characterizes the various Bloom Filter techniques, and determines for
which uses they are most suited?
Full Description:
We seek to advance the understanding of existing Bloom Filter variants,
and their applicability to various application domains.
This might include characterization and comparison of existing
methods (e.g., traditional, Counting, Space-Code, Low-Power, Compressed,
Bloomier, etc.) on their performance, scaling, and security properties.
Are there existing, or new, techniques to classify Bloom Filter variants, which
help understand where the methods are most useful? Do fundamental
issues exist when trying to apply different methods to different application
areas (e.g. Spam detection, packet classification, security, content
summarization, measurement, etc.)?
If fundamental classification methods are discovered, can the methods
help predict other classes of Bloom Filters, and where they might be used?
What are directions for, and pace of, evolving work in this area?
Since Cisco engineers have widely varying exposure to Bloom Filters,
it might also be helpful to highlight the most important work in the
area, and assemble a list like, "The (10?) most important things
Cisco engineers should know about Bloom Filters".
Constraints and other information:
IPR will stay with the University. Cisco expects customary scholarly dissemination of results, and hopes that promising results would be made available to the community without limiting licenses, royalties, or other encumbrances.
Proposal submission:
Cisco is not currently accepting proposals for this RFP.
Questions? Contact: research@cisco.com
