Garbage collecting persistent data structures
Summer 2007
I spent a summer at Harvey Mudd doing a National Science Foundation REU learning about persistent data structures (data structures that maintain a version history of updates) and how they can be effectively garbage collected.
Most garbage collectors work on the principle that only elements of data structures that no longer are pointed to are garbage and that everything else is live and should be kept. In certain persistent data structures, like those in the seminal 1989 paper by Driscoll et al, this overhead is especially wasteful. In order to make asymptotic performance guarantees, pointers pop up between nearly every element of the data structure, guaranteeing that a normal garbage collector will keep the entire data structure until it can be completely discarded.
With a proper interface abstraction, the data structure can ensure that the end user doesn’t have to care about its internal workings and can throw away pointers to versions of the data structure that are no longer interesting. By allowing the data structure to direct its own cleanup, the garbage collector can assure that the theoretical space savings inherent in the structure’s design become actual space savings.
Since the garbage collector itself takes time on the order of the size of the data structure to examine the structure, the holy grail is to develop an algorithm that would take an equivalent amount of time and yet pick up all the logical garbage. We have not completely solved the problem but have, along the way, found many other algorithms that exhibit time/completeness tradeoffs with regards to the amount of garbage found.
Phil Miller and I wrote a draft paper on the subject, Garbage Collecting the Split Node Persistent Data Structure (PDF, 23 pages). Zvi Effron, Phil, and I also gave a presentation (PDF, 120 slides) on this topic and garbage collection in general.
Modeling operator/automation authority
Summer 2006
Over the course of a summer LARSS internship at the NASA Langley Research Center, I investigated how a formally-verified architecture of airplane electronics could be extended to include the pilot in its fault-tolerant specification. So, if the pilot becomes unconscious or is otherwise incapacitated, the autopilot could automatically take over. The problem is much too broad to be solved in a single summer with only a few researchers, so research continued in the formal methods group at NASA Langley. Following are my tech report (PDF; figures available upon request) and poster (PowerPoint) regarding our initial work.
Cognitive and ecological techniques compared for weapons of mass destruction scenarios
Summer/Fall 2005
Over the summer and fall of 2005 in Vanderbilt’s Human-Machine Teaming Laboratory, I worked on learning enough about robotics and human factors to do a human factors study on identifying potential target areas for robotic application from a high-level perspective. Work since progressed to developing human-robotics interfaces based on these techniques. Following are my tech report (PDF; figures available upon request) and poster (PowerPoint) regarding the starting efforts.
Flying Tiger Development, La Habra, CA
Summers 2003 and 2004
I designed, tested, and implemented many games for lots of different cell phones in J2ME and BREW. I took several games designed for Japanese cell phones and got them working within the relatively limited constraints of American phones. The most significant title I worked on was the Java port of the Pirates of the Caribbean cell phone game, as the sole developer for a while. Some pictures of the other various titles I worked on:
