Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Optimal indexing of database costs only 2.33 bits/element (linear not n log(n) )
22 views
Skip to first unread message
dud...@gmail.com
Jul 4, 2012, 11:41:11 AM7/4/12
to
We would think that the amount of information required to distinguish elements by some unique identifiers grows with n log(n) ... but it turns out that it can be compressed using linearly growing amount of information. The trick is that we don't need the information about the order of these identifiers, saving log(n!)~ nlog(n) bits of information.
Specifically, to encode minimal prefix tree required to distinguish hash values of elements, there is asymptotically required 2.77 bits/elements and it can further reduced to 2.33 bits/element:
http://arxiv.org/abs/1206.4555
Where such extremely thrifty encoding might be useful?
Specifically, to encode minimal prefix tree required to distinguish hash values of elements, there is asymptotically required 2.77 bits/elements and it can further reduced to 2.33 bits/element:
http://arxiv.org/abs/1206.4555
Where such extremely thrifty encoding might be useful?
0 new messages