An Improved Upper Bound for Scalable Distributed Search Trees.
Adriano Di Pasquale, Enrico Nardelli, Guido Proietti · 2002
In this paper we analyze the amortized cost of inserts and exact searches in a DRT*, an order preserving scalable distributed data structure able to manage both mono-dimensional and multi-dimensional data. We show that by adding to the DRT * strategy a correction algorithm after split operations, a sequence of m requests of intermixed exact-searches and insertions over a DRT * starting with one empty server and ending with n servers has a cost of O ¡ m ¢ α ¡ m £ n¤¥ ¤ messages, where α ¡ m £ n ¤ is the classic inverse of the Ackermann function, thus improving the previous O ¡ mlog ¦ 1 § m ¨ n © n ¤ bound.