Oregon State University

Can’t find an event? We’re busy migrating to a new event calendar. Try looking at the new calendar



Event Details

MS Final Examination – Meng Meng

Friday, September 22, 2017 10:00 AM - 12:00 PM

Implementation Techniques for Variational Data Structures
Many applications require not only representing variability in software and data, but also computing with it. To do so efficiently requires variational data structures that make variability explicit in the underlying data and the operations used to manipulate it.

Variational data structures have been developed ad hoc for many applications, but there is little general understanding of how to design them or what tradeoffs exist among them.

In this thesis, we introduce the concept of holes to represent variational data structures of different sizes and shapes. Moreover, we strive for a more systematic exploration and analysis of a variational data structure. We want to know how different design decisions affect the performance and scalability of a variational data structure, and what properties of the underlying data and operation sequences need to be considered.

Specifically, we study several alternative designs of a variational stack and analyze how these design decisions affect the performance of a variational stack with different usage profiles. We evaluate variational stacks in a real-world scenario: in the interpreter VarexJ when executing real software containing variability. Finally, we discuss different ways of representing variational priority queues and show how this affects the performance of the variational Dijkstra’s algorithm.

Major Advisor: Eric Walkingshaw
Committee: Martin Erwig
Committee: Amir Nayyeri
GCR: Kyle Niemeyer

Kelley Engineering Center (campus map)
Calvin Hughes
1 541 737 3168
Calvin.Hughes at oregonstate.edu
Sch Elect Engr/Comp Sci
This event appears on the following calendars: