ASortedListDataStructurefor32BitKeys.ppt

1、Engineering a Sorted List Data Structure for 32 Bit Keys,Roman Dementiev Lutz Kettner Jens Mehnert Peter Sanders MPI fr Informatik, Saarbrcken,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Introduction,The power of integer keys helps in Sorting (radix MSB,LSB) Priority

2、 queues (radix heaps) Static search trees Dictionaries (hash tables) Faster both in theory and practice What about dynamic search data structures?,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Motivation,van Emde Boas (vEB) search trees van Emde Boas77,MehlhornNaeher90

3、: Small K, large n vEB are faster ? NO, their direct implementations are 2-8 times slower than comp. based trees Wenzel92,here Here: a tuned vEB data structure that outperforms comp. based implementations,n number of elements K bit width of keys c size of the output,R. Dementiev et al.: A Sorted Lis

4、t Data Structure for 32 Bit Keys (ALENEX04),Direct vEB Implementation,vEB tree maintains set Recursive definition: |M|=1 or K=1: store directly, otherwise let K = K/2: store minM,maxM, top: store (top recursion) boti: store (bottom recursion) use hash table,K bit vEB top,hash table,K bit vEB boti,R.

5、 Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Improvement 1,Replace top data structure with a bit pattern hierarchy,K bit vEB top,hash table,K bit vEB boti,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Improvement 2,Break recursion when K=8

6、 3 levels max.,hash table,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Improvement 3,Replace root hash table with an array,63,0,0,31,0,31,32,32,63,63,4095,65535,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Range Query Support,Link eleme

7、nts,63,0,0,31,0,31,32,32,63,63,4095,Level 1 root Bits 31-16,Level 2 Bits 15-8,Level 2 Bits 15-8,Level 3 Bits 7-0,65535,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Example: Locate Operation,return handle of Function locate(y:N):ElementHandle if y maxM then return / no

8、 larger element i := y16.31/ index into root table top if topi=null or ymaxMi then return minMtop.locate(i)/ look in the next L2 table if Mi=x then return x/ single element case j := y8.15/ key for L2 table at Mi if rij=null or y maxMij then return minMi,top(i).locate(j)/ look in the next L3 table i

9、f Mij=x then return x/ single element case return rijtopij.locate(y0.7)/ L3 table access At most 9 comparisons for any input sizes,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Locate Performance,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX

10、04),Construction,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Deletion,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Hard Inputs,R. Dementiev et al.: A Sorted List Data Structure for 32 Bit Keys (ALENEX04),Conclusions and Future Work,Integer search trees can outperform comp. based search da