mboehm7 commented on a change in pull request #909: URL: https://github.com/apache/systemml/pull/909#discussion_r433479211
########## 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); + } + + switch(op.operatorType) { + case COUNT_DISTINCT: + return CountDistinctValuesNaive(in); + case COUNT_DISTINCT_ESTIMATE_KMV: + return CountDistinctValuesKVM(in, op); + case COUNT_DISTINCT_ESTIMATE_HYPER_LOG_LOG: + return CountDistinctHyperLogLog(in); + default: + throw new DMLException("Invalid or not implemented Estimator Type"); + } + } + + /** + * Naive implementation of counting Distinct values. Benefit Precise, but Uses memory, on the scale of input. + * + * @param in the input matrix to count number distinct values in + * @return the distinct count + */ + private static int CountDistinctValuesNaive(MatrixBlock in) { + // Make a hash set to contain all the distinct. + // Memory usage scale linear with number of distinct values. + + Set<Double> distinct = new HashSet<Double>(); + + for(int c = 0; c < in.getNumColumns(); c++) { + for(int r = 0; r < in.getNumRows(); r++) { + distinct.add(in.getValue(r, c)); Review comment: no, allocating a vector in the number of celles would be even slower than iterating over all cells. The important this is to be in the number of non-zeros for sparse matrices. ---------------------------------------------------------------- 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]
