1

I have a collection of many millions of objects, each with a unique id, each composed of tens to thousands of values. Values in this case are simply arrays of floats, with dimensions in the tens to a hundred.

The same value can be present in different objects, thus duplicate values are many, taking up to 70% of the volume of the data.
For now, the id is associated to a contiguous slice which is used to index the list of values. It's nice and fast to index contiguous slices of the list, which is mmaped and stays on disk.
Once created, the structure is read-only. No updates are necessary.

I'd like however to trade some speed for a non negligible gain of space, by keeping a list of the unique values only, and gather them to construct an object when I lookup the structure by the object id. But for now I can't think of anything else than keeping a list of indices for each id and doing what's essentially random access on the list of values, which can be very slow for thousands of indices.
Is there a cleverer way to retrieve the values without scattered access to the list ?

The objects/values are requested many times per second. The list of unique values could fit in RAM when duplicates are removed.

Thank you.

8
  • 1
    Do you assign IDs to the unique values and store them in an associative array? That should give you constant-time lookups. Apr 15, 2022 at 17:18
  • 2
    Probably need to see an example, plus need to know create/update vs. read, since most algorithms trading off space & speed will also alter the balance between create/update vs. read.
    – Erik Eidt
    Apr 15, 2022 at 19:01
  • 1
    I updated my question, as it was quite unintentionally vague. Values are arrays of floats. As to why I need tu reduce space, it's simply because as of now these structures take quite a lot of disk space, and the storage resource can be scarse and disk usage has to be tightly monitored.
    – alkonost
    Apr 16, 2022 at 15:06
  • 1
    Did you try indexing the contents of those arrays? Would be the most straightforward thing to do if performance is tolerable for you.
    – bobah
    Apr 16, 2022 at 15:22
  • 1
    Need some more info: What is the size (in bits) of a float on your system? 32? 64? More? How many unique values can you have? A few thousands? Millions? More? Depending on these answers you may gain a lot, not gain much, or even loose space by indexing your values. Apr 19, 2022 at 15:02

2 Answers 2

1

Assuming you can't drop any of the non-duplicate values. Hashing the values might be out of the question.

A fairly effective way to find duplicates would be to sort them, and avoid the duplicates, since these entities will only be read afterwards. In java, you can use a TreeSet<byte[]>(ByteUtil::compareByteArrays) to sort the values.

The compareByteArray implementation just compares each value on the two bytes until one of the arrays end. When there is a duplicate, the TreeSet::add method will return true and you can skip adding it to the DS you will be using for the look up.

The runtime will be O(n*log(n)*lengthOfArray). However, I imagine most compares won't check more than a few numbers. If there are a lot of duplicates, the log(n), would also be reduced.

0

Say you have 10^7 objects, with 10^3 values, where each value is 10^3 bytes, and lets say 10% of the data is unique to keep it simple, so on the order of 10^12 bytes or 1TB of data, give or take a magnitude.

This would be fairly large to keep in memory, but not infeasible given a large server. If you can keep everything in ram you would probably not need to care about any random access times. One object should be on the order of 1MB, and fetching this from ram should be on the order of 10 microseconds, so handling a few hundred requests per second should really not be an issue.

As far as I can tell, a good SSD should be able to process on the order of 10k IOPS of about 1kB each. Since each request would require about 1k random reads I would expect around 10 requests per second to be handled fairly well, possibly more if using higher end drives, more drives, or some memory for caching.

So If I'm understanding your requirements correctly you might be able to solve your problem by just using enough memory or a sufficiently fast disk system. I would probably try using some fast compression algorithm, like lz4, to compress each value individually. This might not work well, but should be fairly simple to try, so might be worth to test at least.

You might be able to create groups of values that are all shared between multiple objects to allow them to be read in one go. I do not think it is possible to find the optimal grouping within a reasonable amount of time, but there might be some optimization algorithms that could produce a decent result. But I would not bother with this unless simpler methods failed to produce the required performance.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.