"
The Research Challenge.
The long-term challenge is whether we can easily or even automatically find the optimal storage design for a given problem. This has been recognized as an open problem since the early days of computer science. In his seminal 1978 paper, Robert Tarjan includes this problem in his list of the five major challenges for the future (which also included P Vs NP) [85]: “Is there a calculus of data structures by which one can choose the appropriate data representation and techniques for a given problem?”. We propose that a significant step toward a solution includes dealing with the following two challenges:
1) Can we know all possible data structure designs?
2) Can we compute the performance of any design?"