1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
// Two different structures:
// 1 -- The basic CM Sketch
// 2 -- The hierarchical CM Sketch: with log n levels, for range sums etc.
#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) > (y) ? (x) : (y))
typedef struct CM_type{
long long count;
int depth;
int width;
int ** counts;
unsigned int *hasha, *hashb;
} CM_type;
typedef struct CMF_type{ // shadow of above stucture with floats
double count;
int depth;
int width;
double ** counts;
unsigned int *hasha, *hashb;
} CMF_type;
extern CM_type * CM_Init(int, int, int);
extern CM_type * CM_Copy(CM_type *);
extern void CM_Destroy(CM_type *);
extern int CM_Size(CM_type *);
extern void CM_Update(CM_type *, unsigned int, int);
extern int CM_PointEst(CM_type *, unsigned int);
extern int CM_PointMed(CM_type *, unsigned int);
extern long long CM_InnerProd(CM_type *, CM_type *);
extern int CM_Residue(CM_type *, unsigned int *);
extern long long CM_F2Est(CM_type *);
extern CMF_type * CMF_Init(int, int, int);
extern CMF_type * CMF_Copy(CMF_type *);
extern void CMF_Destroy(CMF_type *);
extern int CMF_Size(CMF_type *);
extern void CMF_Update(CMF_type *, unsigned int, double);
extern double CMF_InnerProd(CMF_type *, CMF_type *);
extern double CMF_PointProd(CMF_type *, CMF_type *, unsigned int);
typedef struct CMH_type{
long long count;
int U; // size of the universe in bits
int gran; // granularity: eg 1, 4 or 8 bits
int levels; // function of U and gran
int freelim; // up to which level to keep exact counts
int depth;
int width;
int ** counts;
unsigned int **hasha, **hashb;
} CMH_type;
extern CMH_type * CMH_Init(int, int, int, int);
extern CMH_type * CMH_Copy(CMH_type *);
extern void CMH_Destroy(CMH_type *);
extern int CMH_Size(CMH_type *);
extern void CMH_Update(CMH_type *, unsigned int, int);
extern unsigned int * CMH_FindHH(CMH_type *, int);
extern int CMH_Rangesum(CMH_type *, long long, long long);
extern long long CMH_FindRange(CMH_type * cmh, int);
extern long long CMH_Quantile(CMH_type *cmh,float);
extern long long CMH_F2Est(CMH_type *);
|
