You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by gs...@apache.org on 2025/05/12 18:31:57 UTC

(lucene) branch branch_10x updated: Fix FuzzySet#getEstimatedNumberUniqueValuesAllowingForCollisions to properly account for hashCount (#14614)

This is an automated email from the ASF dual-hosted git repository.

gsmiller pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/branch_10x by this push:
     new 057b0e2f9ae Fix FuzzySet#getEstimatedNumberUniqueValuesAllowingForCollisions to properly account for hashCount (#14614)
057b0e2f9ae is described below

commit 057b0e2f9aec8faabb7aae1f827627713c1b86cd
Author: Greg Miller <gs...@gmail.com>
AuthorDate: Mon May 12 11:24:25 2025 -0700

    Fix FuzzySet#getEstimatedNumberUniqueValuesAllowingForCollisions to properly account for hashCount (#14614)
---
 .../org/apache/lucene/codecs/bloom/FuzzySet.java    | 21 +++++++++++++++++----
 1 file changed, 17 insertions(+), 4 deletions(-)

diff --git a/lucene/codecs/src/java/org/apache/lucene/codecs/bloom/FuzzySet.java b/lucene/codecs/src/java/org/apache/lucene/codecs/bloom/FuzzySet.java
index 2f9e82a6c06..9e5b0d7fee7 100644
--- a/lucene/codecs/src/java/org/apache/lucene/codecs/bloom/FuzzySet.java
+++ b/lucene/codecs/src/java/org/apache/lucene/codecs/bloom/FuzzySet.java
@@ -269,18 +269,31 @@ public class FuzzySet implements Accountable {
   }
 
   public int getEstimatedUniqueValues() {
-    return getEstimatedNumberUniqueValuesAllowingForCollisions(bloomSize, filter.cardinality());
+    return getEstimatedNumberUniqueValuesAllowingForCollisions(
+        bloomSize, filter.cardinality(), hashCount);
   }
 
-  // Given a set size and a the number of set bits, produces an estimate of the number of unique
-  // values recorded
+  /**
+   * Given a set size and the number of set bits, produces an estimate of the number of unique
+   * values recorded (assuming a single hash function is used)
+   */
   public static int getEstimatedNumberUniqueValuesAllowingForCollisions(
       int setSize, int numRecordedBits) {
+    return getEstimatedNumberUniqueValuesAllowingForCollisions(setSize, numRecordedBits, 1);
+  }
+
+  /**
+   * Given a set size, the number of set bits and hash function count, produces an estimate of the
+   * number of unique values recorded
+   */
+  public static int getEstimatedNumberUniqueValuesAllowingForCollisions(
+      int setSize, int numRecordedBits, int hashCount) {
     double setSizeAsDouble = setSize;
     double numRecordedBitsAsDouble = numRecordedBits;
+    double hashCountAsDouble = hashCount;
     double saturation = numRecordedBitsAsDouble / setSizeAsDouble;
     double logInverseSaturation = Math.log(1 - saturation) * -1;
-    return (int) (setSizeAsDouble * logInverseSaturation);
+    return (int) (setSizeAsDouble * logInverseSaturation / hashCountAsDouble);
   }
 
   public float getTargetMaxSaturation() {