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