Book Image

Clojure for Data Science

By : Henry Garner
Book Image

Clojure for Data Science

By: Henry Garner

Overview of this book

Table of Contents (18 chapters)
Clojure for Data Science
Credits
About the Author
Acknowledgments
About the Reviewer
www.PacktPub.com
Preface
Index

Probabilistic methods for large sets


Large sets appear in many contexts in data science. We're likely to encounter them while dealing with users' implicit feedback as previously mentioned, but the approaches described next can be applied to any data that can be represented as a set.

Testing set membership with Bloom filters

Bloom filters are data structures that provide a means to compress the size of a set while preserving our ability to tell whether a given item is a member of the set or not. The price of this compression is some uncertainty. A Bloom filter tells us when an item may be in a set, although it will tell us for certain if it isn't. In situations where disk space saving is worth the small sacrifice in certainty, they are a very popular choice for set compression.

The base data structure of a Bloom filter is a bit vector—a sequence of cells that may contain 1 or 0 (or true or false). The level of compression (and the corresponding increase in uncertainty) is configurable with two...