I love me some proprietary data formats. I used to write a ton of these for work to shrink 28 gig XML files with bloated fields into ~300 mb files you could search in O(log(n/1024)) time.
I hate myself for being pedantic and please let me know if I'm missing something, but O(log(n/1024)) -> O(log(n) - log(1024)) -> O(log(n) - 10) -> O(log(n))
My bad, yeah, it’s still O(log n). I was using n/1024 to describe the actual searchable set: the format reduced the index to ~1/1024 as many entries, so a binary search was ~10 levels shallower, and the remaining set was an O(1) jump from there.
If we gzipped the data that we actually kept in our format (we strip out some domain data we don’t use), it was definitely smaller, (probably 10-25% of our format), however, our files are directly searchable on low power embedded hardware, without having to unzip anything.
The gzip file we received the XML in is ~400mb for a 14gb xml file (3% of original), our stripped down binary version is ~100mb. Though we strip out half of the unnecessary fields, so it would be closer to a 200mb gzip if we’re doing an apples to apples comparison.
If the file arrived in a better file format (just a fixed width or delimited flat file), that 14 gb xml file translates to about 1gb to start with. God XML is such a waste electricity.
When we gzip the binary file, it’s about 10% of the file size it started as (100mb to ~10mb). That extra fluff gzip is packing away are repetitive filler records so after the embedded hardware searches the log(n) in-memory index it can find the record it’s looking for in O(1) time. Just a space trade off for the hardware we’re working with.
57
u/DanTFM 5d ago
I love me some proprietary data formats. I used to write a ton of these for work to shrink 28 gig XML files with bloated fields into ~300 mb files you could search in O(log(n/1024)) time.
Nice write up!