HighlyEfficient Data Structures
Source of Funding:
UKIndia 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
floatingpoint 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
 R. F. Geary, R. Raman and V. Raman.
Succinct tree representations for XML documents.
To appear in
Proc. ACMSIAM Symposium on Discrete Algorithms (SODA04).
 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 345356, 2003.
 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 357368, 2003.
 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.
 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.
