Detailed Description

HyperPlot, Author: Sam Harnew, sam.h.nosp@m.arne.nosp@m.w@gma.nosp@m.il.c.nosp@m.om , Date: Dec 2015

HyperBinning is a binning scheme where each bin volume is defined by a HyperVolume.

Finding the correct bin number is quite a compuationally slow process if one has to loop over every bin and check if a HyperPoint falls within that bin volume. It's not unusual to have millions of HyperPoints that need to be sorted into tens of thousands of bins. This would require billions of calulations. To speed this process up there is the option to build a hierarchy of bins. A schematic below shows a 1D example.

      HyperVolume Numbers 
|-------------0-------------| 
|------1------|------2------| 
|--3---|---4--|---5---|--6--|
|-7-|-8| 
          Bin Numbers
| 0 | 1|   2  |   3   |  4  |

Imagine we have a HyperPoint that falls into Bin 0. One would first check if it falls into HyperVolume 0 (note the distiction here between Bin/HyperVolume Numbers as indicated by the figure). First we check if it falls into HyperVolume 0, then HyperVolume 1 or 2, then HyperVolume 3 or 4, then HyperVolume 7 or 8.

In this simple example, it took 7 operations, whereas checking each Bin would have taken

Clearly as the number of bins increases, it becomes computationally much less expensive to follow this hierarchy approach.

The

Definition at line 82 of file HyperBinning.h.

#include <HyperBinning.h>

Inheritance diagram for HyperBinning:

Public Member Functions
	HyperBinning ()
	The only constructor.

bool	isPrimaryVolume (int volumeNumber) const

int	getHyperVolumeNumber (int binNumber) const

int	getBinNum (int volumeNumber) const

virtual std::vector< int >	getPrimaryVolumeNumbers () const

virtual	~HyperBinning ()

virtual void	setDimension (int dim)

virtual std::vector< int >	getLinkedHyperVolumes (int volumeNumber) const =0

virtual HyperVolume	getHyperVolume (int volumeNumber) const =0

virtual void	addPrimaryVolumeNumber (int volumeNumber)=0

virtual bool	addHyperVolume (const HyperVolume &hyperVolume, std::vector< int > linkedVolumes=std::vector< int >(0, 0))=0

virtual int	getNumHyperVolumes () const =0

virtual int	getNumPrimaryVolumes () const =0

virtual int	getPrimaryVolumeNumber (int i) const =0

virtual void	reserveCapacity (int nElements)

virtual void	load (TString filename, TString option="READ")=0

virtual BinningBase *	clone () const =0

virtual void	save (TString filename) const

virtual void	save () const

virtual void	mergeBinnings (const BinningBase &other)

virtual int	getNumBins () const

virtual int	getBinNum (const HyperPoint &coords) const

virtual std::vector< int >	getBinNum (const HyperPointSet &coords) const

std::vector< int >	getBinNumAlt (const HyperPointSet &coords) const

virtual HyperVolume	getBinHyperVolume (int binNumber) const

virtual HyperPoint	getAverageBinWidth () const

virtual HyperCuboid	getLimits () const

Public Member Functions inherited from BinningBase
void	setNames (HyperName names)

HyperName	getNames () const

const int &	getDimension () const

double	getMin (int dimension) const

double	getMax (int dimension) const

TString	getBinningType () const

bool	isSameBinningType (const BinningBase &other) const

virtual bool	isDiskResident () const

virtual TString	filename () const

Protected Member Functions
int	followBinLinks (const HyperPoint &coords, int binNumber) const

void	updateCash () const

void	updateBinNumbering () const

void	updateAverageBinWidth () const

void	updateMinMax () const

int	getHyperBinningDimFromTree (TTree *tree)

void	createBranches (TTree tree, int binNumber, double lowCorner, double highCorner, std::vector< int > **linkedBins) const

void	saveHyperVolumeToTree (TTree tree, double lowCorner, double *highCorner, const HyperVolume &hyperVolume) const

void	savePrimaryVolumeNumbers () const

Protected Member Functions inherited from BinningBase
void	setBinningType (TString binningType)

Private Attributes
CachedVar< HyperPoint >	_averageBinWidth

CachedVar< HyperCuboid >	_minmax

CachedVar< std::vector< int > >	_binNum

CachedVar< std::vector< int > >	_hyperVolumeNumFromBinNum

Constructor & Destructor Documentation

HyperBinning::~HyperBinning ( )

virtual

Destructor

Definition at line 847 of file HyperBinning.cpp.

Member Function Documentation

void HyperBinning::createBranches	(	TTree *	tree,
		int *	binNumber,
		double *	lowCorner,
		double *	highCorner,
		std::vector< int > **	linkedBins
	)		const

protected

Create the branches in a TTree so that the HyperBinningMemRes can be saved.

Definition at line 719 of file HyperBinning.cpp.

int HyperBinning::followBinLinks	(	const HyperPoint &	coords,
		int	motherVolumeNumber
	)		const

protected

Used to follow the bin hierarchy. Give it a HyperPoint, and the number of a HyperVolume (that has links) that the HyperPoint falls into.

Definition at line 398 of file HyperBinning.cpp.

HyperPoint HyperBinning::getAverageBinWidth ( ) const

virtual

get the average bin width HyperPoint (average bin width in each dimension). This value is cashed for speed - when the binning changes the cashe will automatically be updated.

Implements BinningBase.

Definition at line 619 of file HyperBinning.cpp.

HyperVolume HyperBinning::getBinHyperVolume ( int binNumber ) const

virtual

Get the HyperVolume assosiated with bin number i. This just uses the _hyperVolumeNumFromBinNum variable to find the HyperVolume number from the bin number, then returns that HyperVolume.

Implements BinningBase.

Definition at line 443 of file HyperBinning.cpp.

int HyperBinning::getBinNum ( int volumeNumber ) const

Get the bin number assosiated with a given HyperVolume number. If this returns -1, it means that the HyperVolume in question is not a bin, but part of the binning hierarchy.

Definition at line 452 of file HyperBinning.cpp.

int HyperBinning::getBinNum ( const HyperPoint & coords ) const

virtual

This is used to get the bin number that the HyperPoint falls into.

This is done by looping over the HyperVolumes in order until the HyperPoint is contained within one of them. When one of these is found, check to see if there are any 'linked bins' - if not, this is a true bin, so job done. If there are linked bins, proceed to see which of the linked bins the HyperPoint falls into. Continue this process until you reach a HyperVolume with no linked bins.

The BinNumber is found from the HyperVolume number using the lookup vector _binNum.

             0   1   2   3   4   5   6   7   8
_binNum = { -1, -1, -1, -1,  2,  3,  4,  0   1 }
      HyperVolume Numbers 
|-------------0-------------| 
|------1------|------2------| 
|--3---|---4--|---5---|--6--|
|-7-|-8| 
          Bin Numbers
| 0 | 1|   2  |   3   |  4  |

Implements BinningBase.

Definition at line 61 of file HyperBinning.cpp.

std::vector< int > HyperBinning::getBinNum ( const HyperPointSet & coords ) const

virtual

get multiple bin numbers at the same time. This should speed things up drastically if the binning is disk resident, because random access of a TTree is incredibly slow.

Reimplemented from BinningBase.

Definition at line 117 of file HyperBinning.cpp.

std::vector< int > HyperBinning::getBinNumAlt ( const HyperPointSet & coords ) const

get multiple bin numbers at the same time. This should speed things up drastically if the binning is disk resident, because random access of a TTree is incredibly slow.

Definition at line 275 of file HyperBinning.cpp.

int HyperBinning::getHyperBinningDimFromTree ( TTree * tree )

protected

Look at the tree that contains the HyperBinning and find the dimensionality

Definition at line 691 of file HyperBinning.cpp.

virtual HyperVolume HyperBinning::getHyperVolume ( int volumeNumber ) const

pure virtual

get one of the HyperVolumes

Implemented in HyperBinningMemRes, and HyperBinningDiskRes.

int HyperBinning::getHyperVolumeNumber ( int binNumber ) const

get the HyperVolume Number from the bin number

Definition at line 461 of file HyperBinning.cpp.

HyperCuboid HyperBinning::getLimits ( ) const

virtual

return the limits of the binning. This value is cashed for speed - when the binning changes the cashe will automatically be updated.

Implements BinningBase.

Definition at line 530 of file HyperBinning.cpp.

int HyperBinning::getNumBins ( ) const

virtual

Get number of bins (this is NOT the number of HyperVolumes!!! - see the class description for more details)

Implements BinningBase.

Definition at line 430 of file HyperBinning.cpp.

void HyperBinning::mergeBinnings ( const BinningBase & other )

virtual

This function will merge the two binnings. It assumes that the first

Implements BinningBase.

Definition at line 639 of file HyperBinning.cpp.

void HyperBinning::save ( TString filename ) const

virtual

Save the HyperBinningMemRes to a TFile.

Implements BinningBase.

Definition at line 777 of file HyperBinning.cpp.

void HyperBinning::save ( ) const

virtual

Save the HyperBinningMemRes to the open (and in scope) TFile.

Implements BinningBase.

Definition at line 795 of file HyperBinning.cpp.

void HyperBinning::saveHyperVolumeToTree	(	TTree *	tree,
		double *	lowCorner,
		double *	highCorner,
		const HyperVolume &	hyperVolume
	)		const

protected

Save a single HyperVolume to a tree - this involves looping over every HyperCuboid in the HyperVolume.

Definition at line 734 of file HyperBinning.cpp.

void HyperBinning::savePrimaryVolumeNumbers ( ) const

protected

Save the list of Primary Volume Numbers to the open (and in scope) TFile.

Definition at line 749 of file HyperBinning.cpp.

void HyperBinning::setDimension ( int dim )

virtual

Set the dimension of the HyperBinning. This can only be called once, when it is known what dimesnion it is.

Reimplemented from BinningBase.

Reimplemented in HyperBinningMemRes, and HyperBinningDiskRes.

Definition at line 18 of file HyperBinning.cpp.

void HyperBinning::updateAverageBinWidth ( ) const

protected

update the _averageBinWidth HyperPoint. Will usually be called from updateCash()

Definition at line 541 of file HyperBinning.cpp.

void HyperBinning::updateBinNumbering ( ) const

protected

Update the member variables _binNum and _hyperVolumeNumFromBinNum. Will usually be called from updateCash()

Definition at line 482 of file HyperBinning.cpp.

void HyperBinning::updateCash ( ) const

protected

Update the cash which includes the mutable member variables _binNum, _hyperVolumeNumFromBinNum, _averageBinWidth, and _minmax.

Definition at line 471 of file HyperBinning.cpp.

void HyperBinning::updateMinMax ( ) const

protected

Update the miniumum and maximum values, _minmax, in the cashe. Will usually be called from updateCash().

Definition at line 568 of file HyperBinning.cpp.

Member Data Documentation

CachedVar<HyperPoint> HyperBinning::_averageBinWidth

mutableprivate

< keep a record to check if the binning changes - if so _binNum, _hyperVolumeNumFromBinNum, _averageBinWidth, and _minmax need to be redetermined. store the a Hyperpoint giving the average bin width in each dimension. This is calculated once, and reused.

Definition at line 93 of file HyperBinning.h.

CachedVar<std::vector< int > > HyperBinning::_binNum

mutableprivate

Every HyperVolume has a Bin Number, although these will be -1 if it's not a true bin, and just part of the bin hierarchy. These numbers run from 0 to nBins - 1. In the below example

             0   1   2   3   4   5   6   7   8
_binNum = { -1, -1, -1, -1,  2,  3,  4,  0   1 }
      HyperVolume Numbers 
|-------------0-------------| 
|------1------|------2------| 
|--3---|---4--|---5---|--6--|
|-7-|-8| 
          Bin Numbers
| 0 | 1|   2  |   3   |  4  |

Definition at line 101 of file HyperBinning.h.

CachedVar< std::vector< int > > HyperBinning::_hyperVolumeNumFromBinNum

mutableprivate

The opposite of the member _binNum. This gives the HyperVolume number from the Bin Number. In the below example

                               0   1   2   3   4  
_hyperVolumeNumFromBinNum = {  7,  8,  4,  5,  6 }
      HyperVolume Numbers 
|-------------0-------------| 
|------1------|------2------| 
|--3---|---4--|---5---|--6--|
|-7-|-8| 
          Bin Numbers
| 0 | 1|   2  |   3   |  4  |

Definition at line 130 of file HyperBinning.h.

CachedVar<HyperCuboid> HyperBinning::_minmax

mutableprivate

store the HyperCuboid that surrounds the binning. This is calculated once, and reused.

Definition at line 97 of file HyperBinning.h.

The documentation for this class was generated from the following files:

/Users/sh7566/Documents/Work/Code/HyperPlot/include/HyperBinning.h
/Users/sh7566/Documents/Work/Code/HyperPlot/src/HyperBinning.cpp

Detailed Description

Public Member Functions

Protected Member Functions

Private Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation