[math-fun] Asymptotically zero memory wasted inside dictionaries
Consider a "dictionary" containing N items, where we support insert, delete, search-for, read-access, replace (write-access) in O(L) steps each, where L=logN. This is implementable using "balanced binary trees" such as "red black trees" or "Aa trees" which employ 2 pointers plus some small number (e.g. 1) of bits per data item. Also it can be done using "splay trees" using 2 pointers per item, and no extra bits needed, but speed guarantees now only amortized, not worst case (long pauses occasionally possible). If data items are same size as a pointer, this is a major WASTE OF MEMORY: 3X more consumed than the data itself. --------------- I now point out (which may or may not be a new observation -- I'd guess probably not new?) that there is a way to do this with far less memory wasted, and probably more efficient at the same time. (The reason for alleged "greater efficiency" is because of memory caching effects and the existence of special instructions on many processors for high speed shifts of arrays.) Let K>1 be a constant (or it could even grow slowly with N). Make each node of the tree contain not one, but rather an array of order L items consecutive in the ordering. Each node's array size is fixed, but the array may be only partly filled, knows how many items it contains. We agree that each node's array will always be within fraction 1/K of being full. To search for an item X, walk to right child if X>max array element, to left child if X<min, and binary search within the array, otherwise. To insert a new item, just do a linear insert into the array, if it is not already full; ditto for delete if contains enough items (occupancy count changed by +- 1). If it is desired to insert an item into an already-full node (or delete one from a node which has its minimum allowed occupancy; I'll focus here on insert), then we look for other nodes adjacent to this one in the ordering. We find the J closest nodes where J=1,2,...,K until finding one that is not full. Then we redistribute the array items within these J nodes to equalize their occupancy counts to within 1 and insert the new item. This all takes J times longer than a single search. If on the other hand all J=K of these nodes have full arrays, then we create a new node, redistribute items among the K+1 nodes' arrays, and insert the new item into the correct node's array, and finally, using standard balanced tree (or splay tree) methods, insert the new node into the tree. CONCLUSION: Search & access requires O(L) steps, L=logN. Insert takes O(L) steps usually, occasionally O(J*L) steps with 1<J<K, and even more rarely O(K*L) steps. Ditto delete. Here K is an arbitrary constant. If desired, we can guarantee the rareness of the longer-time kind of steps by adding "hysteresis" to the data structure, i.e. it is ok to delete until a node's array has fraction 2/K unfilled, but any multi-node redistribution is arranged to assure at most 1/K fraction unfilled. In that case, the longer-time steps can occur only a fraction K/L of the time at most, so the AMORTIZED-average time per operation is assured to be O((K/L)*K*L + L) = O(K*K+L). So we can choose K to be anywhere between 1 and sqrt(logN) while still assuring the amortized operation time is O(logN), and worst case operation time (using balanced trees) is O(logN)^2. With splay trees the worst case time could be as large as order N/L. In this case, the "waste" of memory is: 2 pointers and a few bits per K data items, which (provided K grows with N to infinity such as sqrt(logN)) asymptotically tends to ZERO waste of memory. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Smells like B trees to me. On Jun 22, 2014 10:32 AM, "Warren D Smith" <warren.wds@gmail.com> wrote:
Consider a "dictionary" containing N items, where we support insert, delete, search-for, read-access, replace (write-access) in O(L) steps each, where L=logN.
This is implementable using "balanced binary trees" such as "red black trees" or "Aa trees" which employ 2 pointers plus some small number (e.g. 1) of bits per data item.
Also it can be done using "splay trees" using 2 pointers per item, and no extra bits needed, but speed guarantees now only amortized, not worst case (long pauses occasionally possible).
If data items are same size as a pointer, this is a major WASTE OF MEMORY: 3X more consumed than the data itself.
---------------
I now point out (which may or may not be a new observation -- I'd guess probably not new?) that there is a way to do this with far less memory wasted, and probably more efficient at the same time. (The reason for alleged "greater efficiency" is because of memory caching effects and the existence of special instructions on many processors for high speed shifts of arrays.) Let K>1 be a constant (or it could even grow slowly with N).
Make each node of the tree contain not one, but rather an array of order L items consecutive in the ordering. Each node's array size is fixed, but the array may be only partly filled, knows how many items it contains. We agree that each node's array will always be within fraction 1/K of being full.
To search for an item X, walk to right child if X>max array element, to left child if X<min, and binary search within the array, otherwise.
To insert a new item, just do a linear insert into the array, if it is not already full; ditto for delete if contains enough items (occupancy count changed by +- 1).
If it is desired to insert an item into an already-full node (or delete one from a node which has its minimum allowed occupancy; I'll focus here on insert), then we look for other nodes adjacent to this one in the ordering. We find the J closest nodes where J=1,2,...,K until finding one that is not full. Then we redistribute the array items within these J nodes to equalize their occupancy counts to within 1 and insert the new item. This all takes J times longer than a single search.
If on the other hand all J=K of these nodes have full arrays, then we create a new node, redistribute items among the K+1 nodes' arrays, and insert the new item into the correct node's array, and finally, using standard balanced tree (or splay tree) methods, insert the new node into the tree.
CONCLUSION: Search & access requires O(L) steps, L=logN. Insert takes O(L) steps usually, occasionally O(J*L) steps with 1<J<K, and even more rarely O(K*L) steps. Ditto delete. Here K is an arbitrary constant. If desired, we can guarantee the rareness of the longer-time kind of steps by adding "hysteresis" to the data structure, i.e. it is ok to delete until a node's array has fraction 2/K unfilled, but any multi-node redistribution is arranged to assure at most 1/K fraction unfilled. In that case, the longer-time steps can occur only a fraction K/L of the time at most, so the AMORTIZED-average time per operation is assured to be O((K/L)*K*L + L) = O(K*K+L).
So we can choose K to be anywhere between 1 and sqrt(logN) while still assuring the amortized operation time is O(logN), and worst case operation time (using balanced trees) is O(logN)^2. With splay trees the worst case time could be as large as order N/L.
In this case, the "waste" of memory is: 2 pointers and a few bits per K data items, which (provided K grows with N to infinity such as sqrt(logN)) asymptotically tends to ZERO waste of memory.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Any advantage over standard B trees?
--Well, at least based on http://en.wikipedia.org/wiki/B-tree the B tree wastes 1-2 pointers worth of memory per data item in non-leaf nodes, and the leaf nodes could be made to contain no pointers. So in the limit of large branching factor B, the leaf nodes dominate the scene with only fraction of order 1/B of the data in non-leaf nodes, and if we make B of order logN, then this is superior to my trees by a sqrt(logN) factor as far as memory waste is concerned. So I think Tom Rokicki is right: B trees are superior. [My trees probably do have some minor advantages though, since you can try to steal any property of some breed of binary balanced trees, such as O(1) pointer changes per op?]
On 6/22/14, Warren D Smith <warren.wds@gmail.com> wrote:
Any advantage over standard B trees?
--...I think Tom Rokicki is right: B trees are superior.
--wait a cotton picking minute. B trees fill their arrays with t to 2t elements hence may have fill fraction 50%. That is a big memory waste. My trees have asymptotically zero memory waste. That being said, it presumably is possible to change the parameters and algorithms of B trees and I think if you do so right, you'd get something similar to my trees in performance. Which would then be better? I am not sure.
There has been some research on what is called "succinct representation(s)" and/or "succinct data structures". Suggest to web-search these to get a picture of what has been done. Btw. for trees the (non)locality of memory references is very important in practice. IIRC this is a strong point in favor of B-trees (and the variants of them). IIRC (again) some of the modern file systems use (variants of) them. Best, jj
participants (3)
-
Joerg Arndt -
Tom Rokicki -
Warren D Smith