2 Related Works

2.1 Methods of Representing Trees

Index lookup on Person.id Index lookup on Company.Name

Person Index lookup on CompanyId Company

I321Nd JBoLrsaiharNurnaya..mG.BPeoaloegtezh OGNroa..ao..m..glleee

The ode of a tree root is the root identier .

Let us introdu e the operation of getting the following prime number from a set pf primes I:

Let us all a produ t of the node parent identiers by the node Id the node ode.

1. where is parent node, is data added to the tree add(T, d, nparent), nparent d

The following tree operations are admissible:

Pre ondition:

to the tree. parents(T, k) := { x ∈ T | mod(k, key(x)) = 0 ∧ k 6= key(x)} parent(T, k) := M AX(parents(T, k)) where is an operation of node ode re al ulation: recalcKey(T , k, kold, knew) T := T ∪ { x ∈ subtree(T , key(nold))| | n(recalcKey(T , key(x), key(nold), key(nnew)), data(x))} k recalcKey(T , k, kold, knew) := ∗ knew kold 7.3 Hardware Restri tions 7 Future Improvements 7.4 Key Compression

7.2 Multiple GPU Computing Support

7.1 Threaded Exe ution

References

[PSHL10℄ Hagen Peters, Ole S hulz- Hildebrandt , and Norbert Luttenberger . Fast in-pla e sorting with uda

2010 .

based on bitoni sort bitoni sort . In Parallel Pro essing and Applied Mathemati s , pages 403410 .