Documentation
¶
Overview ¶
Package aggregation contains implementations of bitlist aggregation algorithms and heuristics.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ( // ErrBitsOverlap is returned when two bitlists overlap with each other. ErrBitsOverlap = errors.New("overlapping aggregation bits") // 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 ¶
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.
Source Files
Directories