Helger Lipmaa's publications

On Optimal Hash Tree Traversal for Interval Time-Stamping

Helger Lipmaa. On Optimal Hash Tree Traversal for Interval Time-Stamping. In Agnes Chan and Virgil Gligor, editors, Information Security Conference 2002, volume 2433 of Lecture Notes in Computer Science, pages 357--371, São Paulo, Brazil, September 30 --- October 2, 2002. Springer-Verlag.

File: [.ps.bz2 (64 KB), .pdf (160 KB)] ps recommended.


Skewed trees constitute a two-parameter family of recursively constructed trees. Recently, Willemson proved that suitably picked skewed trees are space-optimal for interval time-stamping. At the same time, Willemson proposed a practical but suboptimal algorithm for nonrecursive traversal of skewed trees. We describe an alternative, extremely efficient traversal algorithm for skewed trees. The new algorithm is surprisingly simple and arguably close to optimal in every imaginable sense. We provide a detailed analysis of the average-case storage (and communication) complexity of our algorithm, by using the Laplace's method for estimating the asymptotic behavior of integrals. Since the skewed trees can be seen as a natural generalization of Fibonacci trees, our results might also be interesting in other fields of computer science..

Keywords: Analysis of algorithms, implementation complexity, interval time-stamping, Laplace's method for integrals, tree traversal.


More information: CiteSeer.


Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.