Re: ***Bitmapped Indexing API Beta - Now Available***

Patrick Gainer <gainer@64k.com> wrote: >Deon du Plessis wrote: >> 3) THE ROUTINES OVERCOME THE PROBLEMS ASSOCIATED WITH HIGH CARDINALITY >> >> DATA. This is basically acheived by breaking the data into sections. >> If there is no data in a particular section, a BM for that section is >> not stored. E.g. A bit-map is divided into 10 sections, each >> representing 10,000 bit positions, i.e. a 100,000 bit BM. If position >> 1, 10,000, and 100,000 is set, only 3 - 6 bytes at most would be >> required to store the BM positions. (This excludes section header >> information, which is about 8 bytes for every section, i.e. 24 bytes >> in the example above) >So let's try out a high cardinality example. How many bits or bytes >do your indexes require for a data set with 1,000,000 items >present, each on average about 7-15 bits away from the last item? >I'd be surprised if you needed less than 15,000,000/8 bytes. >Pat Yeah, but so what? This library is not magic; it's just a (so far as I've seen) pretty cleanly-designed package for manipulating bitmaps, with a particular style of compression stated up front --- good for some data models, lousy for others. Yes, of course a byte tree amounts to coding each three bits of a number as a byte. Permuting the input numbers to make numbers cluster on the least-significant bits is a problem in ordered perfect hashing. There are more effective ways of handling high cardinality than that of this package. I'm currently comparing this package against is another one that's based on flat streams with zero-run encoding, btw. The trade-offs are always there. If you go for minimal size of a bitmap representing a single bit, you lose out on speed of random access., or you add complication in decoding (multiple representations). If you optimize for altering bits, you lose on compression. Etcetera. ----- As an aside, and a comment: the func ref is HUGE. Sheesh, didn't ways of factoring out orthogonal functions jump out at you, Deon? --------- Engineers believe that the equations approximate reality. Physicists believe that reality approximates the equations. Mathematicians never make the connection.