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:

  • Maureen Korda.
  • Yoan Jose Pinzon.
  • Naila Rahman.
  • S Srinivasa Rao.

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

  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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. 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.
  • 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.
  • 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 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.
  • 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, Springer-Verlag LNCS series 1668, pp. 214-228, 1999.
  • 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.
  • T. Radzik. Implementation of Dynamic Trees with In-Subtree Operations. ACM J. Experimental Algorithmics, 3 (1998), Article 9.
  • 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.
  • 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.

Final Report

You can find the grant's final report here.

Share this page:

Contact Us

Admissions Enquiries:
BSc: +44 (0) 116 252 5280
MSc: +44 (0) 116 252 2265
E: BSc  seadmissions@le.ac.uk
E: MSc  pgadmissions@le.ac.uk

Departmental Enquiries:
T: +44 (0) 116 252 2129/3887
F: +44 (0) 116 252 3604
E: csadmin@mcs.le.ac.uk

Dept of Informatics
University of Leicester
Leicester, LE1 7RH
United Kingdom

Accessibility

DisabledGo logo

The University of Leicester is committed to equal access to our facilities. DisabledGo has a detailed accessibility guide for the Informatics Building.