You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by al...@apache.org on 2024/07/15 23:44:02 UTC
(datasketches-java) branch quotient-filter updated: implemented merge
This is an automated email from the ASF dual-hosted git repository.
alsay pushed a commit to branch quotient-filter
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
The following commit(s) were added to refs/heads/quotient-filter by this push:
new ffc9bbc2 implemented merge
ffc9bbc2 is described below
commit ffc9bbc2a5e2e28c0ef0a0ff72041a03625b21c3
Author: AlexanderSaydakov <Al...@users.noreply.github.com>
AuthorDate: Mon Jul 15 16:43:56 2024 -0700
implemented merge
---
.../filters/quotientfilter/QuotientFilter.java | 53 +++++++++++++++------
.../filters/quotientfilter/QuotientFilterTest.java | 54 ++++++++++++++++++++++
2 files changed, 94 insertions(+), 13 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/filters/quotientfilter/QuotientFilter.java b/src/main/java/org/apache/datasketches/filters/quotientfilter/QuotientFilter.java
index 7a860f85..cbee5c64 100644
--- a/src/main/java/org/apache/datasketches/filters/quotientfilter/QuotientFilter.java
+++ b/src/main/java/org/apache/datasketches/filters/quotientfilter/QuotientFilter.java
@@ -25,6 +25,7 @@ import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
+import org.apache.datasketches.common.SketchesArgumentException;
import org.apache.datasketches.common.SketchesException;
import org.apache.datasketches.filters.common.BitArray;
import org.apache.datasketches.filters.common.HeapBitArray;
@@ -83,12 +84,6 @@ public class QuotientFilter extends Filter {
return numFingerprintBits_;
}
-// QuotientFilter(final int powerOfTwo, final int numBitsPerEntry, final BitArray bitArray) {
-// powerOfTwoSize_ = powerOfTwo;
-// numBitsPerEntry_ = numBitsPerEntry;
-// bitArray_ = bitArray;
-// }
-
void expand() {
if (getFingerprintLength() < 2) throw new SketchesException("for expansion value must have at least 2 bits");
final QuotientFilter other = new QuotientFilter(lgQ_ + 1, numFingerprintBits_ - 1, loadFactor_);
@@ -150,6 +145,14 @@ public class QuotientFilter extends Filter {
return numEntries_ / (double) getNumSlots();
}
+ public int getLgQ() {
+ return lgQ_;
+ }
+
+ public float getLoadFactor() {
+ return loadFactor_;
+ }
+
// returns the number of slots in the filter without the extension/buffer slots
public long getNumSlots() {
return 1L << lgQ_;
@@ -229,13 +232,14 @@ public class QuotientFilter extends Filter {
public void printFilterSummary() {
final long slots = getNumSlots();
final long numBits = slots * getNumBitsPerEntry();
- System.out.println("slots: " + slots);
- System.out.println("bits: " + numBits);
- System.out.println("bits/entry: " + numBits / (double)numEntries_);
- System.out.println("FP length: " + getFingerprintLength());
- System.out.println("entries: " + numEntries_);
- System.out.println("expansions: " + numExpansions_);
- System.out.println("load: " + numEntries_ / (double)(slots));
+ System.out.println("lgQ: " + lgQ_);
+ System.out.println("FP length: " + getFingerprintLength());
+ System.out.println("load factor: " + getLoadFactor());
+ System.out.println("bits: " + numBits);
+ System.out.println("bits/entry: " + numBits / (double)numEntries_);
+ System.out.println("entries: " + numEntries_);
+ System.out.println("expansions: " + numExpansions_);
+ System.out.println("load: " + numEntries_ / (double)(slots));
computeStatistics();
//System.out.println("num runs: \t\t" + num_runs);
//System.out.println("avg run length: \t" + avg_run_length);
@@ -632,4 +636,27 @@ public class QuotientFilter extends Filter {
avgClusterLength_ = sumClusterLengths / numClusters_;
}
+ public void merge(final QuotientFilter other) {
+ if (lgQ_ + numFingerprintBits_ != other.lgQ_ + other.numFingerprintBits_) {
+ throw new SketchesArgumentException("incompatible sketches in merge");
+ }
+ long i = 0;
+ if (!other.isSlotEmpty(i)) { i = other.findClusterStart(i); }
+
+ final Queue<Long> fifo = new LinkedList<Long>();
+ long count = 0;
+ while (count < other.numEntries_) {
+ if (!other.isSlotEmpty(i)) {
+ if (other.isOccupied(i)) { fifo.add(i); }
+ final long quotient = fifo.element();
+ final long fingerprint = other.getFingerprint(i);
+ final long hash = quotient << other.getFingerprintLength() | fingerprint;
+ System.out.println("q=" + quotient + ", fp=" + fingerprint + ", hash=" + hash);
+ _insert(hash);
+ count++;
+ }
+ i = (i + 1) & other.getSlotMask();
+ if (!fifo.isEmpty() && ! other.isContinuation(i)) { fifo.remove(); }
+ }
+ }
}
diff --git a/src/test/java/org/apache/datasketches/filters/quotientfilter/QuotientFilterTest.java b/src/test/java/org/apache/datasketches/filters/quotientfilter/QuotientFilterTest.java
index 00eb994a..e632744e 100644
--- a/src/test/java/org/apache/datasketches/filters/quotientfilter/QuotientFilterTest.java
+++ b/src/test/java/org/apache/datasketches/filters/quotientfilter/QuotientFilterTest.java
@@ -18,6 +18,7 @@
*/
package org.apache.datasketches.filters.quotientfilter;
+import org.apache.datasketches.common.SketchesArgumentException;
import org.testng.annotations.Test;
import static org.testng.Assert.assertTrue;
import static org.testng.Assert.assertEquals;
@@ -308,4 +309,57 @@ public class QuotientFilterTest {
assertTrue(positives < 6);
}
+ @Test
+ public void mergeEmpty() {
+ final QuotientFilter qf1 = new QuotientFilter(4, 3);
+ final QuotientFilter qf2 = new QuotientFilter(4, 3);
+ qf1.merge(qf2);
+
+ assertEquals(qf1.getLgQ(), 4);
+ assertEquals(qf1.getFingerprintLength(), 3);
+ assertEquals(qf1.getNumEntries(), 0);
+ }
+
+ @Test
+ public void merge() {
+ final QuotientFilter qf1 = new QuotientFilter(16, 13);
+ final QuotientFilter qf2 = new QuotientFilter(16, 13);
+ final int n = 50000;
+ for (int i = 0; i < n / 2; i++) {
+ qf1.insert(i);
+ qf1.insert(i + n / 2);
+ }
+ qf1.merge(qf2);
+
+ assertEquals(qf1.getNumExpansions(), 0);
+ assertTrue(qf1.getNumEntries() > n * 0.99); // allow a few hash collisions
+
+ // query the same keys
+ int positives = 0;
+ for (int i = 0; i < n; i++) { if (qf1.search(i)) { positives++; } }
+ assertEquals(positives, n);
+
+ // query novel keys
+ positives = 0;
+ for (int i = 0; i < n; i++) { if (qf1.search(i + n)) { positives++; } }
+ assertTrue(positives < 4);
+ }
+
+ @Test
+ public void mergeDifferentConfiguration() {
+ final QuotientFilter qf1 = new QuotientFilter(3, 4);
+ final QuotientFilter qf2 = new QuotientFilter(4, 3);
+ qf1.insert(4);
+ qf2.insert(4);
+ qf1.merge(qf2);
+ assertEquals(qf1.getNumEntries(), 1);
+ }
+
+ @Test(expectedExceptions = SketchesArgumentException.class)
+ public void mergeIncompatible() {
+ final QuotientFilter qf1 = new QuotientFilter(4, 4);
+ final QuotientFilter qf2 = new QuotientFilter(4, 3);
+ qf1.merge(qf2);
+ }
+
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org