University of Leicester

informatics

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 floating-point 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, word-level parallelism (WLP) and self-adjusting 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 NP-complete network optimisation problems.

Publications

  1. M. Bender, R. Cole and R. Raman. Exponential trees for efficient cache-oblivious algorithms. In Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), Springer LNCS 2380, 195-207, 2002.
  2. T. Hagerup and R. Raman. An efficient quasidictionary. In Proc. 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002). Springer LNCS 2368, 1-18, 2002.
    • This paper is the subject of an invited talk by Torben Hagerup.
  3. R. Raman, V. Raman and S. S. Rao. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233-242, 2002.
    • Submitted to a special issue of J. Algorithms, D. Eppstein, ed., devoted to selected papers from SODA 2002.
  4. 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), Springer-Verlag LNCS series 2141, 2001, pp 67-78.
  5. 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, 426-437.
  6. 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.
  7. 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.
  8. M. Crochemore, C. S. Iliopoulos, Y. J. Pinzon. Speeding-up Hirschberg and Hunt-Szymanski LCS Algorithms. Proc. of the 8th International Symposium on String Processing and Information Retrieval (SPIRE'01), IEEE Computer Society Press, pp. 59-67, 2001.
  9. C. S. Iliopoulos, L. Mouchard, Y. J. Pinzon. The Max-Shift Algorithm for Approximate String Matching. Proc. 5th Workshop on Algorithm Engineering (WAE'01), Springer-Verlag LNCS v.2141, pp. 13-25, 2001.
  10. 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.
  11. N. Rahman and R. Raman. Analysing the cache behaviour of non-uniform distribution sorting algorithms. In Proc. 8th Annual European Symposium on Algorithms (ESA '00), Springer-Verlag LNCS v. 1879 (M. S. Paterson ed.), pp. 380--391, 2000.
  12. N. Rahman and R. Raman. Adapting radix sort to the memory hierarchy. In Proc. 2nd Workshop on Algorithm Engineering and Experiments (ALENEX 2000), 2000.
  13. M. Korda and R. Raman. An experimental evaluation of hybrid data structures for predecessor searching. In Proc. 3rd Workshop on Algorithm Engineering, Springer-Verlag LNCS series 1668, pp. 214-228, 1999.
  14. N. Rahman and R. Raman. An analysis of cache effects in distribution sorting algorithms. In Proc. 3rd Workshop on Algorithm Engineering, Springer-Verlag LNCS series LNCS 1668, pp.184-198, 1999.
  15. T. Radzik. Implementation of Dynamic Trees with In-Subtree Operations. ACM J. Experimental Algorithmics, 3 (1998), Article 9.
  16. N. Rahman and R. Raman. An experimental evaluation of word-level parallelism in sorting algorithm s. In 2nd Workshop on Algorithm Engineering, WAE '98-Proceedings, K. Mehlhorn, ed., TR MPI-I-98-1-019, Max Planck Institute for Computer Sc ience, ISSN 0946-011X, 1998, pp. 193-203.
  17. R. Raman. Algorithms beyond compare: exploiting word-level parallelism . In Combinatorial algorithms-9th Australasian Workshop on Combinatorial Algorithms (AWOCA '98), C. S. Iliopoulos ed., 1998, pp. 13-15. (Abstract of invited talk.)

Final Report

You can find the grant's final report here.

Author: Rajeev Raman (r.raman at mcs.le.ac.uk), T: +44 (0)116 252 3894.
University of Leicester 15th December 2000. Last modified: 6th August 2003, 13:03:44.
Informatics Web Maintainer. This document has been approved by the Head of Department.