Baunsgaard commented on a change in pull request #909: URL: https://github.com/apache/systemml/pull/909#discussion_r433210181
########## File path: src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixEstimator.java ########## @@ -0,0 +1,249 @@ +/* + * 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.sysds.runtime.matrix.data; + +import java.util.Collections; +import java.util.HashSet; +import java.util.PriorityQueue; +import java.util.Set; + +import org.apache.commons.lang.NotImplementedException; +import org.apache.commons.logging.Log; +import org.apache.commons.logging.LogFactory; +import org.apache.log4j.Level; +import org.apache.log4j.Logger; +import org.apache.sysds.api.DMLException; +import org.apache.sysds.runtime.instructions.cp.AggregateUnaryCPInstruction.AUType; +import org.apache.sysds.runtime.matrix.operators.EstimatorOperator; +import org.apache.sysds.utils.Hash; +import org.apache.sysds.utils.Hash.HashType; + +/** + * This class contains estimation operations for matrix block. + */ +public class LibMatrixEstimator { + + // ------------------------------ + // Logging parameters: + // local debug flag + private static final boolean LOCAL_DEBUG = true; + // DEBUG/TRACE for details + private static final Level LOCAL_DEBUG_LEVEL = Level.DEBUG; + + private static final Log LOG = LogFactory.getLog(LibMatrixEstimator.class.getName()); + + static { + // for internal debugging only + if(LOCAL_DEBUG) { + Logger.getLogger("org.apache.sysds.runtime.matrix.data").setLevel(LOCAL_DEBUG_LEVEL); + } + } + // ------------------------------ + + // public enum EstimatorType { + // NUM_DISTINCT_COUNT, // Baseline naive implementation, iterate though, add to hashMap. + // NUM_DISTINCT_KMV, // K-Minimum Values algorithm. + // NUM_DISTINCT_HYPER_LOG_LOG // HyperLogLog algorithm. + // } + + static public int minimumSize = 64000; + + private LibMatrixEstimator() { + // Prevent instantiation via private constructor. + } + + /** + * Public method to count the number of distinct values inside a matrix. Depending on which EstimatorOperator + * selected it either gets the absolute number or a estimated value. + * + * TODO: support counting num distinct in rows, or columns axis. + * + * @param in the input matrix to count number distinct values in + * @param op the selected operator to use + * @return the distinct count + */ + public static int estimateDistinctValues(MatrixBlock in, EstimatorOperator op) { + // set output to correct size. + + // TODO: If the MatrixBlock type is CompressedMatrix, simply read the vaules from the ColGroups. + + if(op.hashType == HashType.ExpHash && op.operatorType == AUType.COUNT_DISTINCT_ESTIMATE_KMV) { + throw new DMLException( + "Invalid hashing configuration using " + HashType.ExpHash + " and " + AUType.COUNT_DISTINCT_ESTIMATE_KMV); + } + + if(op.operatorType == AUType.COUNT_DISTINCT_ESTIMATE_HYPER_LOG_LOG) + throw new NotImplementedException("HyperLogLog not implemented"); + + // Just use naive implementation if the size is small. + if(in.getNumRows() * in.getNumColumns() < minimumSize) { + return CountDistinctValuesNaive(in); Review comment: I had to choose something, and here 64k double values in an Hash Map equates to ~512k memory, which i found fair, and the approximate functions need some bigger number of elements before they begin to really shine. I have lowered it now to 1k. just like our block sizes, but the effects of this value has to be explored. (there probably is a good trade-off somewhere.) ---------------------------------------------------------------- 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. For queries about this service, please contact Infrastructure at: [email protected]
