computer science

Highly-Efficient Data Structures

Source of Funding: UK-India Science and Technology Research Fund.
Reference: UISTRF IT/2001.04
Amount: £6,800
Duration: April 2001 - August 2003
Principal Investigator (UK): Prof. Rajeev Raman
Principal Investigator (India): Dr. Venkatesh Raman (Institute for Mathematical Sciences, Chennai, India)

The recent explosion in large data sets has given rise to many new issues in the area of data structures. In this field one studies optimal ways of representing and manipulating data so that operations like search and update are performed efficiently.

In this project, we will consider data structuring problems which involve maintaining dynamically changing data, such as sets of integer or floating-point keys. The data structuring problems to be considered are fundamental ones including searching and priority queue operations. We aim to make advances both in theoretical and practical efficiency for these data structuring problems, focussing on the following aspects (there is some overlap among these aspects):

• Adapting data structures to the memory system.
• Making data structures succinct.

Publications

1. R. F. Geary, R. Raman and V. Raman. Succinct tree representations for XML documents. To appear in Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA04).
2. R. Raman and S. Srinivasa Rao. Succinct dynamic dictionaries and trees. In Proceedings of the 30th International Colloquium on Automata; Languages and Computation (ICALP 2003), LNCS 2719, pp 345-356, 2003.
3. J. I. Munro, R. Raman, V. Raman and S. Srinivasa Rao. Succinct representations of permutations. In Proceedings of the 30th International Colloquium on Automata; Languages and Computation (ICALP 2003), LNCS 2719, pp 357-368, 2003.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.

Author: Rajeev Raman (r.raman at mcs.le.ac.uk), T: +44 (0)116 252 3894.
© University of Leicester December 2001. Last modified: 11th October 2003, 20:05:54.
CS Web Maintainer. This document has been approved by the Head of Department.