You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@datasketches.apache.org by "v0id-X (via GitHub)" <gi...@apache.org> on 2026/09/03 01:11:41 UTC
[PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
v0id-X opened a new pull request, #271:
URL: https://github.com/apache/datasketches-rust/pull/271
- Replaces in-place bit inversion on BloomFilter with an owned BloomFilterInvertedView.
-
- Prevents unsound mutations on an inverted filter while retaining membership queries.
-
- Provides bi-directional conversion via invert() and into_filter().
-
- Added unit and integration tests covering the new view type and conversion paths.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on code in PR #271:
URL: https://github.com/apache/datasketches-rust/pull/271#discussion_r3920180109
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -613,6 +622,114 @@ impl BloomFilter {
}
}
+/// A read-only inverted view of a [`BloomFilter`].
+///
+/// An inverted view is created by calling [`BloomFilter::invert()`].
+/// Modifications (such as inserting new elements or merging) are disallowed
+/// on an inverted view to avoid corrupting set membership invariants.
+///
+/// Set membership queries can still be executed via [`contains()`](Self::contains),
+/// and the view can be reinverted back into an updatable [`BloomFilter`].
+#[derive(Debug, Clone, PartialEq)]
+pub struct BloomFilterInvertedView {
+ inner: BloomFilter,
+}
+
+impl BloomFilterInvertedView {
+ /// Returns `true` if an item is possibly in the inverted set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// assert!(!inverted.contains(&"apple"));
+ /// ```
+ pub fn contains<T: Hash>(&self, item: &T) -> bool {
+ self.inner.contains(item)
+ }
+
+ /// Re-inverts the view back into an updatable [`BloomFilter`].
+ ///
+ /// Inverting twice restores the original bit state and filter guarantees.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// let restored = inverted.invert();
+ /// assert!(restored.contains(&"apple"));
+ /// ```
+ pub fn invert(self) -> BloomFilter {
+ self.into_filter()
+ }
+
+ /// Converts this inverted view back into an updatable [`BloomFilter`] by
+ /// inverting the bits again.
+ ///
+ /// Equivalent to [`invert()`](Self::invert).
+ pub fn into_filter(mut self) -> BloomFilter {
+ for word in &mut self.inner.bit_array {
+ *word = !*word;
+ }
+ self.inner.num_bits_set = self.inner.capacity() as u64 - self.inner.num_bits_set;
+ self.inner
+ }
+
+ /// Returns a reference to the underlying [`BloomFilter`] representation.
+ pub fn as_filter(&self) -> &BloomFilter {
+ &self.inner
+ }
Review Comment:
Why do we have this method?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on code in PR #271:
URL: https://github.com/apache/datasketches-rust/pull/271#discussion_r3920170750
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -39,7 +39,7 @@ const EMPTY_FLAG_MASK: u8 = 1 << 2;
/// * Tunable false positive rate
/// * Constant space usage
///
-/// These guarantees hold until [`invert()`](Self::invert) is called; see its documentation.
+/// These guarantees hold unless inverted via [`invert()`](Self::invert).
Review Comment:
This is no longer relevant because the inverted view is now a brand-new read-only view. It is no longer a BloomFilter.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
Posted by "v0id-X (via GitHub)" <gi...@apache.org>.
v0id-X commented on code in PR #271:
URL: https://github.com/apache/datasketches-rust/pull/271#discussion_r3920226513
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -39,7 +39,7 @@ const EMPTY_FLAG_MASK: u8 = 1 << 2;
/// * Tunable false positive rate
/// * Constant space usage
///
-/// These guarantees hold until [`invert()`](Self::invert) is called; see its documentation.
+/// These guarantees hold unless inverted via [`invert()`](Self::invert).
Review Comment:
Yes, Removing it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on code in PR #271:
URL: https://github.com/apache/datasketches-rust/pull/271#discussion_r3920182688
##########
CHANGELOG.md:
##########
@@ -3,6 +3,7 @@
All significant changes to this project will be documented in this file.
## Unreleased
+- feat(bloom): make post-invert semantics observable via `BloomFilterInvertedView` (#270, #271)
Review Comment:
Please follow the changelog format like other entries.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on PR #271:
URL: https://github.com/apache/datasketches-rust/pull/271#issuecomment-5690888412
Thank you for picking this up — the implementation here was clean and well-tested. After a closer look at the underlying semantics, though, we've decided not to expose the inverted state at all, which makes this approach moot.
The reasoning, in short: an inverted Bloom filter only answers "definitely not inserted" on its `true` side, and the original filter already answers that (with a much higher hit rate) on its `false` side — so a read-only inverted view is a strictly worse absence oracle than the filter it came from. The one composition with a clean per-item meaning is A AND NOT B, and that use case is better served by an explicit set-difference operation than by exposing an inverted intermediate. #278 implements that: it removes `invert()` and adds `BloomFilter::difference` with documented semantics.
Closing this in favor of #278; the cross-language discussion is tracked at https://github.com/apache/datasketches-java/issues/766. Your exploration here was still useful input for reaching that conclusion.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
Posted by "v0id-X (via GitHub)" <gi...@apache.org>.
v0id-X commented on code in PR #271:
URL: https://github.com/apache/datasketches-rust/pull/271#discussion_r3920227331
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -251,13 +251,17 @@ impl BloomFilter {
Ok(())
}
- /// Inverts all bits in the filter.
+ /// Consumes the filter and inverts all its bits, returning a read-only inverted view.
///
/// 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.
+ /// `false` from [`contains()`](BloomFilterInvertedView::contains), and metadata methods
+ /// describe the raw inverted bit state.
+ ///
+ /// Updates are disallowed on an inverted view to prevent unsound filter states. An inverted
+ /// view can be converted back into an updatable [`BloomFilter`] via
+ /// [`invert()`](BloomFilterInvertedView::invert) or
+ /// [`into_filter()`](BloomFilterInvertedView::into_filter).
Review Comment:
Agreed. I'll trim the method documentation down to its core behavior and move the details regarding disallowed mutations and reinversion up to the BloomFilterInvertedView struct documentation.
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -613,6 +622,114 @@ impl BloomFilter {
}
}
+/// A read-only inverted view of a [`BloomFilter`].
+///
+/// An inverted view is created by calling [`BloomFilter::invert()`].
+/// Modifications (such as inserting new elements or merging) are disallowed
+/// on an inverted view to avoid corrupting set membership invariants.
+///
+/// Set membership queries can still be executed via [`contains()`](Self::contains),
+/// and the view can be reinverted back into an updatable [`BloomFilter`].
+#[derive(Debug, Clone, PartialEq)]
+pub struct BloomFilterInvertedView {
+ inner: BloomFilter,
+}
+
+impl BloomFilterInvertedView {
+ /// Returns `true` if an item is possibly in the inverted set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// assert!(!inverted.contains(&"apple"));
+ /// ```
+ pub fn contains<T: Hash>(&self, item: &T) -> bool {
+ self.inner.contains(item)
+ }
+
+ /// Re-inverts the view back into an updatable [`BloomFilter`].
+ ///
+ /// Inverting twice restores the original bit state and filter guarantees.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// let restored = inverted.invert();
+ /// assert!(restored.contains(&"apple"));
+ /// ```
+ pub fn invert(self) -> BloomFilter {
+ self.into_filter()
+ }
+
+ /// Converts this inverted view back into an updatable [`BloomFilter`] by
+ /// inverting the bits again.
+ ///
+ /// Equivalent to [`invert()`](Self::invert).
+ pub fn into_filter(mut self) -> BloomFilter {
+ for word in &mut self.inner.bit_array {
+ *word = !*word;
+ }
+ self.inner.num_bits_set = self.inner.capacity() as u64 - self.inner.num_bits_set;
+ self.inner
+ }
Review Comment:
That makes a lot more sense. Symmetrical .invert() (filter.invert().invert()) is way cleaner anyway. Dropping into_filter and keeping just invert(self) -> BloomFilter.
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -613,6 +622,114 @@ impl BloomFilter {
}
}
+/// A read-only inverted view of a [`BloomFilter`].
+///
+/// An inverted view is created by calling [`BloomFilter::invert()`].
+/// Modifications (such as inserting new elements or merging) are disallowed
+/// on an inverted view to avoid corrupting set membership invariants.
+///
+/// Set membership queries can still be executed via [`contains()`](Self::contains),
+/// and the view can be reinverted back into an updatable [`BloomFilter`].
+#[derive(Debug, Clone, PartialEq)]
+pub struct BloomFilterInvertedView {
+ inner: BloomFilter,
+}
+
+impl BloomFilterInvertedView {
+ /// Returns `true` if an item is possibly in the inverted set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// assert!(!inverted.contains(&"apple"));
+ /// ```
+ pub fn contains<T: Hash>(&self, item: &T) -> bool {
+ self.inner.contains(item)
+ }
+
+ /// Re-inverts the view back into an updatable [`BloomFilter`].
+ ///
+ /// Inverting twice restores the original bit state and filter guarantees.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// let restored = inverted.invert();
+ /// assert!(restored.contains(&"apple"));
+ /// ```
+ pub fn invert(self) -> BloomFilter {
+ self.into_filter()
+ }
+
+ /// Converts this inverted view back into an updatable [`BloomFilter`] by
+ /// inverting the bits again.
+ ///
+ /// Equivalent to [`invert()`](Self::invert).
+ pub fn into_filter(mut self) -> BloomFilter {
+ for word in &mut self.inner.bit_array {
+ *word = !*word;
+ }
+ self.inner.num_bits_set = self.inner.capacity() as u64 - self.inner.num_bits_set;
+ self.inner
+ }
+
+ /// Returns a reference to the underlying [`BloomFilter`] representation.
+ pub fn as_filter(&self) -> &BloomFilter {
+ &self.inner
+ }
Review Comment:
I thought about it, this makes the abstraction weaker risking misuse. Removing it entirely.
##########
CHANGELOG.md:
##########
@@ -3,6 +3,7 @@
All significant changes to this project will be documented in this file.
## Unreleased
+- feat(bloom): make post-invert semantics observable via `BloomFilterInvertedView` (#270, #271)
Review Comment:
My bad, will fix the formatting to match the rest of the file.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on code in PR #271:
URL: https://github.com/apache/datasketches-rust/pull/271#discussion_r3920174620
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -251,13 +251,17 @@ impl BloomFilter {
Ok(())
}
- /// Inverts all bits in the filter.
+ /// Consumes the filter and inverts all its bits, returning a read-only inverted view.
///
/// 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.
+ /// `false` from [`contains()`](BloomFilterInvertedView::contains), and metadata methods
+ /// describe the raw inverted bit state.
+ ///
+ /// Updates are disallowed on an inverted view to prevent unsound filter states. An inverted
+ /// view can be converted back into an updatable [`BloomFilter`] via
+ /// [`invert()`](BloomFilterInvertedView::invert) or
+ /// [`into_filter()`](BloomFilterInvertedView::into_filter).
Review Comment:
I think this can be a document of `BloomFilterInvertedView` rather than details on the method.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun commented on code in PR #271:
URL: https://github.com/apache/datasketches-rust/pull/271#discussion_r3920179217
##########
datasketches/src/bloom/sketch.rs:
##########
@@ -613,6 +622,114 @@ impl BloomFilter {
}
}
+/// A read-only inverted view of a [`BloomFilter`].
+///
+/// An inverted view is created by calling [`BloomFilter::invert()`].
+/// Modifications (such as inserting new elements or merging) are disallowed
+/// on an inverted view to avoid corrupting set membership invariants.
+///
+/// Set membership queries can still be executed via [`contains()`](Self::contains),
+/// and the view can be reinverted back into an updatable [`BloomFilter`].
+#[derive(Debug, Clone, PartialEq)]
+pub struct BloomFilterInvertedView {
+ inner: BloomFilter,
+}
+
+impl BloomFilterInvertedView {
+ /// Returns `true` if an item is possibly in the inverted set.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// assert!(!inverted.contains(&"apple"));
+ /// ```
+ pub fn contains<T: Hash>(&self, item: &T) -> bool {
+ self.inner.contains(item)
+ }
+
+ /// Re-inverts the view back into an updatable [`BloomFilter`].
+ ///
+ /// Inverting twice restores the original bit state and filter guarantees.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::bloom::BloomFilterBuilder;
+ ///
+ /// let mut filter = BloomFilterBuilder::with_accuracy(100, 0.01)
+ /// .build()
+ /// .unwrap();
+ /// filter.insert("apple");
+ ///
+ /// let inverted = filter.invert();
+ /// let restored = inverted.invert();
+ /// assert!(restored.contains(&"apple"));
+ /// ```
+ pub fn invert(self) -> BloomFilter {
+ self.into_filter()
+ }
+
+ /// Converts this inverted view back into an updatable [`BloomFilter`] by
+ /// inverting the bits again.
+ ///
+ /// Equivalent to [`invert()`](Self::invert).
+ pub fn into_filter(mut self) -> BloomFilter {
+ for word in &mut self.inner.bit_array {
+ *word = !*word;
+ }
+ self.inner.num_bits_set = self.inner.capacity() as u64 - self.inner.num_bits_set;
+ self.inner
+ }
Review Comment:
I don't think we need alias here. Please think of it by yourself rather than just blindly follow the issue description.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
Posted by "v0id-X (via GitHub)" <gi...@apache.org>.
v0id-X commented on PR #271:
URL: https://github.com/apache/datasketches-rust/pull/271#issuecomment-5519275636
All review comments addressed and updated:
- Removed the outdated guarantee disclaimer on `BloomFilter`.
- Moved mutation/inversion details from `BloomFilter::invert`'s doc to `BloomFilterInvertedView`'s struct-level documentation.
- Removed the `into_filter` alias in favor of symmetrical `invert(self) -> BloomFilter`.
- Removed `as_filter` to preserve view encapsulation.
- Aligned `CHANGELOG.md` under `### Breaking changes` and `### New features` per `CONTRIBUTING.md`.
- Uncommented the inverted view doctest example in `bloom/mod.rs`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org
Re: [PR] feat(bloom): introduce BloomFilterInvertedView for inverted queries (datasketches-rust)
Posted by "tisonkun (via GitHub)" <gi...@apache.org>.
tisonkun closed pull request #271: feat(bloom): introduce BloomFilterInvertedView for inverted queries
URL: https://github.com/apache/datasketches-rust/pull/271
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org