From dev-return-1862-apmail-systemml-dev-archive=systemml.apache.org@systemml.apache.org Tue Jun 20 20:43:24 2017 Return-Path: X-Original-To: apmail-systemml-dev-archive@minotaur.apache.org Delivered-To: apmail-systemml-dev-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 3CD1B18EC6 for ; Tue, 20 Jun 2017 20:43:24 +0000 (UTC) Received: (qmail 13331 invoked by uid 500); 20 Jun 2017 20:43:19 -0000 Delivered-To: apmail-systemml-dev-archive@systemml.apache.org Received: (qmail 13281 invoked by uid 500); 20 Jun 2017 20:43:19 -0000 Mailing-List: contact dev-help@systemml.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@systemml.apache.org Delivered-To: mailing list dev@systemml.apache.org Received: (qmail 13269 invoked by uid 99); 20 Jun 2017 20:43:18 -0000 Received: from pnap-us-west-generic-nat.apache.org (HELO spamd4-us-west.apache.org) (209.188.14.142) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 20 Jun 2017 20:43:18 +0000 Received: from localhost (localhost [127.0.0.1]) by spamd4-us-west.apache.org (ASF Mail Server at spamd4-us-west.apache.org) with ESMTP id 6B16AC1232 for ; Tue, 20 Jun 2017 20:43:18 +0000 (UTC) X-Virus-Scanned: Debian amavisd-new at spamd4-us-west.apache.org X-Spam-Flag: NO X-Spam-Score: -0.395 X-Spam-Level: X-Spam-Status: No, score=-0.395 tagged_above=-999 required=6.31 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=2, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-2.796, RCVD_IN_SORBS_SPAM=0.5, URIBL_BLOCKED=0.001] autolearn=disabled Authentication-Results: spamd4-us-west.apache.org (amavisd-new); dkim=pass (1024-bit key) header.d=cs.washington.edu Received: from mx1-lw-us.apache.org ([10.40.0.8]) by localhost (spamd4-us-west.apache.org [10.40.0.11]) (amavisd-new, port 10024) with ESMTP id 6iC-V5YdBWcB for ; Tue, 20 Jun 2017 20:43:15 +0000 (UTC) Received: from mail-wr0-f180.google.com (mail-wr0-f180.google.com [209.85.128.180]) by mx1-lw-us.apache.org (ASF Mail Server at mx1-lw-us.apache.org) with ESMTPS id 6E7B65FBB8 for ; Tue, 20 Jun 2017 20:43:15 +0000 (UTC) Received: by mail-wr0-f180.google.com with SMTP id y25so67674003wrd.2 for ; Tue, 20 Jun 2017 13:43:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.washington.edu; s=goo201206; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=9tSdB+vuoJzjntkHD3qfQ/hgd7r9YnWfrXt303da+hU=; b=gbZ8oBzjIXAkaa8pEi1/VRig1xja7Cud1iItbnT0HjSJC25ZnNNAiTNH2OsOR0qgGE x94/HQ40Vlo6PKiHZ2lc1prfY4eAj+gaz3eE8fEcqy4y+qgOAU5pGour2R6n3EyA5ZOg I47umFq5IQ3Nq6y1SAqYedvEXdvFljYkB4tG0= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=9tSdB+vuoJzjntkHD3qfQ/hgd7r9YnWfrXt303da+hU=; b=XmKI0dj7q9j8VEA1GeoWrCgAHGg8NOcfLAPFroiX3MHYRSq4J16LvjYT7WkJ/A3Z5m TA/3fnhI804rszzfOQV651WgL018KehGfVERswqNzQGvMrWhczWZTm6mZ3ar2OSFhGac uDQHTWgLA0ADvQZ7L5Rhx3KISwV8BhTINnD67WGAbFB9TyaP+TpTVLTOCAYv2ZSqL654 TnSL7b1JYUGMS0wNpu2K/FXB9VGySnwt0gXRn/sGHJFwLXmwnK6RGqF2CsnkMZgVB1zC 0xBUdMCsX+ohg7dLNc4Du9urzm8OsvMYzoRbMp6vT8nsOR53qdMy2KbRzZXSX76DFhhu Zz8w== X-Gm-Message-State: AKS2vOy+GzsjiFdI47xK8BLJFYehnu7UP9GNMVor6sWK4rIQq0Mr1qGu SpxJI65FqTe8GgjC/RAdpmfUzQjjbd1V X-Received: by 10.223.183.20 with SMTP id l20mr22207187wre.154.1497991394264; Tue, 20 Jun 2017 13:43:14 -0700 (PDT) MIME-Version: 1.0 Received: by 10.223.138.148 with HTTP; Tue, 20 Jun 2017 13:42:53 -0700 (PDT) In-Reply-To: References: From: Dylan Hutchison Date: Tue, 20 Jun 2017 13:42:53 -0700 Message-ID: Subject: Re: Sparsity estimates for Matrix Multiplication To: dev@systemml.apache.org Content-Type: multipart/alternative; boundary="f40304388be4ee9c6105526a4c2d" --f40304388be4ee9c6105526a4c2d Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable In case it is helpful, this 2010 paper is my favorite for estimating the nnz of a matrix product with high confidence. The algorithm is much more involved than the simple SystemML calculation, because it looks at samples from the actual data. Here are some notes I have on the paper: There is a sketch algorithm [2] that gives a (1 + =CE=B5) approximation z= =CC=83 to z for any =CE=B5 > 4 / (z^.25) in O(m) time and with a bound on the number of I/Os. In relational algebra, this is estimating |=CF=80_{ik}( A(i, j) =E2=8B=88 B(j, k) )|. The idea behind the algorithm i= s finding, for some tuning parameter k that varies with z, the k-smallest value of a hash function h(i; k). The larger this value is, the more is and ks that match for a given j. Repeat this for all js. Different (i, k)s contribute to different entries in the result matrix and have different hash values. A sketch for this algorithm can be incrementally maintained via independent samples on is and ks. Computing the z=CC=83 esti= mate from the sample takes o(n) time for large enough z. The larger z is, the smaller a sample size we need. (Need large samples for small z.) (Everything above assumes the zero product property and zero-sum-free). On Tue, Jun 20, 2017 at 12:06 PM, Nakul Jindal wrote: > Hi, > > There is code in systemml to =E2=80=9Cestimate=E2=80=9D the output sparsi= ty of a matrix > multiplication operation between two sparse matrices. > Is there a citation for this? If not, have we done any tests to figure ou= t > how good these estimates are? > https://github.com/nakul02/systemml/blob/df8d4a63d8d09cae94b > 6ca2634e31da554302c72/src/main/java/org/apache/sysml/ > hops/OptimizerUtils.java#L944-L953 > > Thanks, > Nakul > --f40304388be4ee9c6105526a4c2d--