gocroaring

README

gocroaring

Go wrapper for CRoaring (a C/C++ implementation at https://github.com/RoaringBitmap/CRoaring)

Roaring bitmaps are used by several important systems:

• Apache Lucene and derivative systems such as Solr and Elastic,
• Metamarkets' Druid,
• Apache Spark,
• Netflix Atlas,
• LinkedIn Pinot,
• OpenSearchServer,
• Cloud Torrent,
• Whoosh,
• Pilosa,
• Microsoft Visual Studio Team Services (VSTS),
• eBay's Apache Kylin.

Roaring bitmaps are found to work well in many important applications:

Use Roaring for bitmap compression whenever possible. Do not use other bitmap compression methods (Wang et al., SIGMOD 2017)

The original java version can be found at https://github.com/RoaringBitmap/RoaringBitmap

There is a native Go version at https://github.com/RoaringBitmap/roaring

This code is licensed under Apache License, Version 2.0 (ASL2.0).

Copyright 2016 by the authors.

Benchmarking

See https://github.com/lemire/gobitmapbenchmark for a comparison between this wrapper and the Go native version.

References

• Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O'Hara, François Saint-Jacques, Gregory Ssi-Yan-Kai, Roaring Bitmaps: Implementation of an Optimized Software Library arXiv:1709.07821
• Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience Volume 46, Issue 5, pages 709–719, May 2016 http://arxiv.org/abs/1402.6407 This paper used data from http://lemire.me/data/realroaring2014.html
• Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser, Consistently faster and smaller compressed bitmaps with Roaring, Software: Practice and Experience (accepted in 2016, to appear) http://arxiv.org/abs/1603.06549

Dependencies

None in particular.

Naturally, you also need to grab the roaring code itself:

• go get github.com/RoaringBitmap/gocroaring

Example

Here is a simplified but complete example:

package main

import (
	"fmt"

	"github.com/RoaringBitmap/gocroaring"
)

func main() {
	// example inspired by https://github.com/fzandona/goroar
	fmt.Println("==roaring==")
	rb1 := gocroaring.New(1, 2, 3, 4, 5, 100, 1000)
	rb1.RunOptimize() // improves compression
	fmt.Println("Cardinality: ", rb1.Cardinality())
	fmt.Println("Contains 3? ", rb1.Contains(3))

	rb2 := gocroaring.New()
	rb2.Add(3, 4, 1000)
	rb2.RunOptimize() // improves compression

	rb1.And(rb2)
	// prints {3,4,1000}
	fmt.Println(rb1)

	rb3 := gocroaring.New(1, 5)
	rb3.Or(rb1)

        // prints 1, 3, 4, 5, 1000
        i := rb3.Iterator()
        for i.HasNext() {
          fmt.Println(i.Next())
        }
        fmt.Println()

	fmt.Println(rb3.ToArray())
	fmt.Println(rb3)

	rb4 := gocroaring.FastOr(rb1, rb2, rb3) // optimized way to compute unions between many bitmaps
	fmt.Println(rb4)

	// next we include an example of serialization
	buf := make([]byte, rb1.SerializedSizeInBytes())
	rb1.Write(buf) // we omit error handling
	newrb, _ := gocroaring.Read(buf)
	if rb1.Equals(newrb) {
		fmt.Println("I wrote the content to a byte stream and read it back.")
	}

	fmt.Println(rb1.Stats()) // show the cardinality and the numbers of each type of container used.
}

Documentation

Current documentation is available at http://godoc.org/github.com/RoaringBitmap/gocroaring

Mailing list/discussion group

https://groups.google.com/forum/#!forum/roaring-bitmaps

Compatibility with Java RoaringBitmap library

You can read bitmaps in Go, Java, C, C++ that have been serialized in Java, Java, C, C++.

Documentation

Overview

Package gocroaring is an wrapper for CRoaring in go It provides a fast compressed bitmap data structure. See http://roaringbitmap.org for details.

Index

• Constants
• type Bitmap
  • func And(x1, x2 *Bitmap) *Bitmap
  • func AndNot(x1, x2 *Bitmap) *Bitmap
  • func FastOr(bitmaps ...*Bitmap) *Bitmap
  • func Flip(bm *Bitmap, rangeStart, rangeEnd uint64) *Bitmap
  • func New(x ...uint32) *Bitmap
  • func Or(x1, x2 *Bitmap) *Bitmap
  • func Read(b []byte) (*Bitmap, error)
  • func Xor(x1, x2 *Bitmap) *Bitmap
  • func (rb *Bitmap) Add(x ...uint32)
  • func (rb *Bitmap) And(x2 *Bitmap)
  • func (rb *Bitmap) AndCardinality(x2 *Bitmap) uint64
  • func (rb *Bitmap) AndNot(x2 *Bitmap)
  • func (rb *Bitmap) AndNotCardinality(x2 *Bitmap) uint64
  • func (rb *Bitmap) Cardinality() uint64
  • func (rb *Bitmap) Clear()
  • func (rb *Bitmap) Clone() *Bitmap
  • func (rb *Bitmap) Contains(x uint32) bool
  • func (rb *Bitmap) Equals(o interface{}) bool
  • func (rb *Bitmap) Flip(rangeStart, rangeEnd uint64)
  • func (rb *Bitmap) Intersect(x2 *Bitmap) bool
  • func (rb *Bitmap) IsEmpty() bool
  • func (rb *Bitmap) Iterator() IntIterable
  • func (rb *Bitmap) JaccardIndex(x2 *Bitmap) float64
  • func (rb *Bitmap) Maximum() uint32
  • func (rb *Bitmap) Minimum() uint32
  • func (rb *Bitmap) Or(x2 *Bitmap)
  • func (rb *Bitmap) OrCardinality(x2 *Bitmap) uint64
  • func (rb *Bitmap) Printf()
  • func (rb *Bitmap) Rank(x uint32) uint64
  • func (rb *Bitmap) Remove(x uint32)
  • func (rb *Bitmap) RemoveRunCompression() bool
  • func (rb *Bitmap) RunOptimize() bool
  • func (rb *Bitmap) Select(rank uint32) (uint32, error)
  • func (rb *Bitmap) SerializedSizeInBytes() int
  • func (rb *Bitmap) Stats() map[string]uint64
  • func (rb *Bitmap) String() string
  • func (rb *Bitmap) ToArray() []uint32
  • func (rb *Bitmap) Write(b []byte) error
  • func (rb *Bitmap) Xor(x2 *Bitmap)
  • func (rb *Bitmap) XorCardinality(x2 *Bitmap) uint64
• type IntIterable

Constants

const CRoaringMajor = C.ROARING_VERSION_MAJOR

const CRoaringMinor = C.ROARING_VERSION_MINOR

const CRoaringRevision = C.ROARING_VERSION_REVISION

Types

type Bitmap

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

Bitmap is the roaring bitmap

func And

func And(x1, x2 *Bitmap) *Bitmap

And computes the intersection between two bitmaps and returns the result

func AndNot

func AndNot(x1, x2 *Bitmap) *Bitmap

AndNot computes the difference between two bitmaps and returns the result

func FastOr

func FastOr(bitmaps ...*Bitmap) *Bitmap

FastOr computes the union between many bitmaps quickly, as opposed to having to call Or repeatedly. It might also be faster than calling Or repeatedly.

func Flip

func Flip(bm *Bitmap, rangeStart, rangeEnd uint64) *Bitmap

Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed,

func New

func New(x ...uint32) *Bitmap

New creates a new Bitmap with any number of initial values.

func Or

func Or(x1, x2 *Bitmap) *Bitmap

Or computes the union between two bitmaps and returns the result

func Read

func Read(b []byte) (*Bitmap, error)

Read reads a serialized version of the bitmap (you need to call Free on it once you are done)

func Xor

func Xor(x1, x2 *Bitmap) *Bitmap

Xor computes the symmetric difference between two bitmaps and returns the result

func (*Bitmap) Add

func (rb *Bitmap) Add(x ...uint32)

Add the integer(s) x to the bitmap

func (*Bitmap) And

func (rb *Bitmap) And(x2 *Bitmap)

And computes the intersection between two bitmaps and stores the result in the current bitmap

func (*Bitmap) AndCardinality

func (rb *Bitmap) AndCardinality(x2 *Bitmap) uint64

AndCardinality computes the size of the intersection between two bitmaps

func (*Bitmap) AndNot

func (rb *Bitmap) AndNot(x2 *Bitmap)

AndNot computes the difference between two bitmaps and stores the result in the current bitmap

func (*Bitmap) AndNotCardinality

func (rb *Bitmap) AndNotCardinality(x2 *Bitmap) uint64

AndNotCardinality computes the size of the difference between two bitmaps

func (*Bitmap) Cardinality

func (rb *Bitmap) Cardinality() uint64

Cardinality returns the number of integers contained in the bitmap

func (*Bitmap) Clear

func (rb *Bitmap) Clear()

Clear removes all elements from the bitmap

func (*Bitmap) Clone

func (rb *Bitmap) Clone() *Bitmap

Clone creates a copy of the Bitmap

func (*Bitmap) Contains

func (rb *Bitmap) Contains(x uint32) bool

Contains returns true if the integer is contained in the bitmap

func (*Bitmap) Equals

func (rb *Bitmap) Equals(o interface{}) bool

Equals returns true if the two bitmaps contain the same integers

func (*Bitmap) Flip

func (rb *Bitmap) Flip(rangeStart, rangeEnd uint64)

Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed,

func (*Bitmap) Intersect

func (rb *Bitmap) Intersect(x2 *Bitmap) bool

Intersect checks whether the two bitmaps intersect

func (*Bitmap) IsEmpty

func (rb *Bitmap) IsEmpty() bool

IsEmpty returns true if the Bitmap is empty (it is faster than doing (Cardinality() == 0))

func (*Bitmap) Iterator

func (rb *Bitmap) Iterator() IntIterable

Iterator creates a new IntIterable to iterate over the integers contained in the bitmap, in sorted order

func (*Bitmap) JaccardIndex

func (rb *Bitmap) JaccardIndex(x2 *Bitmap) float64

JaccardIndex computes the Jaccard index between two bitmaps

func (*Bitmap) Maximum

func (rb *Bitmap) Maximum() uint32

Maximum returns the largest of the integers contained in the bitmap assuming that it is not empty

func (*Bitmap) Minimum

func (rb *Bitmap) Minimum() uint32

Minimum returns the smallest of the integers contained in the bitmap assuming that it is not empty

func (*Bitmap) Or

func (rb *Bitmap) Or(x2 *Bitmap)

Or computes the union between two bitmaps and stores the result in the current bitmap

func (*Bitmap) OrCardinality

func (rb *Bitmap) OrCardinality(x2 *Bitmap) uint64

OrCardinality computes the size of the union between two bitmaps

func (*Bitmap) Printf

func (rb *Bitmap) Printf()

Printf writes a description of the bitmap to stdout

func (*Bitmap) Rank

func (rb *Bitmap) Rank(x uint32) uint64

Rank returns the number of values smaller or equal to x

func (*Bitmap) Remove

func (rb *Bitmap) Remove(x uint32)

Remove the integer x from the bitmap

func (*Bitmap) RemoveRunCompression

func (rb *Bitmap) RemoveRunCompression() bool

RemoveRunCompression Remove run-length encoding even when it is more space efficient return whether a change was applied

func (*Bitmap) RunOptimize

func (rb *Bitmap) RunOptimize() bool

RunOptimize the compression of the bitmap (call this after populating a new bitmap), return true if the bitmap was modified

func (*Bitmap) Select

func (rb *Bitmap) Select(rank uint32) (uint32, error)

Select returns the element having the designated rank, if it exists

func (*Bitmap) SerializedSizeInBytes

func (rb *Bitmap) SerializedSizeInBytes() int

SerializedSizeInBytes computes the serialized size in bytes the Bitmap.

func (*Bitmap) Stats

func (rb *Bitmap) Stats() map[string]uint64

Stats returns some statistics about the roaring bitmap.

func (*Bitmap) String

func (rb *Bitmap) String() string

String creates a string representation of the Bitmap

func (*Bitmap) ToArray

func (rb *Bitmap) ToArray() []uint32

ToArray creates a new slice containing all of the integers stored in the Bitmap in sorted order

func (*Bitmap) Write

func (rb *Bitmap) Write(b []byte) error

Write writes a serialized version of this bitmap to stream (you should have enough space)

func (*Bitmap) Xor

func (rb *Bitmap) Xor(x2 *Bitmap)

Xor computes the symmetric difference between two bitmaps and stores the result in the current bitmap

func (*Bitmap) XorCardinality

func (rb *Bitmap) XorCardinality(x2 *Bitmap) uint64

XorCardinality computes the size of the symmetric difference between two bitmaps

type IntIterable

type IntIterable interface {
	HasNext() bool
	Next() uint32
}

IntIterable allows you to iterate over the values in a Bitmap