Sun 23 Jun 2019 10:40 - 11:00 at 106C - Novel Data Applications

Functional (aka immutable) data structures are used extensively in data management systems.
From distributed systems to data persistence, immutability makes complex programs significantly easier to reason about and implement.
However, immutability also makes many runtime optimizations like tree rebalancing, or adaptive organizations, unreasonably expensive. In this paper, we propose semi-functional data structures, an approach to data structure design that allows limited physical changes that preserve logical equivalence. As we will show, this approach retains many of the desirable properties of functional data structures, while also allowing runtime adaptation. To illustrate semi-functional data structures, we work through the design of a lazy-loading map that we call a Fluid COG Fluid COG is a lock-free data structure that incrementally organizes itself in the background by applying equivalence-preserving structural transformations. Our experimental analysis shows that the resulting map structure is flexible enough to adapt to a variety of performance goals, while remaining competitive with existing structures like the C++ standard template library map.

Sun 23 Jun

dbpl-2019-papers
10:20 - 11:00: DBPL 2019 - Novel Data Applications at 106C
dbpl-2019-papers10:20 - 10:40
Talk
Nobutaka SuzukiUniversity of Tsukuba, Takuya OkadaUniversity of Tsukuba, Yeondae KwonThe University of Tokyo
dbpl-2019-papers10:40 - 11:00
Talk
Darshana BalakrishnanUniversity at Buffalo, Lukasz ZiarekSUNY Buffalo, USA, Oliver KennedyUniversity at Buffalo