Skip to content

Commit 44c6201

Browse files
leerholeerho
authored
Merge pull request #768 from jaideeppyne/bloom-difference-deprecate-invert-766
Deprecate BloomFilter.invert and add difference (A NOT B)
2 parents f8018f0 + c20bd80 commit 44c6201

9 files changed

Lines changed: 201 additions & 3 deletions

File tree

‎src/main/java/org/apache/datasketches/filters/bloomfilter/BitArray.java‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -88,6 +88,9 @@ boolean isEmpty() {
8888

8989
abstract void invert();
9090

91+
// applies logical AND-NOT (this &= ~other), matching BitSet.andNot
92+
abstract void andNot(final BitArray other);
93+
9194
// prints the raw BitArray as 0s and 1s, one long per row
9295
@Override
9396
public String toString() {

‎src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilter.java‎

Lines changed: 38 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -703,13 +703,50 @@ public void intersect(final BloomFilter other) {
703703

704704
/**
705705
* Inverts all the bits of the BloomFilter. Approximately inverts the notion of set-membership.
706+
*
707+
* @deprecated Bit inversion has no sound set-membership interpretation. An inverted filter is a
708+
* strictly worse absence oracle than the original, and updates after inversion have no checkable
709+
* meaning. Use {@link #difference(BloomFilter)} for the approximate set-difference (A NOT B) use
710+
* case {@code invert} was meant to enable. See
711+
* <a href="https://github.com/apache/datasketches-java/issues/766">#766</a>.
706712
*/
713+
@Deprecated
707714
public void invert() {
708715
bitArray_.invert();
709716
}
710717

711718
/**
712-
* Helps identify if two BloomFilters may be unioned or intersected.
719+
* Computes the approximate set difference with another filter via bitwise AND-NOT
720+
* ({@code this &= ~other}). After this operation, the filter approximates the set of items
721+
* inserted into this filter but not into {@code other}:
722+
* <ul>
723+
* <li>Items inserted into {@code other} always query {@code false}: they are excluded exactly.</li>
724+
* <li>Items inserted only into this filter keep querying {@code true} as long as none of their
725+
* hash positions is occupied in {@code other}. Unlike {@link #union(BloomFilter)} and
726+
* {@link #intersect(BloomFilter)}, this operation can drop items, with a probability that
727+
* grows with {@code other}'s load factor.</li>
728+
* <li>Items never inserted into this filter may still query {@code true} (false positives), at a
729+
* rate no higher than this filter's false positive rate before the operation.</li>
730+
* </ul>
731+
* This is the Bloom-filter form of the A NOT B operation exposed elsewhere in DataSketches
732+
* (for example Theta {@code AnotB}). Compatible with the Rust {@code BloomFilter::difference}
733+
* API.
734+
*
735+
* @param other A BloomFilter to subtract from this one. A {@code null} argument is a no-op.
736+
* @throws SketchesArgumentException if the filters are not compatible (different seeds, hash
737+
* counts, or sizes)
738+
*/
739+
public void difference(final BloomFilter other) {
740+
if (other == null) { return; }
741+
if (!isCompatible(other)) {
742+
throw new SketchesArgumentException("Cannot difference sketches with different seeds, hash functions, or sizes");
743+
}
744+
745+
bitArray_.andNot(other.bitArray_);
746+
}
747+
748+
/**
749+
* Helps identify if two BloomFilters may be unioned, intersected, or differenced.
713750
* @param other A BloomFilter to check for compatibility with this one
714751
* @return True if the filters are compatible, otherwise false
715752
*/

‎src/main/java/org/apache/datasketches/filters/bloomfilter/DirectBitArray.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -198,6 +198,21 @@ void invert() {
198198
wseg_.set(JAVA_LONG_UNALIGNED, NUM_BITS_OFFSET, numBitsSet_);
199199
}
200200

201+
@Override
202+
void andNot(final BitArray other) {
203+
if (getCapacity() != other.getCapacity()) {
204+
throw new SketchesArgumentException("Cannot andNot bit arrays with unequal lengths");
205+
}
206+
207+
numBitsSet_ = 0;
208+
for (int i = 0; i < dataLength_; ++i) {
209+
final long val = getLong(i) & ~other.getLong(i);
210+
numBitsSet_ += Long.bitCount(val);
211+
setLong(i, val);
212+
}
213+
wseg_.set(JAVA_LONG_UNALIGNED, NUM_BITS_OFFSET, numBitsSet_);
214+
}
215+
201216
@Override
202217
protected void setLong(final int arrayIndex, final long value) {
203218
wseg_.set(JAVA_LONG_UNALIGNED, DATA_OFFSET + (arrayIndex << 3), value);

‎src/main/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayR.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -155,6 +155,11 @@ void invert() {
155155
throw new SketchesReadOnlyException("Attempt to call invert() on read-only MemorySegment");
156156
}
157157

158+
@Override
159+
void andNot(final BitArray other) {
160+
throw new SketchesReadOnlyException("Attempt to call andNot() on read-only MemorySegment");
161+
}
162+
158163
@Override
159164
protected void setLong(final int arrayIndex, final long value) {
160165
throw new SketchesReadOnlyException("Attempt to call setLong() on read-only MemorySegment");

‎src/main/java/org/apache/datasketches/filters/bloomfilter/HeapBitArray.java‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -202,6 +202,22 @@ void invert() {
202202
}
203203
}
204204

205+
// applies logical AND-NOT (this &= ~other)
206+
@Override
207+
void andNot(final BitArray other) {
208+
if (getCapacity() != other.getCapacity()) {
209+
throw new SketchesArgumentException("Cannot andNot bit arrays with unequal lengths");
210+
}
211+
212+
numBitsSet_ = 0;
213+
for (int i = 0; i < data_.length; ++i) {
214+
final long val = data_[i] & ~other.getLong(i);
215+
numBitsSet_ += Long.bitCount(val);
216+
data_[i] = val;
217+
}
218+
isDirty_ = false;
219+
}
220+
205221
void writeToSegmentAsStream(final PositionalSegment posSeg) { //position = 16
206222
posSeg.setInt(data_.length);
207223
posSeg.setInt(0); // unused

‎src/test/java/org/apache/datasketches/filters/bloomfilter/BloomFilterTest.java‎

Lines changed: 67 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -180,7 +180,9 @@ public void basicFilterOperationsTest() {
180180
}
181181

182182
@Test
183+
@SuppressWarnings("deprecation")
183184
public void inversionTest() {
185+
// Deprecated path retained until invert() is removed; prefer difference().
184186
final long numBits = 8192;
185187
final int numHashes = 3;
186188

@@ -195,12 +197,12 @@ public void inversionTest() {
195197
bf.invert();
196198
assertEquals(bf.getBitsUsed(), numBits - numBitsSet);
197199

198-
// original items should be mostly not-present
200+
// inserted items are always absent after inversion (all their positions flipped to 0)
199201
int count = 0;
200202
for (int i = 0; i < n; ++i) {
201203
count += bf.query(Integer.toString(i)) ? 1 : 0;
202204
}
203-
assertTrue(count < (numBits / 10));
205+
assertEquals(count, 0);
204206

205207
// many other items should be present
206208
count = 0;
@@ -227,6 +229,7 @@ public void incompatibleSetOperationsTest() {
227229
// mismatched seed
228230
final BloomFilter bf4 = BloomFilterBuilder.createBySize(numBits, numHashes, bf1.getSeed() - 1);
229231
assertThrows(SketchesArgumentException.class, () -> bf1.union(bf4));
232+
assertThrows(SketchesArgumentException.class, () -> bf1.difference(bf4));
230233
}
231234

232235
@Test
@@ -290,6 +293,68 @@ public void basicIntersectionTest() {
290293
assertTrue(count < (numBits / 10)); // not being super strict
291294
}
292295

296+
@Test
297+
public void basicDifferenceTest() {
298+
final long numBits = 8192;
299+
final int numHashes = 5;
300+
301+
final BloomFilter left = BloomFilterBuilder.createBySize(numBits, numHashes);
302+
final BloomFilter right = BloomFilterBuilder.createBySize(numBits, numHashes, left.getSeed());
303+
304+
final int n = 1024;
305+
for (int i = 0; i < n; ++i) {
306+
left.queryAndUpdate(i);
307+
right.queryAndUpdate((n / 2) + i); // overlap [n/2, n)
308+
}
309+
310+
final long bitsBefore = left.getBitsUsed();
311+
left.difference(null); // no-op
312+
left.difference(right);
313+
314+
// items only in the right filter / overlap are excluded exactly
315+
for (int i = n / 2; i < (n + n / 2); ++i) {
316+
assertFalse(left.query(i), "item " + i + " should be excluded by difference");
317+
}
318+
assertTrue(left.getBitsUsed() <= bitsBefore);
319+
320+
// disjoint left-only items should mostly remain; allow for hash collisions with right
321+
int retained = 0;
322+
for (int i = 0; i < (n / 2); ++i) {
323+
retained += left.query(i) ? 1 : 0;
324+
}
325+
assertTrue(retained > (n / 4), "expected most left-only items retained, got " + retained);
326+
}
327+
328+
@Test
329+
public void differenceWithSelfClearsFilter() {
330+
final BloomFilter bf = BloomFilterBuilder.createBySize(4096, 4);
331+
for (int i = 0; i < 200; ++i) {
332+
bf.queryAndUpdate(i);
333+
}
334+
assertFalse(bf.isEmpty());
335+
final BloomFilter same = BloomFilter.heapify(MemorySegment.ofArray(bf.toByteArray()));
336+
bf.difference(same);
337+
assertTrue(bf.isEmpty());
338+
assertEquals(bf.getBitsUsed(), 0);
339+
assertFalse(bf.query(0));
340+
}
341+
342+
@Test
343+
public void differenceWithEmptyIsIdentity() {
344+
final BloomFilter left = BloomFilterBuilder.createBySize(4096, 4, 42L);
345+
left.queryAndUpdate("apple");
346+
left.queryAndUpdate("banana");
347+
final long bits = left.getBitsUsed();
348+
final byte[] before = left.toByteArray();
349+
350+
final BloomFilter empty = BloomFilterBuilder.createBySize(4096, 4, 42L);
351+
left.difference(empty);
352+
assertEquals(left.getBitsUsed(), bits);
353+
assertTrue(left.query("apple"));
354+
assertTrue(left.query("banana"));
355+
assertEquals(left.toByteArray(), before);
356+
}
357+
293358
@Test
294359
public void emptySerializationTest() {
295360
final long numBits = 32768;

‎src/test/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayRTest.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -167,5 +167,6 @@ public void checkInvalidMethods() {
167167
assertThrows(SketchesReadOnlyException.class, () -> dba.invert());
168168
assertThrows(SketchesReadOnlyException.class, () -> dba.intersect(hba));
169169
assertThrows(SketchesReadOnlyException.class, () -> dba.union(hba));
170+
assertThrows(SketchesReadOnlyException.class, () -> dba.andNot(hba));
170171
}
171172
}

‎src/test/java/org/apache/datasketches/filters/bloomfilter/DirectBitArrayTest.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -217,6 +217,7 @@ public void invalidUnionIntersectionTest() {
217217
final DirectBitArray dba = DirectBitArray.writableWrap(wseg, false);
218218
assertThrows(SketchesArgumentException.class, () -> dba.union(new HeapBitArray(64)));
219219
assertThrows(SketchesArgumentException.class, () -> dba.intersect(new HeapBitArray(512)));
220+
assertThrows(SketchesArgumentException.class, () -> dba.andNot(new HeapBitArray(512)));
220221
}
221222

222223
@Test
@@ -243,4 +244,29 @@ public void validUnionAndIntersectionTest() {
243244
ba3.union(ba2);
244245
assertEquals(ba3.getNumBitsSet(), (3 * n) / 2);
245246
}
247+
248+
@Test
249+
public void validAndNotTest() {
250+
final long numBits = 64;
251+
final int sizeBytes = (int) BitArray.getSerializedSizeBytes(64);
252+
final DirectBitArray ba1 = DirectBitArray.initialize(numBits, MemorySegment.ofArray(new byte[sizeBytes]));
253+
final DirectBitArray ba2 = DirectBitArray.initialize(numBits, MemorySegment.ofArray(new byte[sizeBytes]));
254+
255+
final int n = 10;
256+
for (int i = 0; i < n; ++i) {
257+
ba1.getAndSetBit(i);
258+
ba2.getAndSetBit(i + (n / 2));
259+
}
260+
assertEquals(ba1.getNumBitsSet(), n);
261+
assertEquals(ba2.getNumBitsSet(), n);
262+
263+
ba1.andNot(ba2);
264+
assertEquals(ba1.getNumBitsSet(), n / 2);
265+
for (int i = 0; i < (n / 2); ++i) {
266+
assertTrue(ba1.getBit(i));
267+
}
268+
for (int i = n / 2; i < n; ++i) {
269+
assertFalse(ba1.getBit(i));
270+
}
271+
}
246272
}

‎src/test/java/org/apache/datasketches/filters/bloomfilter/HeapBitArrayTest.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -147,6 +147,36 @@ public void validUnionAndIntersectionTest() {
147147
assertEquals(ba3.getNumBitsSet(), (3 * n) / 2);
148148
}
149149

150+
@Test(expectedExceptions = SketchesArgumentException.class)
151+
public void invalidAndNotTest() {
152+
final HeapBitArray ba = new HeapBitArray(128);
153+
ba.andNot(new HeapBitArray(64));
154+
}
155+
156+
@Test
157+
public void validAndNotTest() {
158+
final HeapBitArray ba1 = new HeapBitArray(64);
159+
final HeapBitArray ba2 = new HeapBitArray(64);
160+
161+
final int n = 10;
162+
for (int i = 0; i < n; ++i) {
163+
ba1.getAndSetBit(i);
164+
ba2.getAndSetBit(i + (n / 2));
165+
}
166+
assertEquals(ba1.getNumBitsSet(), n);
167+
assertEquals(ba2.getNumBitsSet(), n);
168+
169+
ba1.andNot(ba2);
170+
// bits [0, n/2) remain; bits [n/2, n) cleared
171+
assertEquals(ba1.getNumBitsSet(), n / 2);
172+
for (int i = 0; i < (n / 2); ++i) {
173+
assertTrue(ba1.getBit(i));
174+
}
175+
for (int i = n / 2; i < n; ++i) {
176+
assertFalse(ba1.getBit(i));
177+
}
178+
}
179+
150180
@Test
151181
public void serializeEmptyTest() {
152182
final HeapBitArray ba = new HeapBitArray(64);

0 commit comments

Comments
 (0)