An easy way to get the storage overhead of the PH-Tree?

[MaoZiming]

Hi all,

I want to ask if there is an easy way (like a function call) to obtain the storage overhead of the PH-Tree? Thank you!

Best, Ziming

[tzaeschke]

Not at the moment.

A couple of points first:

• The storage overhead depends a lot on the dataset, i.e. dimensionality and point distribution.
• The storage overhead also depends on the storage representation. The representation is chosen depending on the dimensionality, but it is configurable (well, hardcoded) here
• This implementation does not use prefix sharing to reduce storage. This can be useful, see below.

What can you do?

• This implementation doesn't use prefix-sharing. This means that the storage overhead is equal to total storage required (if you can measure that) minus the storage required for storing coordinates (which you can calculate, i.e. for 3D 64bit double: storage = n_entries 3 8byte.
• Depending on the storage representation (especially for d <=3) you can use PhTreeDebugHelper::GetStats(tree)::GetNodeCount() to get the number of nodes. For d<=3 the overhead should correlates strongly with the number of nodes. You can try to calculate this overhead (a Node has an array_map of 8 PhFlatMapPair<Entry>) but it may be easier to mesasure it onec (create a tree with a million entries and calculate the overhead per node). This overhead per node should be fixed, so for all future trees you can simply multiply the number of node with the node overhead. Note: for d > 3 this approach will be less accurate, but with larger trees (1000+ entries?) you should still get a halfway accurate result.

N.b. There is a method PhTreeDebugHelper::GetStats(tree)::GetCalculatedMemSize(). However, I think this never got really implemented so I think it simply returns the entry count, which is not helpful.

[improbable-til]

Please reopen if there are further questions.