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

Displayed time zone: Tijuana, Baja California change

10:20 - 11:00
Novel Data ApplicationsDBPL at 106C
Detecting Unsatisfiable CSS Rules in the Presence of DTDs
Nobutaka Suzuki University of Tsukuba, Takuya Okada University of Tsukuba, Yeondae Kwon The University of Tokyo
Fluid Data Structures
Darshana Balakrishnan University at Buffalo, Lukasz Ziarek SUNY Buffalo, USA, Oliver Kennedy University at Buffalo