Superseding traditional indexes with multicriteria data structures

Abstract

The ever-growing amount of information coming from the Web, social networks and IoT severely impairs the management of data. Much research has been devoted to dealing with this issue, however, we still miss proper algorithmic solutions that work under computational constraints that vary across users, devices and time. We therefore propose the concept of Multicriteria Data Structures, which add to the classic requirement of being efficient, the novel feature of dynamically adapting themselves to the constraints imposed by the application of use. We show the potentiality of this concept by focusing on the paradigmatic dictionary problem. After reviewing some old and new solutions to this problem, we present the first multicriteria data structure, the PGM-index, that solves it with better (both asymptotically and experimentally) time and space than classic indexes for hierarchical memories, such as B-trees, and modern learned indexes. Finally, we show an optimisation algorithm that finds the best design setting of a PGM-index according to the input constraints (either in time or in space).