1 /* 2 * hyperloglog.h 3 * 4 * A simple HyperLogLog cardinality estimator implementation 5 * 6 * Portions Copyright (c) 2014-2021, PostgreSQL Global Development Group 7 * 8 * Based on Hideaki Ohno's C++ implementation. The copyright terms of Ohno's 9 * original version (the MIT license) follow. 10 * 11 * src/include/lib/hyperloglog.h 12 */ 13 14 /* 15 * Copyright (c) 2013 Hideaki Ohno <hide.o.j55{at}gmail.com> 16 * 17 * Permission is hereby granted, free of charge, to any person obtaining a copy 18 * of this software and associated documentation files (the 'Software'), to 19 * deal in the Software without restriction, including without limitation the 20 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 21 * sell copies of the Software, and to permit persons to whom the Software is 22 * furnished to do so, subject to the following conditions: 23 * 24 * The above copyright notice and this permission notice shall be included in 25 * all copies or substantial portions of the Software. 26 * 27 * THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 28 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 29 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 30 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 31 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 32 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 33 * IN THE SOFTWARE. 34 */ 35 36 #ifndef HYPERLOGLOG_H 37 #define HYPERLOGLOG_H 38 39 /* 40 * HyperLogLog is an approximate technique for computing the number of distinct 41 * entries in a set. Importantly, it does this by using a fixed amount of 42 * memory. See the 2007 paper "HyperLogLog: the analysis of a near-optimal 43 * cardinality estimation algorithm" for more. 44 * 45 * hyperLogLogState 46 * 47 * registerWidth register width, in bits ("k") 48 * nRegisters number of registers 49 * alphaMM alpha * m ^ 2 (see initHyperLogLog()) 50 * hashesArr array of hashes 51 * arrSize size of hashesArr 52 */ 53 typedef struct hyperLogLogState 54 { 55 uint8 registerWidth; 56 Size nRegisters; 57 double alphaMM; 58 uint8 *hashesArr; 59 Size arrSize; 60 } hyperLogLogState; 61 62 extern void initHyperLogLog(hyperLogLogState *cState, uint8 bwidth); 63 extern void initHyperLogLogError(hyperLogLogState *cState, double error); 64 extern void addHyperLogLog(hyperLogLogState *cState, uint32 hash); 65 extern double estimateHyperLogLog(hyperLogLogState *cState); 66 extern void freeHyperLogLog(hyperLogLogState *cState); 67 68 #endif /* HYPERLOGLOG_H */ 69