Date: 28 Feb 2006
From: jyrki@diku.dk
Subject: PE-lab: Annual Report 2005

Performance Engineering Laboratory (PE-lab)
http://www.diku.dk/~jyrki/PE-lab/

* Annual Report 2005

In 2005, the focus in the research done at the PE-lab was on efficient
data structures. Both the theoretical and experimental efficiency of
priority queues and hash tables was studied.  For the research done,
the following people were active contributors:

Christopher Derek Curry (Industrial partner, Netcompany A/S)
Amr Elmasry (External collaborator, Alexandria University)
Claus Jensen (M.Sc. student)
Jyrki Katajainen (Lab leader)
Jørgen Havsberg Seland (M.Sc. student)
Anders Thøgersen (B.Sc. student)
Fabio Vitale (External M.Sc. student, University of Insubria).

Other members of the PE-lab were:

Andrei Bjarke Moskvitin Josephsen (M.Sc. student)
Stephan Lynge Herlev Larsen (M.Sc. student)
Jacob De Fine Skibsted (M.Sc. student)

Research articles done under the auspices of the PE-lab are available
via the CPH STL report series, see http://cphstl.dk.

A more detailed description of the projects completed or started in
2005 is given below.


* Priority queues [Amr, Claus, and Jyrki]

The goal in this research was to develop efficient priority queues
that support operations find-min(), insert(), decrease(), and
delete(). That is, this work was done with the aim of finding
alternatives to Fibonacci heaps and Run-relaxed heaps. Our focus was
on simplicity as well as on the worst-case comparison complexity of
delete() under the assumption that the other three operations have the
worst-case cost of O(1). Currently, the best bound achieved by us is
lg n + O(lg lg n) element comparisons. Three different data structures
guaranteeing this performance were developed: multipartite relaxed
binomial queue, two-tier pruned binomial queue, and relaxed weak
queue. These were the first data structures which achieve the bound
lg n + o(lg n) for the number of element comparisons performed by
delete().  Of the three data structures, the last is the most space
efficient requiring 3n + O(lg n) words of storage, in addition to the
n elements stored.

Research output: 3 articles


* Double-ended priority queues [Amr, Claus, and Jyrki]

In this study the comparison complexity of double-ended priority-queue
operations was investigated. In addition to the normal priority-queue
operations, a double-ended priority queue supports both find-min() and
find-max(). Two general data-structural transformations were described
which transform our efficient priority queues into double-ended
priority queues. The resulting double-ended priority queues are the
fastest among all known double-ended priority queues. Due to their
generality, the data-structural transformations applied are of
independent interest.

Research output: 1 article


* Experimental analysis of priority queues [Claus, Fabio, and Jyrki]

The practical efficiency of various priority-queue structures was
studied. The data structures considered include a navigation pile and
a local heap which both had been devised by the members of the
PE-lab. Several novel aspects about the representation of priority
queues were considered:

1) How to make priority queues fully dynamic?
2) How to provide referential integrity?
3) How to improve the cache behaviour?
4) What is the relevance of pointer-based data structures?
5) What is the relevance of the compaction of data structures?

Previously, these implementation issues had been studied sparsely, so
our analyses provide a considerable increase in knowledge in this area.

Research output: 2 papers


* Experimental analysis of hash tables [Jørgen and Anders]

The CPH STL is a high-performance C++ Standard Template Library
implementation. In this project, we designed a modular framework for
standards-compliant hash tables targeted for inclusion in the CPH
STL. Within this framework, hash tables based on three different
approaches, two of which were inspired by Per Åke Larson's "dynamic
hashing", were implemented. The implementations were compared to
existing hash-table implementations in exhaustive synthetic
benchmarks. The conclusion was that none of the approaches were
universally ideal, but that all had strong points, which made a case
for our modular hash-table design. A few common hash-table
optimizations were analysed, among them storing the results of
hash-function computations, which greatly improved the cache
performance of the tables, and the asymptotic running time when
variable-length keys were used.

Research output: 2 articles


* Organizational design [Christopher and Jyrki]

A preliminary version of the book "Reengineering a university
department", which was internally distributed within our organization,
was released in 2003. Now we revised the manuscript and submitted it
to a publisher. Timely updates about the publication process will be
available via the book's home page at http://www.diku.dk/~jyrki/bpr/.

Research output: 1 book