Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bitmap Indexes in Go: Search Speed (2019)

habr.com

Post reply on HN
Print view View original

11–20 of 40 posts

Re: Bitmap Indexes in Go: Search Speed (2019)

#11

Post by skingkong »

iampims wrote: post #2

Bitmaps can also be used for computing funnels: https://vikramoberoi.com/using-bitmaps-to-run-interactive-re...

100%, and are freaking fast...and pretty efficient, especially for high throughput applications tracking tons of changing data. We've found bitmaps handle updates, inserts, and schema changes really elegantly - and quickly (like sub-second). Depending on the use case, looking at cohorts MoM or YoY that freshness doesn't entirely matter, but computing cohorts in real-time hour-over-hour, or even minute-over-minute, for in-app actions/personalization is insanely valuable to keep users engaged (or what ever entity type you are analyzing and taking action on, whether it's devices, nodes across a network, etc).

Re: Bitmap Indexes in Go: Search Speed (2019)

#12

Post by eurasiantiger »

JAA1337 wrote: post #8
iampims wrote: post #2

Bitmaps can also be used for computing funnels: https://vikramoberoi.com/using-bitmaps-to-run-interactive-re...

I think it's fair to say that the use cases for bitmaps have not yet been fully explored. I believe their use in areas of analytics and OLAP/RTOLAP will continue to grow as the desire to infer and target demo's across households increases.

Isn’t Lucene already a household name?

Re: Bitmap Indexes in Go: Search Speed (2019)

#13

Post by JustG »

pjmlp wrote: post #6
jimbokun wrote: post #5

Very approachable introduction to this data structure. The assembly implementation, though, reminded me of the stone soup story. Where a stranger is boiling a rock in a pot of water, and the townspeople intrigued by the idea of stone soup bring various ingredients to add to it and everyone is shocked that "stone soup" could taste so good. The "Go" implementation ends up being pretty much all assembly by the end, in a…

Going off-topic, a typical Portuguese soup actually, worth a visit to a "Loja das Sopas" in a nearby shopping mall when in Portugal.

Some of the best seafood ever is in Lisbon, Portugal, not to mention the Algrave..

Re: Bitmap Indexes in Go: Search Speed (2019)

#14

Post by clowen »

eurasiantiger wrote: post #12
JAA1337 wrote: post #8

Earlier quoted context omitted.

I think it's fair to say that the use cases for bitmaps have not yet been fully explored. I believe their use in areas of analytics and OLAP/RTOLAP will continue to grow as the desire to infer and target demo's across households increases.

Isn’t Lucene already a household name?

Probably not, first thought I had was Lucerne dairy products.

Re: Bitmap Indexes in Go: Search Speed (2019)

#15

Post by manimino »

Writing an object indexer is a fun project. My Python indexer, ducks [1], went through a lot of the same development stages, such as supporting only exact-value matches at first. I tried binning too, but ultimately using a BTree was simpler and performed well enough (500ns for a log-n tree traversal, vs 50ns hash).

Still looking for a way to apply bitmap indexing in ducks; it would surely speed up multi-index queries, but I haven't found an implementation that's worth the tradeoffs yet.

[1] https://ducks.readthedocs.io/en/latest/

Re: Bitmap Indexes in Go: Search Speed (2019)

#16

Post by JAA1337 »

eurasiantiger wrote: post #12
JAA1337 wrote: post #8

Earlier quoted context omitted.

I think it's fair to say that the use cases for bitmaps have not yet been fully explored. I believe their use in areas of analytics and OLAP/RTOLAP will continue to grow as the desire to infer and target demo's across households increases.

Isn’t Lucene already a household name?

Not sure I understand your point. Can you clarify some?

Re: Bitmap Indexes in Go: Search Speed (2019)

#17

Post by gthrone »

eurasiantiger wrote: post #12
JAA1337 wrote: post #8

Earlier quoted context omitted.

I think it's fair to say that the use cases for bitmaps have not yet been fully explored. I believe their use in areas of analytics and OLAP/RTOLAP will continue to grow as the desire to infer and target demo's across households increases.

Isn’t Lucene already a household name?

I didn't realize Lucene used their own flavor of roaring bitmaps! Super Cool. I certainly think of search when it comes to Lucene, where as the cited material from Vikram & FeatureBase are targeting more general analytics.

Re: Bitmap Indexes in Go: Search Speed (2019)

#18

Post by clowen »

jimbokun wrote: post #5

Very approachable introduction to this data structure. The assembly implementation, though, reminded me of the stone soup story. Where a stranger is boiling a rock in a pot of water, and the townspeople intrigued by the idea of stone soup bring various ingredients to add to it and everyone is shocked that "stone soup" could taste so good. The "Go" implementation ends up being pretty much all assembly by the end, in a…

The story as I know it:

Three soldiers wander into a town and watch as the townspeople shutter themselves into their homes.

The first two soldiers, out of rations, start to knock on doors and asking if anyone has any food, but no one answers. The third says: "I have an idea, start a cooking fire in the town square and get some water boiling. I've got to find the right ingredient."

They do as they were told, and the third makes a show of trying to find just the right stone. Making sure the town hears and sees them. They bring the "perfect" stone back, and place it in the pot of boiling water. The other two soldiers start to question, but the third tells them to just shut up and watch.

After boiling a stone for 10 to 15 minutes, one of the villagers comes out to ask what the soldiers are doing. "Making stone soup." replies the soldier, "Though it is usually better with some potatoes or carrots."

The villager lights up, "I have carrots!" They run to their home, come back with a handful of carrots, and add them to the soup. Seeing this, other villagers begin to emerge from their homes, and each suggesting a new ingredient.

Over and over this happens until someone tries to put raw salmon in and is thrown out of the town. I mean, until they have a full and hardy stew going, with more than enough to feed the entire town.

The morale of the story being to always have enough rations.

Re: Bitmap Indexes in Go: Search Speed (2019)

#19

Post by pjmlp »

JustG wrote: post #13
pjmlp wrote: post #6

Earlier quoted context omitted.

Going off-topic, a typical Portuguese soup actually, worth a visit to a "Loja das Sopas" in a nearby shopping mall when in Portugal.

Some of the best seafood ever is in Lisbon, Portugal, not to mention the Algrave..

As northern Portuguese I beg to differ. :)
Post reply on HN