~ubuntu-branches/ubuntu/raring/ntop/raring : revision 18

1

/********************************************************************

2

Count-Min Sketches

3

4

G. Cormode 2003,2004

4

G. Cormode 2003,2004, 2010, 2012

5

6

Updated: 2004-06 Added a floating point sketch and support for

6

Updated: 2004-06 Added a floating point sketch and support for

7

inner product point estimation

8

Initial version: 2003-12

9

10

This work is licensed under the Creative Commons

11

Attribution-NonCommercial License. To view a copy of this license,

12

visit http://creativecommons.org/licenses/by-nc/1.0/ or send a letter

13

to Creative Commons, 559 Nathan Abbott Way, Stanford, California

14

94305, USA.

10

11

This program is free software; you can redistribute it and/or modify

12

it under the terms of the GNU General Public License as published by

13

the Free Software Foundation; either version 2 of the License, or

14

(at your option) any later version.

15

16

This program is distributed in the hope that it will be useful,

17

but WITHOUT ANY WARRANTY; without even the implied warranty of

18

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

19

GNU General Public License for more details.

20

21

You should have received a copy of the GNU General Public License along

22

with this program; if not, write to the Free Software Foundation, Inc.,

23

51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

15

24

*********************************************************************/

16

25

17

26

#include <stdlib.h>

27

#include "prng.h"

18

28

#include "countmin.h"

19

29

20

30

#define min(x,y) ((x) < (y) ? (x) : (y))

23

33

double eps; /* 1+epsilon = approximation factor */

24

34

double delta; /* probability of failure */

25

35

26

//int bits=32;

27

28

36

/************************************************************************/

29

37

/* Routines to support Count-Min sketches */

30

38

/************************************************************************/

36

44

prng_type * prng;

37

45

38

46

cm=(CM_type *) malloc(sizeof(CM_type));

39

prng=prng_Init(-abs(seed),2);

47

prng=prng_Init(-abs(seed),2);

40

48

// initialize the generator to pick the hash functions

41

49

42

50

if (cm && prng)

44

52

cm->depth=depth;

45

53

cm->width=width;

46

54

cm->count=0;

47

cm->prng = prng; /* L. Deri */

48

55

cm->counts=(int **)calloc(sizeof(int *),cm->depth);

49

56

cm->counts[0]=(int *)calloc(sizeof(int), cm->depth*cm->width);

50

57

cm->hasha=(unsigned int *)calloc(sizeof(unsigned int),cm->depth);

61

68

}

62

69

else cm=NULL;

63

70

}

71

if (prng)

72

prng_Destroy(prng);

64

73

return cm;

65

74

}

66

75

105

114

}

106

115

if (cm->hasha) free(cm->hasha); cm->hasha=NULL;

107

116

if (cm->hashb) free(cm->hashb); cm->hashb=NULL;

108

prng_Destroy(cm->prng); /* L.Deri */

109

117

free(cm); cm=NULL;

110

118

}

111

119

187

195

return 1;

188

196

}

189

197

190

int CM_InnerProd(CM_type * cm1, CM_type * cm2)

198

long long CM_InnerProd(CM_type * cm1, CM_type * cm2)

191

199

{ // Estimate the inner product of two vectors by comparing their sketches

192

int i,j, tmp, result;

200

int i,j;

201

long long result, tmp;

193

202

194

203

result=0;

195

204

if (CM_Compatible(cm1,cm2))

207

216

return result;

208

217

}

209

218

219

#if 0

220

long long CM_F2Est(CM_type * cm)

221

{ // Estimate the second frequency moment of the stream

222

int i,j;

223

long long result, tmp, *ans;

224

225

if (!cm) return 0;

226

ans=(long long *) calloc(1+cm->depth,sizeof(long long));

227

228

for (j=0;j<cm->depth;j++)

229

{

230

result=0;

231

for (i=0;i<cm->width;i+=2)

232

{

233

tmp=(cm->counts[j][i]-cm->counts[j][i+1]);

234

result+=tmp*tmp;

235

}

236

ans[j+1]=result;

237

}

238

result=LLMedSelect((cm->depth+1)/2,cm->depth,ans);

239

return result;

240

}

241

#endif

242

210

243

int CM_Residue(CM_type * cm, unsigned int * Q)

211

244

{

212

// CM_Residue computes the sum of everything left after the points

245

// CM_Residue computes the sum of everything left after the points

213

246

// from Q have been removed

214

247

// Q is a list of points, where Q[0] gives the length of the list

215

248

224

257

nextest=0;

225

258

for (i=0;i<cm->width;i++)

226

259

bitmap[i]=0;

227

for (i=1;i<Q[0];i++)

260

for (i=1;i<(int) Q[0];i++)

228

261

bitmap[hash31(cm->hasha[j],cm->hashb[j],Q[i]) % cm->width]=1;

229

262

for (i=0;i<cm->width;i++)

230

263

if (bitmap[i]==0) nextest+=cm->counts[j][i];

245

278

246

279

cm=(CMF_type *) malloc(sizeof(CMF_type));

247

280

248

prng=prng_Init(-abs(seed),2);

281

prng=prng_Init(-abs(seed),2);

249

282

// initialize the generator to pick the hash functions

250

283

251

284

if (cm && prng)

269

302

}

270

303

else cm=NULL;

271

304

}

305

if (prng)

306

prng_Destroy(prng);

272

307

return cm;

273

308

}

274

309

311

346

free(cm->counts);

312

347

cm->counts=NULL;

313

348

}

314

315

316

349

if (cm->hasha) free(cm->hasha); cm->hasha=NULL;

317

350

if (cm->hashb) free(cm->hashb); cm->hashb=NULL;

318

351

free(cm); cm=NULL;

339

372

// this can be done more efficiently if the width is a power of two

340

373

}

341

374

342

int CMF_PointEst(CMF_type * cm, unsigned int query)

375

double CMF_PointEst(CMF_type * cm, unsigned int query)

343

376

{

344

377

// return an estimate of the count of an item by taking the minimum

345

int j, ans;

378

int j;

379

double ans=0.;

346

380

347

381

if (!cm) return 0;

348

382

ans=cm->counts[0][hash31(cm->hasha[0],cm->hashb[0],query) % cm->width];

380

414

{

381

415

loc=hash31(cm1->hasha[j],cm1->hashb[j],query) % cm1->width;

382

416

tmp=cm1->counts[j][loc]*cm2->counts[j][loc];

383

ans=min(ans,tmp);

417

ans=min(ans,tmp);

384

418

}

385

419

}

386

420

return (ans);

387

421

}

388

422

389

423

double CMF_InnerProd(CMF_type * cm1, CMF_type * cm2)

390

424

{ // Estimate the inner product of two vectors by comparing their sketches

391

425

int i,j;

413

447

414

448

CMH_type * CMH_Init(int width, int depth, int U, int gran)

415

449

{

416

// initialize a hierarchical set of sketches for range queries

450

// initialize a hierarchical set of sketches for range queries

417

451

// heavy hitters or quantiles

418

452

419

453

CMH_type * cmh;

424

458

// U is the log the size of the universe in bits

425

459

426

460

if (gran>U || gran<1) return(NULL);

427

// gran is the granularity to look at the universe in

461

// gran is the granularity to look at the universe in

428

462

// check that the parameters make sense...

429

463

430

cmh=(CMH_type *) malloc(sizeof(CMH_type));

464

cmh=(CMH_type *) calloc(1,sizeof(CMH_type));

431

465

432

466

prng=prng_Init(-12784,2);

433

467

// initialize the generator for picking the hash functions

441

475

cmh->gran=gran;

442

476

cmh->levels=(int) ceil(((float) U)/((float) gran));

443

477

for (j=0;j<cmh->levels;j++)

444

if (1<<(cmh->gran*j) <= cmh->depth*cmh->width)

478

if ((long long) 1<<(cmh->gran*j) <= cmh->depth*cmh->width)

445

479

cmh->freelim=j;

446

480

//find the level up to which it is cheaper to keep exact counts

447

481

cmh->freelim=cmh->levels-cmh->freelim;

448

482

449

483

cmh->counts=(int **) calloc(sizeof(int *), 1+cmh->levels);

450

484

cmh->hasha=(unsigned int **)calloc(sizeof(unsigned int *),1+cmh->levels);

451

485

cmh->hashb=(unsigned int **)calloc(sizeof(unsigned int *),1+cmh->levels);

454

488

{

455

489

if (i>=cmh->freelim)

456

490

{ // allocate space for representing things exactly at high levels

457

cmh->counts[i]=calloc(1<<(cmh->gran*j),sizeof(int));

491

cmh->counts[i]=(int *) calloc(1<<(cmh->gran*j),sizeof(int));

458

492

j++;

459

493

cmh->hasha[i]=NULL;

460

494

cmh->hashb[i]=NULL;

461

495

}

462

else

496

else

463

497

{ // allocate space for a sketch

464

498

cmh->counts[i]=(int *)calloc(sizeof(int), cmh->depth*cmh->width);

465

499

cmh->hasha[i]=(unsigned int *)

476

510

}

477

511

}

478

512

}

513

if (prng)

514

prng_Destroy(prng);

479

515

return cmh;

480

516

}

481

517

482

518

void CMH_Destroy(CMH_type * cmh)

483

{ // free up the space

519

{ // free up the space

484

520

int i;

485

521

if (!cmh) return;

486

522

for (i=0;i<cmh->levels;i++)

489

525

{

490

526

free(cmh->counts[i]);

491

527

}

492

else

528

else

493

529

{

494

530

free(cmh->hasha[i]);

495

531

free(cmh->hashb[i]);

513

549

{

514

550

offset=0;

515

551

if (i>=cmh->freelim)

516

{

552

{ // level 0 = leaves, higher levels = internal nodes

517

553

cmh->counts[i][item]+=diff;

518

// keep exact counts at high levels in the hierarchy

554

// keep exact counts at high levels in the hierarchy

519

555

}

520

556

else

521

557

for (j=0;j<cmh->depth;j++)

522

558

{

523

cmh->counts[i][(hash31(cmh->hasha[i][j],cmh->hashb[i][j],item)

559

cmh->counts[i][(hash31(cmh->hasha[i][j],cmh->hashb[i][j],item)

524

560

% cmh->width) + offset]+=diff;

525

561

// this can be done more efficiently if the width is a power of two

526

562

offset+=cmh->width;

545

581

return(admin + hashes + counts);

546

582

}

547

583

548

int CMH_count(CMH_type * cmh, int depth, int item)

584

int CMH_count(CMH_type * cmh, int depth, unsigned int item)

549

585

{

550

586

// return an estimate of item at level depth

551

587

561

597

// else, use the appropriate sketch to make an estimate

562

598

offset=0;

563

599

estimate=cmh->counts[depth][(hash31(cmh->hasha[depth][0],

564

cmh->hashb[depth][0],item)

600

cmh->hashb[depth][0],item)

565

601

% cmh->width) + offset];

566

602

for (j=1;j<cmh->depth;j++)

567

603

{

568

604

offset+=cmh->width;

569

605

estimate=min(estimate,

570

606

cmh->counts[depth][(hash31(cmh->hasha[depth][j],

571

cmh->hashb[depth][j],item)

607

cmh->hashb[depth][j],item)

572

608

% cmh->width) + offset]);

573

609

}

574

610

return(estimate);

575

611

}

576

612

577

void CMH_recursive(CMH_type * cmh, int depth, int start,

613

void CMH_recursive(CMH_type * cmh, int depth, int start,

578

614

int thresh, unsigned int * results)

579

615

{

580

// for finding heavy hitters, recursively descend looking

616

// for finding heavy hitters, recursively descend looking

581

617

// for ranges that exceed the threshold

582

618

583

619

int i;

586

622

int itemshift;

587

623

588

624

estcount=CMH_count(cmh,depth,start);

589

if (estcount>=thresh)

590

{

625

if (estcount>=thresh)

626

{

591

627

if (depth==0)

592

628

{

593

if (results[0]<cmh->width)

629

if (results[0]<(unsigned int) cmh->width)

594

630

{

595

631

results[0]++;

596

632

results[results[0]]=start;

607

643

}

608

644

}

609

645

610

int * CMH_FindHH(CMH_type * cmh, int thresh)

646

unsigned int * CMH_FindHH(CMH_type * cmh, int thresh)

611

647

{ // find all items whose estimated count is greater than phi n

612

648

613

649

unsigned int * results;

618

654

return(results);

619

655

}

620

656

621

int CMH_Rangesum(CMH_type * cmh, int start, int end)

657

int CMH_Rangesum(CMH_type * cmh, long long start, long long end)

622

658

{

623

// compute a range sum:

659

// compute a range sum:

624

660

// start at bottom level

625

661

// compute any estimates needed at each level

626

662

// work upwards

627

663

628

int leftend,rightend,i,depth, result, topend;

664

int depth, result;

665

long long range, leftend, rightend;

666

long long topend, i;

629

667

630

topend=1<<cmh->U;

668

topend=((long long) 1)<<cmh->U;

631

669

end=min(topend,end);

632

if ((end>topend) && (start==0))

670

if ((end>topend) && (start==0)) {

633

671

return cmh->count;

672

}

634

673

635

674

end+=1; // adjust for end effects

636

675

result=0;

637

676

for (depth=0;depth<=cmh->levels;depth++)

638

677

{

639

678

if (start==end) break;

640

if ((end-start+1)<(1<<cmh->gran))

641

{ // at the highest level, avoid overcounting

679

range=(end-start+1);

680

if ((unsigned int) (end-start+1)<(((unsigned int) 1)<<cmh->gran))

681

{ // if only a few nodes to probe at this level, probe them all

642

682

for (i=start;i<end;i++)

643

683

result+=CMH_count(cmh,depth,i);

644

684

break;

646

686

else

647

687

{ // figure out what needs to be done at each end

648

688

leftend=(((start>>cmh->gran)+1)<<cmh->gran) - start;

689

if (leftend>= 1<<cmh->gran) leftend=0;

649

690

rightend=(end)-((end>>cmh->gran)<<cmh->gran);

650

691

if ((leftend>0) && (start<end))

651

692

for (i=0;i<leftend;i++)

665

706

return result;

666

707

}

667

708

668

int CMH_FindRange(CMH_type * cmh, int sum)

709

long long CMH_FindRange(CMH_type * cmh, int sum)

669

710

{

670

unsigned long low, high, mid=0, est;

671

int i;

711

long long low, high, mid=0;

712

int i, est=0;

672

713

// find a range starting from zero that adds up to sum

673

714

674

715

if (cmh->count<sum) return 1<<(cmh->U);

675

716

low=0;

676

high=1<<cmh->U;

717

high=((long long) 1)<<cmh->U;

718

677

719

for (i=0;i<cmh->U;i++)

678

720

{

679

721

mid=(low+high)/2;

680

est=CMH_Rangesum(cmh,0,mid);

722

est=CMH_Rangesum(cmh,0,(unsigned int) mid);

681

723

if (est>sum)

682

724

high=mid;

683

725

else

687

729

688

730

}

689

731

690

int CMH_AltFindRange(CMH_type * cmh, int sum)

732

long long CMH_AltFindRange(CMH_type * cmh, int sum)

691

733

{

692

unsigned long low, high, mid=0, est, top;

693

int i;

734

long long low, high, mid=0,top;

735

int i, est=0;

694

736

// find a range starting from the right hand side that adds up to sum

695

737

696

738

if (cmh->count<sum) return 1<<(cmh->U);

697

739

low=0;

698

top=1<<cmh->U;

740

top=((long long) 1)<<cmh->U;

699

741

high=top;

700

for (i=0;i<cmh->U;i++)

701

{

742

for (i=0;i<cmh->U;i++) {

702

743

mid=(low+high)/2;

703

744

est=CMH_Rangesum(cmh,mid,top);

704

745

if (est<sum)

710

751

711

752

}

712

753

713

int CMH_Quantile(CMH_type * cmh, float frac)

754

long long CMH_Quantile(CMH_type * cmh, float frac)

714

755

{

715

756

// find a quantile by doing the appropriate range search

716

757

if (frac<0) return 0;

717

if (frac>1)

758

if (frac>1)

718

759

return 1<<cmh->U;

719

return ((CMH_FindRange(cmh,cmh->count*frac)+

720

CMH_AltFindRange(cmh,cmh->count*(1-frac)))/2);

760

return ((CMH_FindRange(cmh,(long long) (cmh->count*frac))+

761

CMH_AltFindRange(cmh,(long long) (cmh->count*(1-frac))))/2);

721

762

// each result gives a lower/upper bound on the location of the quantile

722

763

// with high probability, these will be close: only a small number of values

723

// will be between the estimates.

764

// will be between the estimates.

724

765

}

725

766

726

767

long long CMH_F2Est(CMH_type * cmh)