New Paradigms in Data Structures
Source of Funding: Engineering and Physical Sciences
Research Council (EPSRC)
Reference: GR L/92150
Amount: £152,104
Duration: September 1998  August 2001
Principal Investigator: Prof. Rajeev
Raman
Other Investigator: Dr. Tomasz Radzik (King's College London)
Research Assistants:
The project considers data structuring problems which involve maintaining dynamically changing data, such as sets of integer or floatingpoint keys
and networks (graphs). The data structuring problems to be considered include searching, priority queue operations and dynamic tree operations. We
aim to obtain significant practical and theoretical efficiency gains for these problems by using two new paradigms: namely, wordlevel parallelism
(WLP) and selfadjusting data structures (SADS). To demonstrate the practical efficiency gains of data structures based on WLP and SADS, we will
use them in a number of network algorithms, including shortest paths, network flows and local search methods (simulated annealing, genetic
algorithms) for NPcomplete network optimisation problems.
Publications
 M. Bender, R. Cole and R. Raman.
Exponential trees for efficient cacheoblivious algorithms.
In Proceedings of 29th International Colloquium on Automata,
Languages and Programming (ICALP 2002),
Springer LNCS 2380, 195207, 2002.
 T. Hagerup and R. Raman.
An efficient quasidictionary.
In Proc. 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002).
Springer LNCS 2368, 118, 2002.
 This paper is the subject of an invited talk by Torben Hagerup.
 R. Raman, V. Raman and S. S. Rao.
Succinct indexable dictionaries with applications to encoding
kary trees and multisets.
In Proc. 13th ACMSIAM Symposium on Discrete Algorithms (SODA),
pp. 233242, 2002.

Submitted to a special issue of
J. Algorithms,
D. Eppstein, ed., devoted to selected papers from SODA 2002.
 N. Rahman, R. Cole and R. Raman.
Optimised Predecessor Data Structures for Internal Memory.
In Proceedings of the 5th International Workshop on Algorithm Engineering (WAE 2001), SpringerVerlag LNCS series 2141, 2001, pp 6778.
 R. Raman, V. Raman and S. S. Rao.
Succinct dynamic data structures.
Proceedings 7th International Workshop on Algorithms and
Data Structures (WADS 2001), Springer LNCS 2125, 426437.
 D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman and S. S. Rao.
Representing trees of higher degree.
University of Leicester Technical Report 2001/46, 2001. Submitted
for publication.
 N. Rahman and R. Raman.
Adapting radix sort to the memory hierarchy.
ACM J. Experimental Algorithmics,
6 (2001), Article 7.

Special issue
devoted to selected papers from ALENEX 2000,
A. V. Goldberg and B. M. E. Moret, eds.
 M. Crochemore, C. S. Iliopoulos, Y. J. Pinzon.
Speedingup Hirschberg and HuntSzymanski LCS Algorithms.
Proc. of the 8th International Symposium on String Processing and Information Retrieval (SPIRE'01), IEEE Computer Society Press, pp. 5967, 2001.
 C. S. Iliopoulos, L. Mouchard, Y. J. Pinzon.
The MaxShift Algorithm for Approximate String Matching.
Proc. 5th Workshop on Algorithm Engineering (WAE'01),
SpringerVerlag LNCS v.2141, pp. 1325, 2001.
 N. Rahman and R. Raman.
An analysis of cache effects in distribution sorting algorithms.
ACM J. Experimental Algorithmics,
5 (2000), Article 15.
 Special issue devoted to selected papers from
WAE '99, J. S. Vitter and C. D. Zaroliagis, eds.
 N. Rahman and R. Raman.
Analysing the cache behaviour of nonuniform distribution sorting algorithms.
In Proc. 8th Annual European Symposium on Algorithms (ESA '00),
SpringerVerlag LNCS v. 1879 (M. S. Paterson ed.), pp. 380391, 2000.
 N. Rahman and R. Raman.
Adapting radix sort to the memory hierarchy.
In Proc. 2nd Workshop on Algorithm Engineering and Experiments (ALENEX 2000),
2000.
 M. Korda and R. Raman.
An experimental evaluation of hybrid data structures for
predecessor searching.
In Proc. 3rd Workshop on Algorithm Engineering,
SpringerVerlag LNCS series 1668, pp. 214228, 1999.
 N. Rahman and R. Raman.
An analysis of cache effects in distribution sorting algorithms.
In Proc. 3rd Workshop on Algorithm Engineering,
SpringerVerlag LNCS series LNCS 1668, pp.184198, 1999.
 T. Radzik. Implementation of Dynamic Trees with InSubtree Operations.
ACM J. Experimental Algorithmics,
3 (1998), Article 9.
 N. Rahman and R. Raman.
An experimental evaluation of wordlevel parallelism in sorting algorithm
s.
In 2nd Workshop on Algorithm Engineering, WAE '98Proceedings,
K. Mehlhorn, ed., TR MPII981019, Max Planck Institute for Computer Sc
ience,
ISSN 0946011X, 1998, pp. 193203.
 R. Raman. Algorithms beyond compare: exploiting wordlevel parallelism
.
In Combinatorial algorithms9th Australasian Workshop on Combinatorial
Algorithms (AWOCA '98),
C. S. Iliopoulos ed., 1998, pp. 1315. (Abstract of invited talk.)
Final Report
You can find the grant's final report
here.
