CluE  1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
CluE::FrahlingSohler< VectorType, Hash, size_space > Class Template Reference

Coreset algorithm for k-median clustering. More...

#include <frahlingsohler.h>

Inheritance diagram for CluE::FrahlingSohler< VectorType, Hash, size_space >:
Inheritance graph
Collaboration diagram for CluE::FrahlingSohler< VectorType, Hash, size_space >:
Collaboration graph

Classes

struct  GridInstance
 Set of grids. More...
 

Public Member Functions

 FrahlingSohler (DiscreteBoundedSpace< VectorType, size_space > *space, WeightModifier< VectorType > *weightModifier, std::function< Hash()> createHashfunction, double eps, double rho, unsigned int numOfCenters)
 
void insert (VectorType const &element)
 
void remove (VectorType const &element)
 
virtual FrahlingSohler
< VectorType, Hash, size_space > & 
operator<< (VectorType const &element)
 Streaming operator. More...
 
virtual ProxySolution
< VectorType > * 
compute ()
 Runs the algorithm and returns the computed solution. More...
 
- Public Member Functions inherited from CluE::Algorithm
virtual ~Algorithm ()
 

Private Member Functions

void shiftGrid (std::vector< size_space > &cell)
 
void toParentCell (std::vector< size_space > &cell)
 
std::vector< std::vector
< size_space > > 
getChildCells (std::vector< size_space > cell)
 
unsigned long long getCellIndex (typename GridInstance::Grid const &grid, std::vector< size_space > &cell, size_t layer)
 
bool evaluateGrid (std::vector< VectorType > &coreset, size_t gridInstance, size_t gridIndex, std::vector< size_space > cell)
 
bool isHeavy (size_t gridInstance, size_t gridIndex, size_t index)
 

Private Attributes

std::unique_ptr
< DiscreteBoundedSpace
< VectorType, size_space > > 
space
 
std::unique_ptr
< WeightModifier< VectorType > > 
weightModifier
 
std::vector< GridInstancegrids
 
VectorHash< size_t > vechash
 
double eps
 
double rho
 
unsigned int numOfCenters
 
double alpha
 
double delta
 
size_t dimension
 
unsigned long long nFitting
 
size_t numOfNestedLayers
 

Detailed Description

template<typename VectorType, typename Hash, typename size_space>
class CluE::FrahlingSohler< VectorType, Hash, size_space >

Coreset algorithm for k-median clustering.

G. Frahling, C. Sohler: Coresets in dynamic geometric data streams. STOC 2005.

Warning
This implementation needs more testing.

Definition at line 27 of file frahlingsohler.h.

Constructor & Destructor Documentation

template<typename VectorType , typename Hash , typename size_space >
CluE::FrahlingSohler< VectorType, Hash, size_space >::FrahlingSohler ( DiscreteBoundedSpace< VectorType, size_space > *  space,
WeightModifier< VectorType > *  weightModifier,
std::function< Hash()>  createHashfunction,
double  eps,
double  rho,
unsigned int  numOfCenters 
)

Definition at line 94 of file frahlingsohler.h.

Member Function Documentation

template<typename VectorType , typename Hash , typename size_space >
void CluE::FrahlingSohler< VectorType, Hash, size_space >::insert ( VectorType const &  element)

Definition at line 143 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
void CluE::FrahlingSohler< VectorType, Hash, size_space >::remove ( VectorType const &  element)

Definition at line 178 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
FrahlingSohler< VectorType, Hash, size_space > & CluE::FrahlingSohler< VectorType, Hash, size_space >::operator<< ( VectorType const &  element)
virtual

Streaming operator.

Implements CluE::StreamingAlgorithm< VectorType >.

Definition at line 137 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
ProxySolution< VectorType > * CluE::FrahlingSohler< VectorType, Hash, size_space >::compute ( )
virtual

Runs the algorithm and returns the computed solution.

Implementing classes override this method with the computation of a SolutionProvider instance whose reference is returned. The responibility for destructing the instance lies with the caller.

Implements CluE::Algorithm.

Definition at line 208 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
void CluE::FrahlingSohler< VectorType, Hash, size_space >::shiftGrid ( std::vector< size_space > &  cell)
private

Definition at line 286 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
void CluE::FrahlingSohler< VectorType, Hash, size_space >::toParentCell ( std::vector< size_space > &  cell)
private

Definition at line 292 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
std::vector< std::vector< size_space > > CluE::FrahlingSohler< VectorType, Hash, size_space >::getChildCells ( std::vector< size_space >  cell)
private

Definition at line 299 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
unsigned long long CluE::FrahlingSohler< VectorType, Hash, size_space >::getCellIndex ( typename GridInstance::Grid const &  grid,
std::vector< size_space > &  cell,
size_t  layer 
)
private

Definition at line 317 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
bool CluE::FrahlingSohler< VectorType, Hash, size_space >::evaluateGrid ( std::vector< VectorType > &  coreset,
size_t  gridInstance,
size_t  gridIndex,
std::vector< size_space >  cell 
)
private

Definition at line 225 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
bool CluE::FrahlingSohler< VectorType, Hash, size_space >::isHeavy ( size_t  gridInstance,
size_t  gridIndex,
size_t  index 
)
private

Definition at line 276 of file frahlingsohler.h.

Member Data Documentation

template<typename VectorType , typename Hash , typename size_space >
std::unique_ptr<DiscreteBoundedSpace<VectorType, size_space> > CluE::FrahlingSohler< VectorType, Hash, size_space >::space
private

Definition at line 79 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
std::unique_ptr<WeightModifier<VectorType> > CluE::FrahlingSohler< VectorType, Hash, size_space >::weightModifier
private

Definition at line 80 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
std::vector<GridInstance> CluE::FrahlingSohler< VectorType, Hash, size_space >::grids
private

Definition at line 81 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
VectorHash<size_t> CluE::FrahlingSohler< VectorType, Hash, size_space >::vechash
private

Definition at line 82 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
double CluE::FrahlingSohler< VectorType, Hash, size_space >::eps
private

Definition at line 83 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
double CluE::FrahlingSohler< VectorType, Hash, size_space >::rho
private

Definition at line 84 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
unsigned int CluE::FrahlingSohler< VectorType, Hash, size_space >::numOfCenters
private

Definition at line 85 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
double CluE::FrahlingSohler< VectorType, Hash, size_space >::alpha
private

Definition at line 86 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
double CluE::FrahlingSohler< VectorType, Hash, size_space >::delta
private

Definition at line 87 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
size_t CluE::FrahlingSohler< VectorType, Hash, size_space >::dimension
private

Definition at line 88 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
unsigned long long CluE::FrahlingSohler< VectorType, Hash, size_space >::nFitting
private

Definition at line 89 of file frahlingsohler.h.

template<typename VectorType , typename Hash , typename size_space >
size_t CluE::FrahlingSohler< VectorType, Hash, size_space >::numOfNestedLayers
private

Definition at line 90 of file frahlingsohler.h.


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