This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 612ffb2 feat(bloom): replace invert with a set difference operation
(#278)
612ffb2 is described below
commit 612ffb229748276037067eb8a915f8bb55a7e8a0
Author: tison <[email protected]>
AuthorDate: Wed Sep 16 12:45:19 2026 +0800
feat(bloom): replace invert with a set difference operation (#278)
---
CHANGELOG.md | 2 +
README.md | 2 +-
datasketches/Cargo.toml | 4 ++
datasketches/examples/AGENTS.md | 7 +++
datasketches/examples/bloom_difference.rs | 89 ++++++++++++++++++++++++++++
datasketches/src/bloom/mod.rs | 12 ++--
datasketches/src/bloom/sketch.rs | 68 +++++++++++++++------
tests-integration/tests/bloom_test/sketch.rs | 84 ++++++++++++++++++++++----
8 files changed, 233 insertions(+), 35 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 29ceccf..fcfb676 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,10 +6,12 @@ All significant changes to this project will be documented in
this file.
### Breaking changes
+* Remove `BloomFilter::invert`. Bit inversion has no sound set-membership
interpretation; use the new `BloomFilter::difference` for the approximate
set-difference (A NOT B) use case it was meant to serve.
* Move `SearchCriteria` from `req` to `common` and remove its `Default`
implementation. Import `datasketches::common::SearchCriteria` and explicitly
choose `Inclusive` or `Exclusive` for each query.
### New features
+* Add `BloomFilter::difference` for approximate set difference: the result
excludes the other filter's items exactly, while items unique to the left
filter are kept unless their hash positions collide with the right filter.
* Add KLL sketches behind the `kll` feature, with rank, quantile, PMF, and CDF
queries, merging, totally ordered custom item types, a `KllFloat` adapter for
non-NaN floating-point values, and serialization.
### Improvements
diff --git a/README.md b/README.md
index 3143336..b7b04ba 100644
--- a/README.md
+++ b/README.md
@@ -75,7 +75,7 @@ Enable multiple algorithms by listing their features
together, such as `features
| `theta` | `ThetaSketch` and set operations | Distinct counts, set
expressions, and Jaccard similarity. |
| `tuple` | `TupleSketch` and set operations | Theta-style keys
with user-defined summaries attached to retained entries.
|
-See the [API documentation](https://docs.rs/datasketches) for configuration,
accuracy guarantees, serialization, and examples for each algorithm.
+See the [API documentation](https://docs.rs/datasketches) for configuration,
accuracy guarantees, serialization, and examples for each algorithm. Runnable
end-to-end scenarios live in [`datasketches/examples`](datasketches/examples).
## Compatibility
diff --git a/datasketches/Cargo.toml b/datasketches/Cargo.toml
index 1a31d98..0549005 100644
--- a/datasketches/Cargo.toml
+++ b/datasketches/Cargo.toml
@@ -49,6 +49,10 @@ tdigest = []
theta = []
tuple = []
+[[example]]
+name = "bloom_difference"
+required-features = ["bloom"]
+
[dev-dependencies]
googletest = { workspace = true }
insta = { workspace = true }
diff --git a/datasketches/examples/AGENTS.md b/datasketches/examples/AGENTS.md
new file mode 100644
index 0000000..c5c2448
--- /dev/null
+++ b/datasketches/examples/AGENTS.md
@@ -0,0 +1,7 @@
+# Example Style
+
+- Start each example with concise module documentation describing the scenario
and the behavior it demonstrates.
+- Omit run commands, basic Cargo instructions, and comments that merely
restate the code. Assume readers know how to run a Rust example.
+- Keep each example focused on a small, coherent scenario. Explain relevant
semantic differences beside the code; avoid catalogs of unrelated primitives.
+- Keep example explanations in the example source. The repository README only
needs a concise entry point.
+- Register each example in `datasketches/Cargo.toml` with an explicit
`[[example]]` section and its `required-features`, since every sketch feature
is opt-in.
diff --git a/datasketches/examples/bloom_difference.rs
b/datasketches/examples/bloom_difference.rs
new file mode 100644
index 0000000..ad8d375
--- /dev/null
+++ b/datasketches/examples/bloom_difference.rs
@@ -0,0 +1,89 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+//! An edge node folds the origin's purge list into its cache picture with
+//! `BloomFilter::difference`, producing one "everything it still serves"
filter to ship to
+//! sibling nodes. Purged objects are excluded exactly — a takedown is never
served again —
+//! while a few still-valid objects drop out of the filter and become origin
refetches.
+
+use datasketches::bloom::BloomFilter;
+use datasketches::bloom::BloomFilterBuilder;
+
+/// Returns the shared filter configuration published by the origin.
+///
+/// Both sides of a difference must use identical capacity, hash count, and
seed, so the
+/// parameters are distributed rather than chosen independently by each node.
+fn published_config() -> BloomFilterBuilder {
+ BloomFilterBuilder::with_accuracy(CACHED_OBJECTS, 0.01)
+}
+
+/// Number of objects cached by the edge node.
+const CACHED_OBJECTS: u64 = 100_000;
+
+/// Object keys purged in this epoch: every 200th cached object, 500 in total.
+fn purged_objects() -> impl Iterator<Item = u64> {
+ (0..CACHED_OBJECTS).step_by(200)
+}
+
+fn main() {
+ // The edge node records every object it caches.
+ let mut cached = published_config().build().unwrap();
+ for object in 0..CACHED_OBJECTS {
+ cached.insert(object);
+ }
+
+ // The origin records every purged object using the same published
configuration.
+ let mut purged = published_config().build().unwrap();
+ for object in purged_objects() {
+ purged.insert(object);
+ }
+
+ // Fold the purge list into the cache picture once, producing one artifact
to store or
+ // ship instead of keeping both filters and querying both per lookup. A
cached object
+ // survives only while none of its hash positions is occupied in the purge
filter, so
+ // difference suits a subtracted set that is sparse in the shared shape —
a purge list
+ // is naturally tiny next to a whole cache.
+ cached.difference(&purged).unwrap();
+
+ // The guarantee that matters for takedowns: a purged object is never
served again.
+ for object in purged_objects() {
+ assert!(!cached.contains(&object));
+ }
+
+ // Count how many still-valid objects survived; dropped ones cost an
origin refetch,
+ // never a stale serve.
+ let valid = CACHED_OBJECTS - purged_objects().count() as u64;
+ let mut retained = 0_u64;
+ for object in (0..CACHED_OBJECTS).filter(|object| object % 200 != 0) {
+ if cached.contains(&object) {
+ retained += 1;
+ }
+ }
+ println!("Cached objects: {CACHED_OBJECTS}");
+ println!("Purged objects: {}", purged_objects().count());
+ println!(
+ "Still served: {retained} / {valid} valid objects ({:.1}% retained;
drops become cache misses)",
+ retained as f64 / valid as f64 * 100.0
+ );
+ assert!(retained as f64 >= valid as f64 * 0.9);
+
+ // Ship the resulting filter to a sibling node; the purge filter is
discarded.
+ let bytes = cached.serialize();
+ let shipped = BloomFilter::deserialize(&bytes).unwrap();
+ assert_eq!(shipped, cached);
+ println!("Shipped filter: {} bytes", bytes.len());
+}
diff --git a/datasketches/src/bloom/mod.rs b/datasketches/src/bloom/mod.rs
index dabecdb..ff49e3f 100644
--- a/datasketches/src/bloom/mod.rs
+++ b/datasketches/src/bloom/mod.rs
@@ -28,8 +28,10 @@
//! * **Fixed size**: Unlike typical sketches, Bloom filters do not resize
automatically
//! * **Linear space**: Size is proportional to the expected number of
distinct items
//!
-//! These guarantees describe normal operation. After
[`invert()`](BloomFilter::invert) neither
-//! the no-false-negative nor the false-positive guarantee holds; see its
documentation.
+//! Set operations transform the represented set:
[`union()`](BloomFilter::union) keeps items
+//! from either filter, and [`intersect()`](BloomFilter::intersect) keeps only
items in both.
+//! [`difference()`](BloomFilter::difference) excludes the right filter's
items exactly, but
+//! may also drop left items whose hash positions collide with the right
filter.
//!
//! # Usage
//!
@@ -128,8 +130,10 @@
//! // Intersect: recognizes only items in both filters
//! // filter1.intersect(&filter2).unwrap();
//!
-//! // Invert: approximately inverts set membership
-//! // filter1.invert();
+//! // Difference: recognizes items in filter1 that are definitely not in
filter2
+//! filter1.difference(&filter2).unwrap();
+//! assert!(filter1.contains(&"a"));
+//! assert!(!filter1.contains(&"b"));
//! ```
//!
//! # Implementation Details
diff --git a/datasketches/src/bloom/sketch.rs b/datasketches/src/bloom/sketch.rs
index d0d4b6b..fb311a8 100644
--- a/datasketches/src/bloom/sketch.rs
+++ b/datasketches/src/bloom/sketch.rs
@@ -38,8 +38,6 @@ const EMPTY_FLAG_MASK: u8 = 1 << 2;
/// * No false negatives (inserted items always return `true`)
/// * Tunable false positive rate
/// * Constant space usage
-///
-/// These guarantees hold until [`invert()`](Self::invert) is called; see its
documentation.
#[derive(Debug, Clone, PartialEq)]
pub struct BloomFilter {
/// Hash seed for all hash functions
@@ -251,38 +249,70 @@ impl BloomFilter {
Ok(())
}
- /// Inverts all bits in the filter.
+ /// Computes the approximate set difference with another filter via
bitwise AND-NOT.
+ ///
+ /// After this operation, the filter approximates the set of items
inserted into this
+ /// filter but not into `other`:
+ /// * Items inserted into `other` always return `false`: they are excluded
exactly.
+ /// * Items inserted only into this filter keep returning `true` as long
as none of their hash
+ /// positions is occupied in `other`. Unlike [`union()`](Self::union) and
+ /// [`intersect()`](Self::intersect), this operation can drop items,
with a probability that
+ /// grows with `other`'s load factor.
+ /// * Items never inserted into this filter may return `true` (false
positives), at a rate no
+ /// higher than this filter's false positive rate before the operation.
///
- /// This approximately inverts the notion of set membership. After
inversion, neither the
- /// no-false-negative nor the false-positive guarantee holds: inserted
items may return
- /// `false` from [`contains()`](Self::contains), and
[`is_empty()`](Self::is_empty),
- /// [`bits_used()`](Self::bits_used), and
[`load_factor()`](Self::load_factor) describe the
- /// raw bit state rather than the inserted items.
+ /// This is the transformation other DataSketches libraries expose as A
NOT B.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error if the filters are not compatible (different size,
number of hashes, or
+ /// seed). Use [`is_compatible()`](Self::is_compatible) to check first
when an error is not
+ /// expected.
///
/// # Examples
///
/// ```
/// use datasketches::bloom::BloomFilterBuilder;
///
- /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// let mut left = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .seed(123)
/// .build()
/// .unwrap();
- /// filter.insert("apple");
+ /// let mut right = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .seed(123)
+ /// .build()
+ /// .unwrap();
+ ///
+ /// left.insert("apple");
+ /// left.insert("shared");
+ /// right.insert("grape");
+ /// right.insert("shared");
///
- /// filter.invert();
- /// // Now "apple" probably returns false, and most other items return true
+ /// left.difference(&right).unwrap();
+ /// assert!(left.contains(&"apple")); // Only in the left filter
+ /// assert!(!left.contains(&"shared")); // In both filters: excluded
exactly
/// ```
- pub fn invert(&mut self) {
- for word in &mut self.bit_array {
- *word = !*word;
+ pub fn difference(&mut self, other: &BloomFilter) -> Result<(), Error> {
+ if !self.is_compatible(other) {
+ return Err(Error::invalid_argument(
+ "Bloom filters must have matching capacity, number of hashes,
and seed",
+ ));
}
- self.num_bits_set = self.capacity() as u64 - self.num_bits_set;
+
+ // Count bits during difference operation (single pass)
+ let mut num_bits_set = 0;
+ for (word, other_word) in
self.bit_array.iter_mut().zip(&other.bit_array) {
+ *word &= !*other_word;
+ num_bits_set += word.count_ones() as u64;
+ }
+ self.num_bits_set = num_bits_set;
+ Ok(())
}
- /// Returns whether no bits are set in the filter.
+ /// Returns `true` if no bits are set in the filter.
///
- /// In normal operation this means no items were inserted. After
[`invert()`](Self::invert),
- /// it reports the raw bit state instead.
+ /// This is the case when no items were inserted, after
[`reset()`](Self::reset), or when a
+ /// set operation cleared every bit.
pub fn is_empty(&self) -> bool {
self.num_bits_set == 0
}
diff --git a/tests-integration/tests/bloom_test/sketch.rs
b/tests-integration/tests/bloom_test/sketch.rs
index 3032fd9..db0a0db 100644
--- a/tests-integration/tests/bloom_test/sketch.rs
+++ b/tests-integration/tests/bloom_test/sketch.rs
@@ -15,6 +15,7 @@
// specific language governing permissions and limitations
// under the License.
+use datasketches::bloom::BloomFilter;
use datasketches::bloom::BloomFilterBuilder;
use datasketches::error::ErrorKind;
use googletest::assert_that;
@@ -26,7 +27,7 @@ const NUM_BITS: u64 = 65_536;
const NUM_HASHES: u16 = 5;
const SEED: u64 = 123;
-fn filter() -> datasketches::bloom::BloomFilter {
+fn filter() -> BloomFilter {
BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
.seed(SEED)
.build()
@@ -84,18 +85,79 @@ fn test_union_and_intersection() {
}
#[test]
-fn test_invert_is_reversible() {
- let mut filter = filter();
- filter.insert("apple");
- filter.insert("banana");
+fn test_difference_excludes_right_items_exactly() {
+ let mut left = filter();
+ let mut right = filter();
+ for i in 0..100_u64 {
+ left.insert(i);
+ right.insert(i);
+ }
+ for i in 100..200_u64 {
+ left.insert(i);
+ }
+
+ let left_bits = left.bits_used();
+ left.difference(&right).unwrap();
+
+ // Items inserted into the right filter are excluded exactly.
+ for i in 0..100_u64 {
+ assert!(!left.contains(&i));
+ }
+ assert_that!(left.bits_used(), le(left_bits));
+
+ // The bit count must stay consistent with the backing array.
+ let restored = BloomFilter::deserialize(&left.serialize()).unwrap();
+ assert_eq!(restored, left);
+}
+
+#[test]
+fn test_difference_keeps_disjoint_items() {
+ let mut left = filter();
+ left.insert("shared");
+ left.insert("left");
+
+ let mut right = filter();
+ right.insert("shared");
+ right.insert("right");
+
+ left.difference(&right).unwrap();
+ assert!(left.contains(&"left"));
+ assert!(!left.contains(&"shared"));
+ assert!(!left.contains(&"right"));
+}
+
+#[test]
+fn test_difference_with_self_clears_filter() {
+ let mut left = filter();
+ left.insert("apple");
+ left.insert("banana");
+
+ let same = left.clone();
+ left.difference(&same).unwrap();
+ assert!(left.is_empty());
+ assert_eq!(left.bits_used(), 0);
+ assert!(!left.contains(&"apple"));
+}
- let original = filter.clone();
- let original_bits = filter.bits_used();
- filter.invert();
- assert_eq!(filter.bits_used(), filter.capacity() as u64 - original_bits);
+#[test]
+fn test_difference_with_empty_right_is_identity() {
+ let mut left = filter();
+ left.insert("apple");
- filter.invert();
- assert_eq!(filter, original);
+ let original = left.clone();
+ left.difference(&filter()).unwrap();
+ assert_eq!(left, original);
+}
+
+#[test]
+fn test_difference_rejects_incompatible_filters() {
+ let mut left = filter();
+ let right = BloomFilterBuilder::with_size(NUM_BITS, NUM_HASHES)
+ .seed(SEED + 1)
+ .build()
+ .unwrap();
+ let error = left.difference(&right).unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
#[test]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
