[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[asfgit]

Github user asfgit closed the pull request at:

https://github.com/apache/spark/pull/16864


---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[Bcpoole]

Github user Bcpoole commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100624882
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilterImpl.java 
---
@@ -221,6 +221,49 @@ public BloomFilter mergeInPlace(BloomFilter other) 
throws IncompatibleMergeExcep
   }
 
   @Override
+  public double approxItems() {
+double m = bitSize();
+return (-m / numHashFunctions) * Math.log(1 - (bits.cardinality() / 
m));
--- End diff --

> Math is deprecated. Use math.

Assume you were thinking of Scala?


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[mengxr]

Github user mengxr commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100569750
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilter.java ---
@@ -81,6 +81,11 @@ int getVersionNumber() {
   public abstract long bitSize();
 
   /**
+   * Swamidass & Baldi (2007) approximation for number of items in a Bloom 
filter
--- End diff --

Please describe the method first and its properties (approximation error).  
Then put the reference in `@seealso` with a permanent link to the paper: 
https://dx.doi.org/10.1021%2Fci600526a


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[mengxr]

Github user mengxr commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100571446
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilter.java ---
@@ -148,6 +153,24 @@ int getVersionNumber() {
   public abstract boolean mightContainBinary(byte[] item);
 
   /**
+   * Returns a new Bloom filter of the union of two Bloom filters.
+   * Unlike mergeInplace, this will not cause a mutation.
+   * Callers must ensure the bloom filters are appropriately sized to 
avoid saturating them.
+   *
+   * @param other The bloom filter to union this bloom filter with.
+   * @throws IncompatibleUnionException if {@code isCompatible(other) == 
false}
+   */
+  public abstract BloomFilterImpl union(BloomFilter other) throws 
IncompatibleUnionException;
+
+  /**
+   * Swamidass & Baldi (2007) approximation for number of items in the 
intersection of two Bloom filters
--- End diff --

* Same here. Document the method first and then mention the reference.
* How is it different from intersecting two bloom filters and then estimate 
the number of items? Union might lead to larger approximation error.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[mengxr]

Github user mengxr commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100570007
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilter.java ---
@@ -81,6 +81,11 @@ int getVersionNumber() {
   public abstract long bitSize();
 
   /**
+   * Swamidass & Baldi (2007) approximation for number of items in a Bloom 
filter
+   */
+  public abstract double approxItems();
--- End diff --

It might be easier to keep it as double because the estimate could be out 
of bound if the bits are full.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[mengxr]

Github user mengxr commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100571673
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilterImpl.java 
---
@@ -221,6 +221,49 @@ public BloomFilter mergeInPlace(BloomFilter other) 
throws IncompatibleMergeExcep
   }
 
   @Override
+  public double approxItems() {
+double m = bitSize();
+return (-m / numHashFunctions) * Math.log(1 - (bits.cardinality() / 
m));
--- End diff --

* `Math` is deprecated. Use `math`.
* Please add a test when `bits` is full. This should return 
`Double.Infinity`.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[rxin]

Github user rxin commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100503141
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilter.java ---
@@ -81,6 +81,11 @@ int getVersionNumber() {
   public abstract long bitSize();
 
   /**
+   * Swamidass & Baldi (2007) approximation for number of items in a Bloom 
filter
+   */
+  public abstract double approxItems();
--- End diff --

yea but that would only be off by 1. I wouldn't worry about that since it 
is approximate anyway.



---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[Bcpoole]

Github user Bcpoole commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100385258
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilter.java ---
@@ -81,6 +81,11 @@ int getVersionNumber() {
   public abstract long bitSize();
 
   /**
+   * Swamidass & Baldi (2007) approximation for number of items in a Bloom 
filter
+   */
+  public abstract double approxItems();
--- End diff --

I was debating this due to possible rounding errors.


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[Bcpoole]

Github user Bcpoole commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100381372
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/IncompatibleUnionException.java
 ---
@@ -0,0 +1,24 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.util.sketch;
+
+public class IncompatibleUnionException extends Exception {
--- End diff --

In that case IncompatibleMergeException needs it too :)


---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[rxin]

Github user rxin commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100261227
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilter.java ---
@@ -81,6 +81,11 @@ int getVersionNumber() {
   public abstract long bitSize();
 
   /**
+   * Swamidass & Baldi (2007) approximation for number of items in a Bloom 
filter
+   */
+  public abstract double approxItems();
--- End diff --

shouldn't this return a long rather than a double?



---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[rxin]

Github user rxin commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100261151
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilter.java ---
@@ -148,6 +153,20 @@ int getVersionNumber() {
   public abstract boolean mightContainBinary(byte[] item);
 
   /**
+   * Returns a new Bloom filter of the union of two Bloom filters.
+   * Unlike mergeInplace, this will not cause a mutation.
+   * Callers must ensure the bloom filters are appropriately sized to 
avoid saturating them.
+   *
+   * @throws IncompatibleUnionException if either are null, different 
classes, or different size or number of hash functions
+   */
+  public abstract BloomFilterImpl createUnionBloomFilter(BloomFilter 
other) throws IncompatibleUnionException;
--- End diff --

how about just calling this union?



---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[rxin]

Github user rxin commented on a diff in the pull request:

https://github.com/apache/spark/pull/16864#discussion_r100261088
  
--- Diff: 
common/sketch/src/main/java/org/apache/spark/util/sketch/IncompatibleUnionException.java
 ---
@@ -0,0 +1,24 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.util.sketch;
+
+public class IncompatibleUnionException extends Exception {
--- End diff --

we need some javadoc ere.



---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org

[GitHub] spark pull request #16864: [SPARK-19527][Core] Approximate Size of Intersect...

[Bcpoole]

GitHub user Bcpoole opened a pull request:

https://github.com/apache/spark/pull/16864

[SPARK-19527][Core] Approximate Size of Intersection of Bloom Filters

**What changes were proposed in this pull request?**

Added functions to get the Swamidass & Baldi (2007) approximation for 
number of items in a Bloom filter and the intersections of two filters. Added 
an exception type IncompatibleUnionException mimicing 
IncompatibleMergeException. As needed for the intersection approximation, there 
is a function that create the union of two Bloom filters (no mutations).

**How was this patch tested?**

Manual Tests

You can merge this pull request into a Git repository by running:

$ git pull https://github.com/Bcpoole/spark 
approxItemsInBloomFilterIntersection

Alternatively you can review and apply these changes as the patch at:

https://github.com/apache/spark/pull/16864.patch

To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

This closes #16864


commit 7a3ad46ff86bd3d2d47f6a56bace1a0c4fd171c8
Author: Bcpoole 
Date:   2017-02-09T01:11:07Z

Swamidass & Baldi approx. items in intersection of two Bloom filters. Also 
function to create union (non-mutation) of two Bloom filters.

commit b9680c57b2f8b1d93c28884de9a7ebbe52505f6c
Author: Bcpoole 
Date:   2017-02-09T01:42:36Z

Changed createUnionBloomFilter & approxItemsInIntersection to be instance 
instead of static functions

commit 501ad7e22101b00862c0c77ef8c38e1b166d33a4
Author: Bcpoole 
Date:   2017-02-09T01:53:50Z

Updated abstract class to reflect changes in previous commit




---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---

-
To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org
For additional commands, e-mail: reviews-h...@spark.apache.org