You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by "ibobak (via GitHub)" <gi...@apache.org> on 2024/09/10 16:42:01 UTC
[I] No method "IsMemberOf". An attempt to make it leads to failure. (datasketches-java)
ibobak opened a new issue, #599:
URL: https://github.com/apache/datasketches-java/issues/599
The code below implements a method "IsMemberOf" which is very much needed in big data. I can explain later why it is so important.
But there is a serious issue in it:
```
package org.example;
//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.theta.*;
// simplified file operations and no error handling for clarity
public class Main {
final static long SIZE = 7680;
final static long SIZE_LEFT = (long)(SIZE / 2);
final static long SIZE_RIGHT = SIZE_LEFT + SIZE;
/**
* this function generates two sketches with some overlap and serializes them into files
*/
public static void generateFiles() throws IOException {
// SIZE unique keys
UpdateSketch sketch1 = UpdateSketch.builder().setSeed(1).build();
for (int key = 0; key < SIZE; key++)
sketch1.update("item" + key);
FileOutputStream out1 = new FileOutputStream("ThetaSketch1.bin");
out1.write(sketch1.compact().toByteArray());
out1.close();
// SIZE unique keys
// the first SIZE unique keys overlap with sketch1
UpdateSketch sketch2 = UpdateSketch.builder().setSeed(1).build();
for (long key = SIZE_LEFT; key < SIZE_RIGHT; key++)
sketch2.update("item" + key);
FileOutputStream out2 = new FileOutputStream("ThetaSketch2.bin");
out2.write(sketch2.compact().toByteArray());
out2.close();
}
public static boolean IsMemberOf(String aMember, Sketch aSketch) {
UpdateSketch singleItemSketch = UpdateSketch.builder().setSeed(1).setNominalEntries(8192).build();
singleItemSketch.update(aMember);
Intersection intersection = SetOperation.builder().setSeed(1).setNominalEntries(8192).buildIntersection();
intersection.intersect(aSketch); // this will just create a sketch (nothing is there yet)
intersection.intersect(singleItemSketch); // intersect with the single item
// get the result of the intersection
Sketch result = intersection.getResult();
return (result.getEstimate() > 0);
}
public static void main(String[] args) throws Exception {
generateFiles();
FileInputStream in1 = new FileInputStream("ThetaSketch1.bin");
byte[] bytes1 = new byte[in1.available()];
in1.read(bytes1);
in1.close();
Sketch sketch1 = Sketches.wrapSketch(Memory.wrap(bytes1));
System.out.println(String.format("ZIZE = %d, sketch1 size = %f", SIZE, sketch1.getEstimate()));
int found1 = 0;
for (long key = 0; key < SIZE; key++)
if (IsMemberOf("item" + key, sketch1))
found1++;
System.out.println(String.format("\nIndividual checks for existing: found %d, must be found - %d", found1, SIZE));
}
}
```
It works OK with SIZE = 7680:
```
Individual checks for existing: found 7680, must be found - 7680
```
However, try to change 7680 to 7681 and re-run it again, and you will get this:
```
Individual checks for existing: found 4096, must be found - 7681
```
So, what is the problem? Why the intersection doesn't work any more?
Note: I tried to set different value in setNominalEntries, but this doesn't help.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] No method "IsMemberOf". An attempt to make it leads to failure. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #599:
URL: https://github.com/apache/datasketches-java/issues/599#issuecomment-2380285622
Closing this issue.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] No method "IsMemberOf". An attempt to make it leads to failure. (datasketches-java)
Posted by "ibobak (via GitHub)" <gi...@apache.org>.
ibobak commented on issue #599:
URL: https://github.com/apache/datasketches-java/issues/599#issuecomment-2341506261
Could you suggest a library which implements it? It is very preferably if it has a wrapper in HIVE/Spark, so that it can be used in this scenario:
1. Step 1: compute a "filter", "sketch", whatever on top of some_table.user_id column where date = yesterday.
2. Step 2: find all users in some_table with date=today which were NOT in yesterdays' set of users.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] No method "IsMemberOf". An attempt to make it leads to failure. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho commented on issue #599:
URL: https://github.com/apache/datasketches-java/issues/599#issuecomment-2380266808
You misunderstand the function of the theta sketches. Theta sketches count the **number** of unique identifiers within a stream (or set). The result you get from a Theta Sketch is a count. If you were to modify Step 2 above to:
> Step 2: find **the number of unique** users in some_table with date=today which were NOT in yesterdays' set of users.
Then A Theta Sketch could be used to give you a count estimate, which would be the set operation A-Not-B. But it would **not** give you the list of names!
To do literally what you asked you could use a Bloom or Quotient Filter as Alex suggested:
- Construct a Filter with all the users from yesterday's table.
- iterate over all the users in today's table and test each one against yesterdays Filter. Voila!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] No method "IsMemberOf". An attempt to make it leads to failure. (datasketches-java)
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #599:
URL: https://github.com/apache/datasketches-java/issues/599#issuecomment-2341471044
Theta sketch cannot be used like this for approximate membership.
There are different algorithms for this such as Bloom Filter and Quotient Filter.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] No method "IsMemberOf". An attempt to make it leads to failure. (datasketches-java)
Posted by "leerho (via GitHub)" <gi...@apache.org>.
leerho closed issue #599: No method "IsMemberOf". An attempt to make it leads to failure.
URL: https://github.com/apache/datasketches-java/issues/599
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] No method "IsMemberOf". An attempt to make it leads to failure. (datasketches-java)
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #599:
URL: https://github.com/apache/datasketches-java/issues/599#issuecomment-2341508774
https://github.com/apache/datasketches-java/tree/master/src/main/java/org/apache/datasketches/filters/bloomfilter
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org