Visitar URL original
Merge pull request #778 from MaxFreedomPollard/fix/theta-exactly-equa… · apache/datasketches-java@665ffa2 · GitHub
Skip to content

Commit 665ffa2

Browse files
leerholeerho
authored
Merge pull request #778 from MaxFreedomPollard/fix/theta-exactly-equal-bounds
Fix JaccardSimilarity.exactlyEqual throwing for small theta sketches
2 parents 6f07e26 + fca1388 commit 665ffa2

2 files changed

Lines changed: 58 additions & 42 deletions

File tree

‎src/main/java/org/apache/datasketches/theta/JaccardSimilarity.java‎

Lines changed: 47 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -61,28 +61,8 @@ public static double[] jaccard(final ThetaSketch sketchA, final ThetaSketch sket
6161
if (sketchA.isEmpty() && sketchB.isEmpty()) { return ONES.clone(); }
6262
if (sketchA.isEmpty() || sketchB.isEmpty()) { return ZEROS.clone(); }
6363

64-
final int countA = sketchA.getRetainedEntries(true);
65-
final int countB = sketchB.getRetainedEntries(true);
66-
67-
//Create the ThetaUnion
68-
final int minK = 1 << ThetaUtil.MIN_LG_NOM_LONGS;
69-
final int maxK = 1 << ThetaUtil.MAX_LG_NOM_LONGS;
70-
final int newK = max(min(ceilingPowerOf2(countA + countB), maxK), minK);
71-
final ThetaUnion union =
72-
ThetaSetOperation.builder().setNominalEntries(newK).buildUnion();
73-
union.union(sketchA);
74-
union.union(sketchB);
75-
final ThetaSketch unionAB = union.getResult(false, null);
76-
final long thetaLongUAB = unionAB.getThetaLong();
77-
final long thetaLongA = sketchA.getThetaLong();
78-
final long thetaLongB = sketchB.getThetaLong();
79-
final int countUAB = unionAB.getRetainedEntries(true);
80-
81-
//Check for identical data
82-
if (countUAB == countA && countUAB == countB
83-
&& thetaLongUAB == thetaLongA && thetaLongUAB == thetaLongB) {
84-
return ONES.clone();
85-
}
64+
final ThetaSketch unionAB = computeUnion(sketchA, sketchB);
65+
if (identicalSets(sketchA, sketchB, unionAB)) { return ONES.clone(); }
8666

8767
//Create the ThetaIntersection
8868
final ThetaIntersection inter = ThetaSetOperation.builder().buildIntersection();
@@ -100,6 +80,10 @@ public static double[] jaccard(final ThetaSketch sketchA, final ThetaSketch sket
10080
/**
10181
* Returns true if the two given sketches have exactly the same hash values and the same
10282
* theta values. Thus, they are equivalent.
83+
*
84+
* <p>Note: For very large pairs of sketches, where the configured nominal entries of the sketches
85+
* are 2^26, this method may return false even if the two sketches are equal.
86+
*
10387
* @param sketchA the given sketch A
10488
* @param sketchB the given sketch B
10589
* @return true if the two given sketches have exactly the same hash values and the same
@@ -112,26 +96,8 @@ public static boolean exactlyEqual(final ThetaSketch sketchA, final ThetaSketch
11296
if (sketchA.isEmpty() && sketchB.isEmpty()) { return true; }
11397
if (sketchA.isEmpty() || sketchB.isEmpty()) { return false; }
11498

115-
final int countA = sketchA.getRetainedEntries(true);
116-
final int countB = sketchB.getRetainedEntries(true);
117-
118-
//Create the ThetaUnion
119-
final ThetaUnion union =
120-
ThetaSetOperation.builder().setNominalEntries(ceilingPowerOf2(countA + countB)).buildUnion();
121-
union.union(sketchA);
122-
union.union(sketchB);
123-
final ThetaSketch unionAB = union.getResult();
124-
final long thetaLongUAB = unionAB.getThetaLong();
125-
final long thetaLongA = sketchA.getThetaLong();
126-
final long thetaLongB = sketchB.getThetaLong();
127-
final int countUAB = unionAB.getRetainedEntries(true);
128-
129-
//Check for identical counts and thetas
130-
if (countUAB == countA && countUAB == countB
131-
&& thetaLongUAB == thetaLongA && thetaLongUAB == thetaLongB) {
132-
return true;
133-
}
134-
return false;
99+
final ThetaSketch unionAB = computeUnion(sketchA, sketchB);
100+
return identicalSets(sketchA, sketchB, unionAB);
135101
}
136102

137103
/**
@@ -178,4 +144,43 @@ public static boolean dissimilarityTest(final ThetaSketch measured, final ThetaS
178144
return jRatioUB <= threshold;
179145
}
180146

147+
/**
148+
* Computes the union of the two given sketches. The union is sized to hold the retained entries
149+
* of both sketches, clamped to the legal range of nominal entries. The result is unordered,
150+
* because only its retained entries and theta are used.
151+
* @param sketchA the given sketch A
152+
* @param sketchB the given sketch B
153+
* @return the unordered union of sketch A and sketch B
154+
*/
155+
private static ThetaSketch computeUnion(final ThetaSketch sketchA, final ThetaSketch sketchB) {
156+
final int countA = sketchA.getRetainedEntries(true);
157+
final int countB = sketchB.getRetainedEntries(true);
158+
final int minK = 1 << ThetaUtil.MIN_LG_NOM_LONGS;
159+
final int maxK = 1 << ThetaUtil.MAX_LG_NOM_LONGS;
160+
final int newK = max(min(ceilingPowerOf2(countA + countB), maxK), minK);
161+
final ThetaUnion union =
162+
ThetaSetOperation.builder().setNominalEntries(newK).buildUnion();
163+
union.union(sketchA);
164+
union.union(sketchB);
165+
return union.getResult(false, null);
166+
}
167+
168+
/**
169+
* Returns true if the two given sketches and their union all have the same number of retained
170+
* entries and the same theta, which means the two sketches hold identical sets.
171+
* @param sketchA the given sketch A
172+
* @param sketchB the given sketch B
173+
* @param unionAB the union of sketch A and sketch B
174+
* @return true if the two given sketches hold identical sets
175+
*/
176+
private static boolean identicalSets(final ThetaSketch sketchA, final ThetaSketch sketchB,
177+
final ThetaSketch unionAB) {
178+
final int countUAB = unionAB.getRetainedEntries(true);
179+
final long thetaLongUAB = unionAB.getThetaLong();
180+
return countUAB == sketchA.getRetainedEntries(true)
181+
&& countUAB == sketchB.getRetainedEntries(true)
182+
&& thetaLongUAB == sketchA.getThetaLong()
183+
&& thetaLongUAB == sketchB.getThetaLong();
184+
}
185+
181186
}

‎src/test/java/org/apache/datasketches/theta/JaccardSimilarityTest.java‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -233,6 +233,17 @@ public void checkMinK() {
233233
println(result[0] + ", " + result[1] + ", " + result[2]);
234234
}
235235

236+
@Test
237+
public void checkMinKExactlyEqual() {
238+
UpdatableThetaSketch skA = UpdatableThetaSketch.builder().build(); //4096
239+
UpdatableThetaSketch skB = UpdatableThetaSketch.builder().build(); //4096
240+
skA.update(1);
241+
skB.update(1);
242+
assertTrue(exactlyEqual(skA, skB));
243+
skB.update(2);
244+
assertFalse(exactlyEqual(skA, skB));
245+
}
246+
236247
@Test
237248
public void printlnTest() {
238249
println("PRINTING: "+this.getClass().getName());

0 commit comments

Comments
 (0)