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

Pilosa: An open source, distributed index

pilosa.com

Post reply on HN
Print view View original

21–30 of 30 posts

Re: Pilosa: An open source, distributed index

#21

Post by jaffee »

dTal wrote: post #16
fnordsensei wrote: post #11

Earlier quoted context omitted.

Well, you could decide that one axis is monkeyIndex, and the other is amountOfBananasOwned, and have a quite compact representation of which monkey owns what number of bananas. I.e., decide on a symbolic meaning for the axes rather than converting data wholesale.

That doesn't sound compact at all! Every monkey's banana count uses a fixed number n of bits, where n = max(amountOfBananasOwned). That's horribly inefficient, when an ordinary binary counter uses n = log2(amountOfBananasOwned). Which is not a criticism of Pilosa - I'm sure it's doing something very clever - I just don't understand what.

Bit-sliced indexing is the clever magic here. This post goes very deep on it https://www.pilosa.com/blog/range-encoded-bitmaps/

But really, you use one bitmap for each binary bit of an integer, and it turns out you can generate arbitrary range queries on your dataset by doing various combinations of boolean operations on those bitmaps.

Re: Pilosa: An open source, distributed index

#23

Post by kazinator »

jaffee wrote: post #10
dTal wrote: post #7

Earlier quoted context omitted.

>converting data such that it is represented in ones and zeros er, what? Isn't it all? >This dramatically reduces the size huh? There is no symbolic encoding less efficient for length than binary.

Good catch... that sounds pretty silly. It should probably read more like "converting relationships to be represented by single bits" As a concrete example, we took the NYC taxi ride data set which is something like 300GB of CSV files and when it was indexed in Pilosa, the total size of all the bitmap files was closer to 40GB.

It's quite clear to hopefully everyone that a matrix of bits can represent a DAG. That's called an adjacency matrix.

What's not obvious is what we're associating with what in the NYC taxi ride data set.

A bitmap can also represent a set: the bit positions denote enumerated element symbols, and the value indicates whether that element is present.

So we rearrange the NYC taxi ride data into a data structure based on graphs and sets, and make large bitmaps?

Re: Pilosa: An open source, distributed index

#24

Post by kazinator »

ytklx wrote: post #14
fnordsensei wrote: post #11

Earlier quoted context omitted.

Well, you could decide that one axis is monkeyIndex, and the other is amountOfBananasOwned, and have a quite compact representation of which monkey owns what number of bananas. I.e., decide on a symbolic meaning for the axes rather than converting data wholesale.

This is very similar to how Pilosa saves integers. https://www.pilosa.com/docs/latest/data-model/#bsi-range-enc...

Okay, so if we store a three-bit 5 as 101 (in columns 0-2) and an additional "non-null" indicating 1 in column 3, we're saying that we have a row that has an association with columns 0, 2 and 3, but not with 1. Since, you know:

> The central component of Pilosa’s data model is a boolean matrix. Each cell in the matrix is a single bit; if the bit is set, it indicates that a relationship exists between that particular row and column.

But why do I want my integers sliced apart into these associations?

Re: Pilosa: An open source, distributed index

#25

Post by kazinator »

ytklx wrote: post #12
dTal wrote: post #7

Earlier quoted context omitted.

>converting data such that it is represented in ones and zeros er, what? Isn't it all? >This dramatically reduces the size huh? There is no symbolic encoding less efficient for length than binary.

Pilosa uses roaring bitmaps to store the data. Roaring bitmaps are compressed and performing bit operations on them is very efficient since they don't require uncompressing the whole bitmap to perform bit operations.

The Roaring bitmap paper is equally opaque in this regard. I easily understand everything about the bitmaps themselves: the compression and various operations. But then they say that they tested it on some Census1881 data, and I'm thinking, what, how? How do you grind census data into a bitmap? And is everything in the bitmap, including people's names and such, or does the bitmap refer to objects that are not in the bitmap?

Re: Pilosa: An open source, distributed index

#26

Post by kazinator »

jaffee wrote: post #21
dTal wrote: post #16

Earlier quoted context omitted.

That doesn't sound compact at all! Every monkey's banana count uses a fixed number n of bits, where n = max(amountOfBananasOwned). That's horribly inefficient, when an ordinary binary counter uses n = log2(amountOfBananasOwned). Which is not a criticism of Pilosa - I'm sure it's doing something very clever - I just don't understand what.

Bit-sliced indexing is the clever magic here. This post goes very deep on it https://www.pilosa.com/blog/range-encoded-bitmaps/ But really, you use one bitmap for each binary bit of an integer, and it turns out you can generate arbitrary range queries on your dataset by doing various combinations of boolean operations on those bitmaps.

This page perpetrates an apparent contradiction. Starts off with:

> Pilosa is built around the concept of representing everything as bitmaps.

What this literally means is that not a single datum is stored that is not in the bitmap.

But then the diagrammed examples look like this:

                manatee loris sea_horse
  Vertebrate    1       1     1
  Invertebrate  0       0     0
  Breathes Air  1       1     0
Pardon my ignorance, but I see here a bitmap of 9 bits plus six character strings that are obviously not inside that bitmap.

If those strings are removed, the bitmap means jack squat.

Are they understood to be in another bitmap?

Re: Pilosa: An open source, distributed index

#28

Post by jaffee »

kazinator wrote: post #26
jaffee wrote: post #21

Earlier quoted context omitted.

Bit-sliced indexing is the clever magic here. This post goes very deep on it https://www.pilosa.com/blog/range-encoded-bitmaps/ But really, you use one bitmap for each binary bit of an integer, and it turns out you can generate arbitrary range queries on your dataset by doing various combinations of boolean operations on those bitmaps.

This page perpetrates an apparent contradiction. Starts off with: > Pilosa is built around the concept of representing everything as bitmaps. What this literally means is that not a single datum is stored that is not in the bitmap. But then the diagrammed examples look like this: manatee loris sea_horse Vertebrate 1 1 1 Invertebrate 0 0 0 Breathes Air 1 1 0 Pardon my ignorance, but I see here a bitmap of 9 bits plus…

One does have to maintain some understanding of the how integer row and column ids are linked to what they actually represent.

Sometimes this is a function which might map (for example) row 3 to the letter 'd', 4 to 'e', and so on. Sometimes it has to be a lookup table which can be kept within Pilosa, or externally. Sometimes the IDs map directly to what they represent (day-of-month, year, passenger count, etc.)

So strictly speaking, not everything is a bitmap, but the bulk of the heavy lifting in terms of serving queries is computation on bitmaps.

Re: Pilosa: An open source, distributed index

#29

Post by toddgruben »

kazinator wrote: post #24
ytklx wrote: post #14

Earlier quoted context omitted.

This is very similar to how Pilosa saves integers. https://www.pilosa.com/docs/latest/data-model/#bsi-range-enc...

Okay, so if we store a three-bit 5 as 101 (in columns 0-2) and an additional "non-null" indicating 1 in column 3, we're saying that we have a row that has an association with columns 0, 2 and 3, but not with 1. Since, you know: > The central component of Pilosa’s data model is a boolean matrix. Each cell in the matrix is a single bit; if the bit is set, it indicates that a relationship exists between that particular…

So that you can perform very fast range queries on deeply complex filters on those associations

Re: Pilosa: An open source, distributed index

#30

Post by jaffee »

shuzchen wrote: post #27

Any chance there'll be some built-in support to perform collaborative filtering? Seems like a database of relations like this would be awesome for user-based collaborative filtering.

Great question! We have actually done some experiments with this in the past and will likely be rolling out features like this on top of Pilosa as part of Molecula https://www.molecula.com/is-your-data-ai-ready/
Post reply on HN