slimarray.proto

syntax = "proto3";

option go_package = "slimarray";

// SlimArray compresses a uint32 array with overall trend by describing the trend
// with a polynomial, e.g., to store a sorted array is very common in practice.
// Such as an block-list of IP addresses, or a series of var-length record
// position on disk.
//
// E.g. a uint32 costs only 5 bits in average in a sorted array of a million
// number in range [0, 1000*1000].
//
// In addition to the unbelievable low memory footprint,
// a `Get` access is also very fast: it takes only 10 nano second in our
// benchmark.
//
// SlimArray is also ready for transport since it is defined with protobuf. E.g.:
//    a := slimarray.NewU32([]uint32{1, 2, 3})
//    bytes, err := proto.Marshal(a)
//
// Since 0.1.1
message SlimArray {

    // N is the count of elts
    int32  N                    = 10;

    repeated uint64 Rank      = 19;

    // Every 1024 elts segment has a 64-bit bitmap to describe the spans in it,
    // and another 64-bit rank: the count of `1` in preceding bitmaps.
    repeated uint64 Bitmap      = 20;

    // Polynomial and config of every span.
    // 3 doubles to represent a polynomial;
    repeated double Polynomials = 21;

    // Config stores the offset of residuals in Residuals and the bit width to
    // store a residual in a span.
    repeated int64 Configs = 22;

    // packed residuals for every elt.
    repeated uint64 Residuals   = 23;
}

// SlimBytes is a var-length []byte array.
//
// Internally it use a SlimArray to store record positions.
// Thus the memory overhead is about 8 bit / record.
//
// Since 0.1.4
message SlimBytes {

    // Positions is the array of start position of every record.
    // There are n + 1 int32 in it.
    // The last one equals len(Records)
    SlimArray Positions = 21;

    // Records is byte slice of all record packed together.
    bytes Records  = 22;
}