aggregation

package
v1.4.4 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 31, 2021 License: GPL-3.0 Imports: 5 Imported by: 0

Documentation

Overview

Package aggregation contains implementations of bitlist aggregation algorithms and heuristics.

Index

Constants

This section is empty.

Variables

View Source
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")
)
View Source
var ErrInvalidMaxCoverProblem = errors.New("invalid max_cover problem")

ErrInvalidMaxCoverProblem is returned when Maximum Coverage problem was initialized incorrectly.

Functions

func MaxCover added in v1.2.0

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.

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL