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:24:31 UTC
(lucene) branch main 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 main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 36b3577c17a Fix FuzzySet#getEstimatedNumberUniqueValuesAllowingForCollisions to properly account for hashCount (#14614)
36b3577c17a is described below
commit 36b3577c17a52b2d9ae21d5976141e2da77cfab3
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 1aeeea49c4a..f41db6fb995 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
@@ -268,18 +268,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() {