aggregation

Documentation

Overview

Package aggregation contains implementations of bitlist aggregation algorithms and heuristics.

Index

• Variables
• func MaxCover(candidates []*bitfield.Bitlist64, k int, allowOverlaps bool) (selected, coverage *bitfield.Bitlist64, err error)
• type Aggregation
• type MaxCoverCandidate
  • func NewMaxCoverCandidate(key int, bits *bitfield.Bitlist) *MaxCoverCandidate
• type MaxCoverCandidates
• type MaxCoverProblem
  • func (mc *MaxCoverProblem) Cover(k int, allowOverlaps bool) (*Aggregation, error)

Variables

var (
	// ErrBitsOverlap is returned when two bitlists overlap with each other.
	ErrBitsOverlap = errors.New("overlapping aggregation bits")

	// ErrBitsDifferentLen is returned when two bitlists have different lengths.
	ErrBitsDifferentLen = errors.New("different bitlist lengths")

	// ErrInvalidStrategy is returned when invalid aggregation strategy is selected.
	ErrInvalidStrategy = errors.New("invalid aggregation strategy")
)

var ErrInvalidMaxCoverProblem = errors.New("invalid max_cover problem")

ErrInvalidMaxCoverProblem is returned when Maximum Coverage problem was initialized incorrectly.

Functions

func MaxCover

func MaxCover(candidates []*bitfield.Bitlist64, k int, allowOverlaps bool) (selected, coverage *bitfield.Bitlist64, err error)

MaxCover finds the k-cover of Maximum Coverage problem.

Types

type Aggregation

type Aggregation struct {
	// Coverage represents the best available solution to bitlist aggregation.
	Coverage bitfield.Bitlist
	// Keys is a list of candidate keys in the best available solution.
	Keys []int
}

Aggregation defines the bitlist aggregation problem solution.

type MaxCoverCandidate

type MaxCoverCandidate struct {
	// contains filtered or unexported fields
}

MaxCoverCandidate represents a candidate set to be used in aggregation.

func NewMaxCoverCandidate

func NewMaxCoverCandidate(key int, bits *bitfield.Bitlist) *MaxCoverCandidate

NewMaxCoverCandidate returns initialized candidate.

type MaxCoverCandidates

type MaxCoverCandidates []*MaxCoverCandidate

MaxCoverCandidates is defined to allow group operations (filtering, sorting) on all candidates.

type MaxCoverProblem

type MaxCoverProblem struct {
	Candidates MaxCoverCandidates
}

MaxCoverProblem defines Maximum Coverage problem.

Problem is defined as MaxCover(U, S, k): S', where: U is a finite set of objects, where |U| = n. Furthermore, let S = {S_1, ..., S_m} be all subsets of U, that's their union is equal to U. Then, Maximum Coverage is the problem of finding such a collection S' of subsets from S, where |S'| <= k, and union of all subsets in S' covering U with maximum cardinality.

The current implementation captures the original MaxCover problem, and the variant where additional invariant is enforced: all elements of S' must be disjoint. This comes handy when we need to aggregate bitsets, and overlaps are not allowed.

For more details, see: "Analysis of the Greedy Approach in Problems of Maximum k-Coverage" by Hochbaum and Pathria. https://hochbaum.ieor.berkeley.edu/html/pub/HPathria-max-k-coverage-greedy.pdf

func (*MaxCoverProblem) Cover

func (mc *MaxCoverProblem) Cover(k int, allowOverlaps bool) (*Aggregation, error)

Cover calculates solution to Maximum k-Cover problem in O(knm), where n is number of candidates and m is a length of bitlist in each candidate.