Mailing-List: contact issues-help@flink.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@flink.apache.org
Date: Mon, 25 Sep 2017 16:49:00 +0000 (UTC)
From: "ASF GitHub Bot (JIRA)" <jira@apache.org>
To: issues@flink.apache.org
Message-ID: <JIRA.13095257.1502956394000.195075.1506358140239@Atlassian.JIRA>
In-Reply-To: <JIRA.13095257.1502956394000@Atlassian.JIRA>
References: <JIRA.13095257.1502956394000@Atlassian.JIRA> <JIRA.13095257.1502956394272@jira-lw-us.apache.org>
Subject: [jira] [Commented] (FLINK-7465) Add build-in BloomFilterCount on
 TableAPI&SQL
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
archived-at: Mon, 25 Sep 2017 16:49:06 -0000


    [ https://issues.apache.org/jira/browse/FLINK-7465?page=3Dcom.atlassian=
.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=3D1617=
9299#comment-16179299 ]=20

ASF GitHub Bot commented on FLINK-7465:
---------------------------------------

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

    https://github.com/apache/flink/pull/4652#discussion_r140832701
 =20
    --- Diff: flink-libraries/flink-table/src/main/java/org/apache/flink/ta=
ble/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 imp=
lied.
    + * See the License for the specific language governing permissions and
    + * limitations under the License.
    + */
    +
    +package org.apache.flink.table.runtime.functions.aggfunctions.cardinal=
ity;
    +
    +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 =3D 1.04/sqrt(m) where
    + * m =3D 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 corre=
ction function
    + * defined in the original paper.  Empirical evidence shows that the c=
orrection
    + * function causes more harm than good.
    + * </p>
    + */
    +public class HyperLogLog implements ICardinality, Serializable {
    --- End diff --
   =20
    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 p=
eople 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 so=
me 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 pr=
oportional to the number of elements to be added; the precise choice of k a=
nd the constant of proportionality of m are determined by the intended fals=
e 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 the=
se positions is 0, the element is definitely not in the set =E2=80=93 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 chanc=
e been set to 1 during the insertion of other elements, resulting in a fals=
e 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 bi=
t-array position containing 0. For this figure, m =3D 18 and k =3D 3. The s=
ketch 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/ap=
ache/hive/common/util/BloomFilter.java
> Hi [~fhueske] [~twalthr] I appreciated if you can give me some advice. :-=
)


--
This message was sent by Atlassian JIRA
(v6.4.14#64029)