Computational Models for Algorithm and Data Structure Design in Systems

Abstract

Computational models are powerful tools that can be applied in a number of ways. We present three examples of how they can be applied in the context of algorithms and data structure design for systems, both as components within a design and as tools for navigating design tradeoffs. We start with an example of the former, where we demonstrate how best to utilize a machine learning model to improve the false-positive rate of the classic Bloom Filter. We then demonstrate how a computational model can be used to navigate the design space of prefix-based range filters and how such a model can be used for automated online optimization. Finally, we examine the history of computational models used for evaluating storage algorithms and demonstrate how tailoring these models to the critical aspects of modern storage hardware can provide valuable new insights.