Resevoir sampling is based on the 2005 paper "Weighted Random Sampling" by Efraimidis and Spirakis. More...

Collaboration diagram for duckdb::BaseReservoirSampling:

[legend]

Public Member Functions
	BaseReservoirSampling (int64_t seed)

void	InitializeReservoirWeights (idx_t cur_size, idx_t sample_size)

void	SetNextEntry ()

void	ReplaceElementWithIndex (idx_t entry_index, double with_weight, bool pop=true)

void	ReplaceElement (double with_weight=-1)

void	UpdateMinWeightThreshold ()

void	FillWeights (SelectionVector &sel, idx_t &sel_size)

unique_ptr< BaseReservoirSampling >	Copy ()

void	Serialize (Serializer &serializer) const

Static Public Member Functions
static unique_ptr< BaseReservoirSampling >	Deserialize (Deserializer &deserializer)

Public Attributes
ReservoirRNG	random
	The random generator.

idx_t	next_index_to_sample
	The next element to sample.

double	min_weight_threshold
	The reservoir threshold of the current min entry.

idx_t	min_weighted_entry_index
	The reservoir index of the current min entry.

idx_t	num_entries_to_skip_b4_next_sample

idx_t	num_entries_seen_total

std::priority_queue< std::pair< double, idx_t > >	reservoir_weights
	Priority queue of [random element, index] for each of the elements in the sample.

Friends
class	BlockingSample

Detailed Description

Resevoir sampling is based on the 2005 paper "Weighted Random Sampling" by Efraimidis and Spirakis.

Member Function Documentation

◆ FillWeights()

void duckdb::BaseReservoirSampling::FillWeights	(	SelectionVector &	sel,
		idx_t &	sel_size
	)

Go from the naive sampling to the reservoir sampling Naive samping will not collect weights, but when we serialize we need to serialize weights again.

Member Data Documentation

◆ num_entries_to_skip_b4_next_sample

idx_t duckdb::BaseReservoirSampling::num_entries_to_skip_b4_next_sample

The current count towards next index (i.e. we will replace an entry in next_index - current_count tuples) The number of entries "seen" before choosing one that will go in our reservoir sample.

◆ num_entries_seen_total

idx_t duckdb::BaseReservoirSampling::num_entries_seen_total

when collecting a sample in parallel, we want to know how many values each thread has seen so we can collect the samples from the thread local states in a uniform manner

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

external/duckdb/duckdb.hpp

Public Member Functions

Static Public Member Functions