Must read research papers on Data Structures

Data Structures are not seen to be as important as Algorithms but in reality, it is equally important to solve computational problems efficiently. The must read research papers on Data Structures are:

• Ordered Hash Table (1973)
• Randomized Search Trees (1989)
• EERTREE: An Efficient Data Structure for Processing Palindromes in Strings (2015)
• Making data structures persistent (1986)
• Design and implementation of an efficient priority queue (1976)
• Fractional cascading: A data structuring technique (1986)

Note that the above list has been prepared by OpenGenus and is very accuracy. We will now go through each in detail:

Ordered Hash Table

Basic details on the paper:

• Author: O. Amble and D. E. Knuth
• Affiliation: University of Oslo and Stanford University
• Date published: 1973
• Journal/ Conference: The Computer Journal
• Read this paper here: by Oxford Academia
• Read about Hash Tables

Hash table is a fundamental progress as it shows how a simple data structure like array can be used to improve common operations like searching to constant time. Today, hash map has a central place in algorithms but a lot of ideas goes into it for efficiency like:

• collision avoidance
• hash generation

This is a must read for anyone interested in Computer Science and specially, Algorithms and Data Structures.

Randomized Search Trees

Basic details on the paper:

• Author: Raimund Seidel and Cecilia Aragon
• Affiliation: UC Berkeley
• Date published: November 1989
• Journal/ Conference: 30th Annual Symposium on Foundations of Computer Science
• Read this paper here: Research Gate (PDF)
• Read about Randomized Search Trees

Balanced Search trees are a solution to a number of problems but when it comes to reality, trees keep changing and keeping it balanced is a difficult process. This paper presents how balanced trees can be modified using randomness and opens up a whole new category of algorithms.

For will need to understand Binary Search Tree to get the complete idea of this.

EERTREE: An Efficient Data Structure for Processing Palindromes in Strings

Basic details on the paper:

• Author: Mikhail Rubinchik and Arseny M. Shur
• Affiliation: Ural Federal University, Ekaterinburg, Russia
• Date published: June 2015
• Journal/ Conference: European Journal of Combinatorics
• Read this paper here: ArXiv
• Read about EerTree

This is a must read because this data structure shows that some problems like string related problems may seem to be pruely algorithmic problems but a clever use of a data structure can improve the performance significantly.

This paper bridges the gap between algorithms and data structures with respect to strings.

Making data structures persistent

Basic details on the paper:

• Author: Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E
• Affiliation: Carnegie-Mellon University, IBM, AT&T Bell Laboratories, Princeton University
• Date published: 5th August 1986
• Journal/ Conference: Journal of Computer and System Sciences
• Read this paper here: ACM
• Read about Persistent Segment Tree

Usually, data structures need not remember previous structures but as we went on to solve complex problems in time domain, need of persistent data structures that is data structures maintaining its previous structures rose. This paper is a must read as it shows what it means for a data structure to be persistent and how we can do so.

This opens up the path to a whole new domain of persistent data structures.

Design and implementation of an efficient priority queue

Basic details on the paper:

• Author: P. van Emde Boas, R. KaasE. Zijlstra
• Affiliation: Mathematical Centre, Amsterdam, Netherlands
• Date published: December 1976
• Journal/ Conference: Mathematical systems theory
• Read this paper here: Springer
• Read about Priority Queue

This is an old paper but is a good read as it shows how a data structure should be implemented depending on the system architecture and programming language used to get the most performance out of it.

This will open up your mind to look at algorithms and data structures differently.

Fractional cascading: A data structuring technique

Basic details on the paper:

• Author: Bernard Chazelle, Leonidas J. Guibas
• Affiliation: Brown University, Ecole Normale Supérieure, DEC/SRC and Stanford University, USA
• Date published: November 1986
• Journal/ Conference: Algorithmica
• Read this paper here: Springer

This is an important paper as it shows how particular data structure can perform less for the first few tries and then, show superior performance as it gets warmed up. This is a must read to understand the true potential of data structures.

Learn more about Data Structures

With this, you will have a good understanding of the wide variety of data structures and what can be done using them.