cpc

package
v0.1.0-rc4 Latest Latest
Warning

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

 Go to latest Published: Feb 4, 2026 License: Apache-2.0 Imports: 12 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	NextWordIdx = 0 // ptrArr[0]: nextWordIndex
	BitBuf      = 1 // ptrArr[1]: bitBuf
	BufBits     = 2 // ptrArr[2]: bufBits
)

Constants for ptrArr indices.

Variables

This section is empty.

Functions

func CountCoupons 

func CountCoupons(bitMatrix []uint64) uint64

CountCoupons sums the number of set bits across all 64-bit words in bitMatrix.

func CpcSketchToString 

func CpcSketchToString(mem []byte, detail bool) (string, error)

func NewPairTable 

func NewPairTable(lgSizeInts, numValidBits int) (*pairTable, error)

Types

type BitMatrix 

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

BitMatrix is a test structure that tracks bit patterns for hashed 64-bit data. It is not part of the core CPC algorithm; it's just for certain tests.

func NewBitMatrixWithSeed 

func NewBitMatrixWithSeed(lgK int, seed uint64) *BitMatrix

NewBitMatrixWithSeed creates a BitMatrix with the given lgK and custom seed.

func (*BitMatrix) GetMatrix 

func (bm *BitMatrix) GetMatrix() []uint64

GetMatrix returns the underlying array of 64-bit words storing the bits.

func (*BitMatrix) GetNumCoupons 

func (bm *BitMatrix) GetNumCoupons() uint64

GetNumCoupons returns the number of set bits (coupons) in the matrix. If numCouponsInvalid were ever set to true, it would recalculate by scanning the bitMatrix. By default, it’s always up to date.

func (*BitMatrix) Reset 

func (bm *BitMatrix) Reset()

Reset clears the entire bitMatrix, setting all bits to zero, and resets the coupon count to zero.

func (*BitMatrix) Update 

func (bm *BitMatrix) Update(datum int64)

Update hashes the given 64-bit datum and sets the corresponding bit in the matrix. If that bit was previously unset, the coupon count increments.

type CompressionCharacterization 

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

CompressionCharacterization is a harness that tests compression performance for various log(K) and N, measuring the time spent in creation, updates, compression, serialization, deserialization, uncompression, and equality checks.

func NewCompressionCharacterization 

func NewCompressionCharacterization(
	lgMinK, lgMaxK, lgMinT, lgMaxT, lgMulK, uPPO, incLgK int,
	pS, pW io.Writer,
) *CompressionCharacterization

func (*CompressionCharacterization) Start 

func (cc *CompressionCharacterization) Start() error

Start runs the entire characterization, printing the header first.

type CpcCompressedState 

type CpcCompressedState struct {
	CsvIsValid    bool
	WindowIsValid bool
	LgK           int
	SeedHash      int16
	FiCol         int
	MergeFlag     bool // compliment of HIP Flag
	NumCoupons    uint64

	Kxp         float64
	HipEstAccum float64

	NumCsv        uint64
	CsvStream     []int // may be longer than required
	CsvLengthInts int
	CwStream      []int // may be longer than required
	CwLengthInts  int
}

func NewCpcCompressedState 

func NewCpcCompressedState(lgK int, seedHash int16) *CpcCompressedState

func NewCpcCompressedStateFromSketch 

func NewCpcCompressedStateFromSketch(sketch *CpcSketch) (*CpcCompressedState, error)

type CpcFlavor 

type CpcFlavor int
const (
	CpcFlavorEmpty   CpcFlavor = 0 //    0  == C <    1
	CpcFlavorSparse  CpcFlavor = 1 //    1  <= C <   3K/32
	CpcFlavorHybrid  CpcFlavor = 2 // 3K/32 <= C <   K/2
	CpcFlavorPinned  CpcFlavor = 3 //   K/2 <= C < 27K/8  [NB: 27/8 = 3 + 3/8]
	CpcFlavorSliding CpcFlavor = 4 // 27K/8 <= C
)

func (CpcFlavor) String 

func (f CpcFlavor) String() string

type CpcFormat 

type CpcFormat int
const (
	CpcFormatEmptyMerged             CpcFormat = 0
	CpcFormatEmptyHip                CpcFormat = 1
	CpcFormatSparseHybridMerged      CpcFormat = 2
	CpcFormatSparseHybridHip         CpcFormat = 3
	CpcFormatPinnedSlidingMergedNosv CpcFormat = 4
	CpcFormatPinnedSlidingHipNosv    CpcFormat = 5
	CpcFormatPinnedSlidingMerged     CpcFormat = 6
	CpcFormatPinnedSlidingHip        CpcFormat = 7
)

func (CpcFormat) String 

func (f CpcFormat) String() string

type CpcSketch 

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

func NewCpcSketch 

func NewCpcSketch(lgK int, seed uint64) (*CpcSketch, error)

func NewCpcSketchFromSlice 

func NewCpcSketchFromSlice(bytes []byte, seed uint64) (*CpcSketch, error)

func NewCpcSketchFromSliceWithDefault 

func NewCpcSketchFromSliceWithDefault(bytes []byte) (*CpcSketch, error)

func NewCpcSketchWithDefault 

func NewCpcSketchWithDefault(lgK int) (*CpcSketch, error)

func (*CpcSketch) Copy 

func (c *CpcSketch) Copy() (*CpcSketch, error)

Copy creates and returns a deep copy of the CpcSketch.

func (*CpcSketch) GetEstimate 

func (c *CpcSketch) GetEstimate() float64

func (*CpcSketch) GetLgK 

func (c *CpcSketch) GetLgK() int

GetLgK returns the log-base-2 of K.

func (*CpcSketch) GetLowerBound 

func (c *CpcSketch) GetLowerBound(kappa int) float64

func (*CpcSketch) GetUpperBound 

func (c *CpcSketch) GetUpperBound(kappa int) float64

func (*CpcSketch) String 

func (c *CpcSketch) String() string

func (*CpcSketch) ToCompactSlice 

func (c *CpcSketch) ToCompactSlice() ([]byte, error)

ToCompactSlice returns this sketch as a compressed byte slice.

func (*CpcSketch) UpdateByteSlice 

func (c *CpcSketch) UpdateByteSlice(datum []byte) error

func (*CpcSketch) UpdateFloat64 

func (c *CpcSketch) UpdateFloat64(datum float64) error

func (*CpcSketch) UpdateInt32Slice 

func (c *CpcSketch) UpdateInt32Slice(datum []int32) error

func (*CpcSketch) UpdateInt64 

func (c *CpcSketch) UpdateInt64(datum int64) error

func (*CpcSketch) UpdateInt64Slice 

func (c *CpcSketch) UpdateInt64Slice(datum []int64) error

func (*CpcSketch) UpdateString 

func (c *CpcSketch) UpdateString(datum string) error

func (*CpcSketch) UpdateUint64 

func (c *CpcSketch) UpdateUint64(datum uint64) error

type CpcUnion 

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

func NewCpcUnionSketch 

func NewCpcUnionSketch(lgK int, seed uint64) (CpcUnion, error)

func NewCpcUnionSketchWithDefault 

func NewCpcUnionSketchWithDefault(lgK int) (CpcUnion, error)

func (*CpcUnion) GetBitMatrix 

func (u *CpcUnion) GetBitMatrix() ([]uint64, error)

func (*CpcUnion) GetFamilyId 

func (u *CpcUnion) GetFamilyId() int

func (*CpcUnion) GetResult 

func (u *CpcUnion) GetResult() (*CpcSketch, error)

func (*CpcUnion) Update 

func (u *CpcUnion) Update(source *CpcSketch) error

type CpcWrapper 

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

CpcWrapper is a read-only view of a serialized CPC sketch.

func NewCpcWrapperFromBytes 

func NewCpcWrapperFromBytes(byteArray []byte) (*CpcWrapper, error)

NewCpcWrapperFromBytes constructs a read-only view of the given byte array that contains a CpcSketch. It checks that the preamble is valid and that the sketch is in compressed format.

func (*CpcWrapper) GetEstimate 

func (cw *CpcWrapper) GetEstimate() float64

GetEstimate returns the best estimate of the cardinality of the wrapped sketch. If the sketch is in HIP mode, we return the HIP accumulator; otherwise we return the ICON estimate.

func (*CpcWrapper) GetFamily 

func (cw *CpcWrapper) GetFamily() int

GetFamily returns the family ID for CPC sketches.

func (*CpcWrapper) GetLgK 

func (cw *CpcWrapper) GetLgK() int

GetLgK returns the log-base-2 of K for this sketch.

func (*CpcWrapper) GetLowerBound 

func (cw *CpcWrapper) GetLowerBound(kappa int) float64

GetLowerBound returns the lower bound of the confidence interval given kappa (the number of standard deviations from the mean).

func (*CpcWrapper) GetUpperBound 

func (cw *CpcWrapper) GetUpperBound(kappa int) float64

GetUpperBound returns the upper bound of the confidence interval given kappa (the number of standard deviations from the mean).

type MergingValidation 

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

func NewMergingValidation 

func NewMergingValidation(
	lgMinK, lgMaxK, lgMulK, uPPO, incLgK int,
	pS, pW io.Writer,
) *MergingValidation

func (*MergingValidation) Start 

func (mv *MergingValidation) Start() error

Start prints the header, then calls doRangeOfLgK.

type QuickMergingValidation 

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

func NewQuickMergingValidation 

func NewQuickMergingValidation(
	lgMinK, lgMaxK, incLgK int,
	ps, pw io.Writer,
) *QuickMergingValidation

func (*QuickMergingValidation) Start 

func (qmv *QuickMergingValidation) Start() error

type StreamingValidation 

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

StreamingValidation is a test/characterization harness that repeatedly updates a CPC sketch and a BitMatrix, checks their correctness, and logs results.

func NewStreamingValidation 

func NewStreamingValidation(
	lgMinK, lgMaxK, trials, ppoN int,
	pS, pW io.Writer,
) *StreamingValidation

func (*StreamingValidation) Start 

func (sv *StreamingValidation) Start()

Start begins the streaming validation process, printing column headers and running the test loops.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.