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() {