The ever growing need to efficiently store, retrieve and analyze massive datasets, originated by very different sources, is currently made more complex by the different requirements posed by users, devices and applications. Such a new level of complexity cannot be handled properly by current data structures for Big Data problems. To successfully meet these challenges, new surprising results have appeared recently in the literature that integrate classic approaches (such as B-trees) with various kinds of learning models (such as Neural Networks), called Hybrid Data Structures. They achieve improved space-time trade-offs and open new research scenarios. In this talk, I’ll survey the evolution of search data structures, point out new challenges and results, and propose the novel concept of Personalized Data Structures and its corresponding algorithmic framework, called Multicriteria Data Structures. Here, one wishes to seamlessly integrate, via a principled optimization approach, classic or compressed data structures with new, revolutionary, data structures “learned” from the input data by using proper machine-learning tools. The Hybrid Data Structures are just a simple instance of this framework, which we believe deserves much research attention because of its scientific challenges and significant practical impacts.