Implement BSI Addition

[jacksonrnewhouse]

Bit Slice Indexes basically provide a map[int]int with some very fast operations. One operation that can be implemented against BSIs is addition, which basically sums up the values by key for two BSI's. This can be entirely accomplished using bitwise arithmetic. The primary functions you need are addToValues(*Bitmap) and addDigit(*Bitmap, int). pseudo-code for the inplace versions is something like

func (bsi *BSI) addToValues(bitmap *Bitmap) { 
    bsi.eBM.Or(bitmap)
}

func (bsi *BSI) addDigit(bitmap *Bitmap, digit i) {
    carry := roaring.And(bsi.bA[i], bitmap)
    bsi.bA[i].Xor(bitmap)
    if carry.GetCardinality() > 0 {
        addDigit(carry, i+1)
    }
}

[guymolinari]

This has been implemented. I am preparing a pull request with this and some other enhancements.

[lemire]

@guymolinari Did you close the issue deliberately ?

[guymolinari]

I am testing the new feature now and will submit a pull request. But Yes.

…

On Tue, Sep 8, 2020, 8:28 PM Daniel Lemire ***@***.***> wrote: @guymolinari <https://github.com/guymolinari> Did you close the issue deliberately ? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#260 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADZZAUWVCQUAHJM4KXF3SITSE3DZVANCNFSM4PE4KLBQ> .

[lemire]

@guymolinari My proposal is to reopen the issue and close it when the PR will have been merged. Less confusing that way.

[guymolinari]

Sounds good. Didn't know the process. My apologies.

…

On Wed, Sep 9, 2020, 3:46 PM Daniel Lemire ***@***.***> wrote: @guymolinari <https://github.com/guymolinari> My proposal is to reopen the issue and close it when the PR will have been merged. Less confusing that way. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#260 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADZZAUSNHOQUA7P6NVBH23LSE7LSFANCNFSM4PE4KLBQ> .

[lemire]

Sounds good. Didn't know the process. My apologies.

Do not apologize.

I have reopened the issue.

When creating a pull request, add "Fixes #260" as part of your description. This will link the issue with the PR. You can also link the issue explicitly by entering it the addresses at the right locations in the web pages.

[guymolinari]

Cool. I have written unit test coverage of the new features. Just wanted to do some more application testing for good measure.

…

On Wed, Sep 9, 2020, 8:23 PM Daniel Lemire ***@***.***> wrote: Sounds good. Didn't know the process. My apologies. Do not apologize. I have reopened the issue. When creating a pull request, add "Fixes #260 <#260>" as part of your description. This will link the issue with the PR. You can also link the issue explicitly by entering it the addresses at the right locations in the web pages. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#260 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADZZAUQT6ZCYKMLNI6FGDALSFAMAVANCNFSM4PE4KLBQ> .

[lemire]

Issue resolved by @guymolinari

[Smallhi]

@guymolinari For BSI, the function transpose can be used for vectorization. I found the fucntion use a RoraingBitmap to return. It make me confused. Could u tell me how can we use it to process groupBy computing? I think the return value RoraingBitmap discard the original Info.
Thanks a lot!

[guymolinari]

It is designed to transpose values in the BSI and convert those values to columnIDs in a Bitmap. Cheers, Guy

…

On Fri, Nov 27, 2020 at 12:37 AM hhl ***@***.***> wrote: @guymolinari <https://github.com/guymolinari> For BSI, the function transpose can be used for vectorization. I found the fucntion use a RoraingBitmap to return. It make me confused. Could u tell me how can we use it to process groupBy computing? I think the return value RoraingBitmap discard the original Info. Thanks a lot! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#260 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADZZAUV7CGJWALWJS77D43TSR5QMZANCNFSM4PE4KLBQ> .

[Smallhi]

@guymolinari If you don't mind me asking，could you give me an example of how to "transpose values in the BSI and convert those values to columnIDs in a Bitmap". That would be very useful for me!
Thanks a lot!

[guymolinari]

The best way to understand an open source project (at least one that is properly run), is to look at the test cases.

…

On Sat, Nov 28, 2020 at 9:06 PM hhl ***@***.***> wrote: @guymolinari <https://github.com/guymolinari> If you don't mind me asking，could you give me an example of how to "transpose values in the BSI and convert those values to columnIDs in a Bitmap". That's very usefule for me! Thanks a lot! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#260 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADZZAUSFBMVR5R3ZO3KYXKTSSHJGXANCNFSM4PE4KLBQ> .

[Smallhi]

@guymolinari I had read and run all your code .... Thanks anyway!