flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (FLINK-7465) Add build-in BloomFilterCount on TableAPI&SQL
Date Mon, 25 Sep 2017 16:49:00 GMT

    [ https://issues.apache.org/jira/browse/FLINK-7465?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16179299#comment-16179299

ASF GitHub Bot commented on FLINK-7465:

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

    --- Diff: flink-libraries/flink-table/src/main/java/org/apache/flink/table/runtime/functions/aggfunctions/cardinality/HyperLogLog.java
    @@ -0,0 +1,333 @@
    + * 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.flink.table.runtime.functions.aggfunctions.cardinality;
    +import java.io.ByteArrayInputStream;
    +import java.io.ByteArrayOutputStream;
    +import java.io.DataInput;
    +import java.io.DataInputStream;
    +import java.io.DataOutput;
    +import java.io.DataOutputStream;
    +import java.io.Externalizable;
    +import java.io.IOException;
    +import java.io.ObjectInput;
    +import java.io.ObjectInputStream;
    +import java.io.ObjectOutput;
    +import java.io.Serializable;
    + * Java implementation of HyperLogLog (HLL) algorithm from this paper:
    + * <p/>
    + * http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
    + * <p/>
    + * HLL is an improved version of LogLog that is capable of estimating
    + * the cardinality of a set with accuracy = 1.04/sqrt(m) where
    + * m = 2^b.  So we can control accuracy vs space usage by increasing
    + * or decreasing b.
    + * <p/>
    + * The main benefit of using HLL over LL is that it only requires 64%
    + * of the space that LL does to get the same accuracy.
    + * <p/>
    + * <p>
    + * Note that this implementation does not include the long range correction function
    + * defined in the original paper.  Empirical evidence shows that the correction
    + * function causes more harm than good.
    + * </p>
    + */
    +public class HyperLogLog implements ICardinality, Serializable {
    --- End diff --
    I see this class is adapted from https://github.com/addthis/stream-lib. I think you should
comment that this class was adapted from the link, so people can track differences.

> Add build-in BloomFilterCount on TableAPI&SQL
> ---------------------------------------------
>                 Key: FLINK-7465
>                 URL: https://issues.apache.org/jira/browse/FLINK-7465
>             Project: Flink
>          Issue Type: Sub-task
>          Components: Table API & SQL
>            Reporter: sunjincheng
>            Assignee: sunjincheng
>         Attachments: bloomfilter.png
> In this JIRA. use BloomFilter to implement counting functions.
> BloomFilter Algorithm description:
> An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different
hash functions defined, each of which maps or hashes some set element to one of the m array
positions, generating a uniform random distribution. Typically, k is a constant, much smaller
than m, which is proportional to the number of elements to be added; the precise choice of
k and the constant of proportionality of m are determined by the intended false positive rate
of the filter.
> To add an element, feed it to each of the k hash functions to get k array positions.
Set the bits at all these positions to 1.
> To query for an element (test whether it is in the set), feed it to each of the k hash
functions to get k array positions. If any of the bits at these positions is 0, the element
is definitely not in the set – if it were, then all the bits would have been set to 1 when
it was inserted. If all are 1, then either the element is in the set, or the bits have by
chance been set to 1 during the insertion of other elements, resulting in a false positive.
> An example of a Bloom filter, representing the set {x, y, z}. The colored arrows show
the positions in the bit array that each set element is mapped to. The element w is not in
the set {x, y, z}, because it hashes to one bit-array position containing 0. For this figure,
m = 18 and k = 3. The sketch as follows:
> !bloomfilter.png!
> Reference:
> 1. https://en.wikipedia.org/wiki/Bloom_filter
> 2. https://github.com/apache/hive/blob/master/storage-api/src/java/org/apache/hive/common/util/BloomFilter.java
> Hi [~fhueske] [~twalthr] I appreciated if you can give me some advice. :-)

This message was sent by Atlassian JIRA

View raw message