aggregation

Documentation

Overview

Package aggregation contains implementations of bitlist aggregation algorithms and heuristics.

Index

• Variables
• type Aggregation
  • func (ag *Aggregation) String() string
• type MaxCoverCandidate
  • func NewMaxCoverCandidate(key int, bits *bitfield.Bitlist) *MaxCoverCandidate
  • func (c *MaxCoverCandidate) String() string
• type MaxCoverCandidates
• type MaxCoverProblem
  • func (mc *MaxCoverProblem) Cover(k int, allowOverlaps, allowDuplicates 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.

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.

func (*Aggregation) String

func (ag *Aggregation) String() string

String provides string representation of a 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.

func (*MaxCoverCandidate) String

func (c *MaxCoverCandidate) String() string

String provides string representation of a 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, allowDuplicates 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.