bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR > Class Template Reference

Top-Down NonOrdFP tree projection algo TD NonOrdFP structure with single-path optimization. More...

Inheritance diagram for bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >:

[legend]Collaboration diagram for bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >:

[legend]List of all members.


Public Types
typedef TYPENAME NonOrdFPStructure< INPUT, BUILDTREEALLOC, FIRSTLEVEL >::fptree_t	fptree_t
typedef TYPENAME NonOrdFPStructure< INPUT, BUILDTREEALLOC, FIRSTLEVEL >::index_t	index_t
Public Member Functions
	TDNonOrdFPStructure (INPUT *_inp, item_t maxitem, counter_t _minsupp)
	~TDNonOrdFPStructure ()
item_t DINLINE	checkSinglePath (fptree_t *t, item_t curritem, item_t spdepth)
SinglePathIterator DINLINE	getSinglePathIterator (fptree_t *tree, item_t curritem)
void DINLINE	zeroDataDense (fptree_t *intr, item_t curritem)
void DINLINE	zeroDataADense (fptree_t *intr, item_t curritem)
void DINLINE	aggregateSparse (index_t itemstarts, index_t parents, counter_t freqs, counter_t ocounters, counter_t *ncounters, item_t curritem)
void DINLINE	aggregateDense (index_t itemstarts, index_t parents, counter_t freqs, counter_t ocounters, counter_t *ncounters, item_t curritem)
fptree_t *DINLINE	projectTree (fptree_t *intr, item_t curritem)
bool DINLINE	dropNode (fptree_t *t, item_t curritem, index_t nodeidx)
void DINLINE	compactTree (fptree_t *t, item_t projitem)
void DINLINE	compactTreeSparse (fptree_t *t, item_t projitem)
void DINLINE	deallocTree (fptree_t t, fptree_t parent, item_t projitem)
counter_t	getTransactionCount ()
	NonOrdFPStructure (INPUT *_inp, item_t maxitem)
	construct a structure from transactions.
fptree_t *	getFullTree ()
fptree_t *	getProjTree (item_t item)
bool DINLINE	checkSinglePath (fptree_t *t, item_t curritem)
void DINLINE	handleSinglePath (fptree_t t, item_t curritem, O_M out)
Protected Member Functions
void	buildTree (item_t maxitem)
	Create the unconditional tree.
void	buildAllL1Trees (item_t maxitem)
	Create all first-level conditional trees.
void	simultProject (item_t maxitem)
Protected Attributes
fptree_t	fulltree
std::vector< fptree_t >	l1trees
counter_t	transaction_count
Private Attributes
counter_t	minsupp
counter_t *	multiples
index_t *	last
index_t *	projmap
	mapping of old-nodeidx to new-nodeidx
index_t *	projlastidx
	the node index of the last child of a node (on the current level)
index_t *	sparsenodes
	hold a list of sparse nodes
index_t **	nextfreesparsenode
	the next free element in the above array on a particular level
blockstack< stacksingleblock< counter_t, true > >	nodealloc
	allocator following the recursion for nodes (counter,parent)
blockstack< stacksingleblock< counter_t, false > >	headeralloc
	allocator following the recursion for headers (itemstarts,freqs)
blockstack< stacksingleblock< index_t, false > >	projheaderalloc
	allocator following the recursion for projections (itemstarts)
blockstack< stacksingleblock< index_t, false > >	projnodealloc
	allocator following the recursion for projections (itemstarts)
singlesalloc< fptree_t, 100 >	treealloc
	allocator for the fptree_t * structures
Friends
class	SimultProject
Classes
class	SinglePathIterator

Detailed Description

template<class INPUT, class BUILDTREEALLOC, bool SINGLE, bool TD, bool PROJECT, bool PROJECTDELETECLOSED, bool PROJMERGENODES, FirstLevel FIRSTLEVEL, bool SPARSEAGGR>
class bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >

Top-Down NonOrdFP tree projection algo TD NonOrdFP structure with single-path optimization.

!!!IMPORTANT!!! due to the reusal of previous fp-tree memory for the projected counters, in TD mode the NEELevel1 gives WRONG RESULTS. But nothing warns you about that... (In fact the issue appears only at very low support levels on very dense datasets).

If the caller uses NEE optimization, then he must ensure that the NEE list contains only larger numbered items than curritem (the item you project). This is due to the single path export returns all items, even if they are considered as closed and put on the NEE list. Also the correct frequencies are always recalculated and replaced as the projections are performed.

Definition at line 599 of file nonordfp.cpp.

Member Typedef Documentation

template<class INPUT, class BUILDTREEALLOC, bool SINGLE, bool TD, bool PROJECT, bool PROJECTDELETECLOSED, bool PROJMERGENODES, FirstLevel FIRSTLEVEL, bool SPARSEAGGR>

typedef TYPENAME NonOrdFPStructure<INPUT,BUILDTREEALLOC,FIRSTLEVEL>::fptree_t bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::fptree_t

Reimplemented from bracz::NonOrdFPStructure< INPUT, BUILDTREEALLOC, FIRSTLEVEL >.
Definition at line 601 of file nonordfp.cpp.

template<class INPUT, class BUILDTREEALLOC, bool SINGLE, bool TD, bool PROJECT, bool PROJECTDELETECLOSED, bool PROJMERGENODES, FirstLevel FIRSTLEVEL, bool SPARSEAGGR>

typedef TYPENAME NonOrdFPStructure<INPUT,BUILDTREEALLOC,FIRSTLEVEL>::index_t bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::index_t

Reimplemented from bracz::NonOrdFPStructure< INPUT, BUILDTREEALLOC, FIRSTLEVEL >.
Definition at line 602 of file nonordfp.cpp.

Constructor & Destructor Documentation

Member Function Documentation

void bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::buildAllL1Trees ( item_t maxitem ) [inline, protected, inherited]

Create all first-level conditional trees.

Definition at line 194 of file nonordfp.cpp.
References bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::inp, bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::l1trees, and bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::transaction_count.

void bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::buildTree ( item_t maxitem ) [inline, protected, inherited]

Create the unconditional tree.

Definition at line 174 of file nonordfp.cpp.
References bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::fulltree, bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::inp, and bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::transaction_count.

bool DINLINE bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::checkSinglePath ( fptree_t * t,

item_t curritem

) [inline, inherited]

Definition at line 568 of file nonordfp.cpp.

fptree_t* bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::getFullTree ( ) [inline, inherited]

Definition at line 544 of file nonordfp.cpp.
References FLBuildSingleTree, and bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::fulltree.

fptree_t* bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::getProjTree ( item_t item ) [inline, inherited]

Definition at line 552 of file nonordfp.cpp.
References FLBuildSingleTree, and bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::l1trees.

template<class INPUT, class BUILDTREEALLOC, bool SINGLE, bool TD, bool PROJECT, bool PROJECTDELETECLOSED, bool PROJMERGENODES, FirstLevel FIRSTLEVEL, bool SPARSEAGGR>

SinglePathIterator DINLINE bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::getSinglePathIterator ( fptree_t * tree,

item_t curritem

) [inline]

Definition at line 713 of file nonordfp.cpp.
References bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::last.

counter_t bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::getTransactionCount ( ) [inline, inherited]

Definition at line 73 of file nonordfp.cpp.
References bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::transaction_count.

void DINLINE bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::handleSinglePath ( fptree_t * t,

item_t curritem,

O_M * out

) [inline, inherited]

Definition at line 572 of file nonordfp.cpp.

bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::NonOrdFPStructure ( INPUT * _inp,

item_t maxitem

) [inline, inherited]

construct a structure from transactions.

Parameters:

_inp is the input manager

maxitem is the first unallocated item. (i.e. valid itemids are 0..maxitem-1)

Definition at line 526 of file nonordfp.cpp.
References bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::buildAllL1Trees(), bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::buildTree(), FLBuildAllL1Trees, FLBuildSingleTree, FLSimultProject, bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::inp, and bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::simultProject().

void bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::simultProject ( item_t maxitem ) [inline, protected, inherited]

Definition at line 495 of file nonordfp.cpp.
References bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::inp, bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::SimultProject, and bracz::NonOrdFPStructure< INPUT, BUILDTREE, FIRSTLEVEL >::transaction_count.

Friends And Related Function Documentation

friend class SimultProject [friend, inherited]

Definition at line 493 of file nonordfp.cpp.

Member Data Documentation

fptree_t bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::fulltree [protected, inherited]

Definition at line 85 of file nonordfp.cpp.
Referenced by bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::TDNonOrdFPStructure().

template<class INPUT, class BUILDTREEALLOC, bool SINGLE, bool TD, bool PROJECT, bool PROJECTDELETECLOSED, bool PROJMERGENODES, FirstLevel FIRSTLEVEL, bool SPARSEAGGR>

blockstack<stacksingleblock<counter_t,false> > bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::headeralloc [private]

allocator following the recursion for headers (itemstarts,freqs)

Definition at line 625 of file nonordfp.cpp.
Referenced by bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::deallocTree(), and bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::projectTree().

std::vector<fptree_t> bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::l1trees [protected, inherited]

Definition at line 87 of file nonordfp.cpp.
Referenced by bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::TDNonOrdFPStructure().

template<class INPUT, class BUILDTREEALLOC, bool SINGLE, bool TD, bool PROJECT, bool PROJECTDELETECLOSED, bool PROJMERGENODES, FirstLevel FIRSTLEVEL, bool SPARSEAGGR>

blockstack<stacksingleblock<counter_t,true> > bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::nodealloc [private]

allocator following the recursion for nodes (counter,parent)

Definition at line 623 of file nonordfp.cpp.
Referenced by bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::compactTreeSparse(), bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::deallocTree(), and bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::projectTree().

template<class INPUT, class BUILDTREEALLOC, bool SINGLE, bool TD, bool PROJECT, bool PROJECTDELETECLOSED, bool PROJMERGENODES, FirstLevel FIRSTLEVEL, bool SPARSEAGGR>

blockstack<stacksingleblock<index_t,false> > bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::projheaderalloc [private]

allocator following the recursion for projections (itemstarts)

Definition at line 627 of file nonordfp.cpp.
Referenced by bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::compactTree(), bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::compactTreeSparse(), and bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::deallocTree().

template<class INPUT, class BUILDTREEALLOC, bool SINGLE, bool TD, bool PROJECT, bool PROJECTDELETECLOSED, bool PROJMERGENODES, FirstLevel FIRSTLEVEL, bool SPARSEAGGR>

blockstack<stacksingleblock<index_t,false> > bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::projnodealloc [private]

allocator following the recursion for projections (itemstarts)

Definition at line 629 of file nonordfp.cpp.
Referenced by bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::compactTree(), bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::compactTreeSparse(), and bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::deallocTree().

counter_t bracz::NonOrdFPStructure< INPUT , BUILDTREEALLOC , FIRSTLEVEL >::transaction_count [protected, inherited]

Definition at line 90 of file nonordfp.cpp.

template<class INPUT, class BUILDTREEALLOC, bool SINGLE, bool TD, bool PROJECT, bool PROJECTDELETECLOSED, bool PROJMERGENODES, FirstLevel FIRSTLEVEL, bool SPARSEAGGR>

singlesalloc<fptree_t,100> bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::treealloc [private]

allocator for the fptree_t * structures

Definition at line 631 of file nonordfp.cpp.
Referenced by bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::deallocTree(), and bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR >::projectTree().

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

nonordfp.cpp

Generated on Sun Sep 17 17:57:32 2006 for FIM environment by

1.4.4

bracz::TDNonOrdFPStructure< INPUT, BUILDTREEALLOC, SINGLE, TD, PROJECT, PROJECTDELETECLOSED, PROJMERGENODES, FIRSTLEVEL, SPARSEAGGR > Class Template Reference

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Attributes