Research


Areas of interest

Research Theme

I am working in the areas of mobile and adaptive systems. In particular my work has focused on supporting collaborative database applications in the mobile environment through novel prefetching and concurrency management techniques.

The mobile environement is very different from the traditional distributed environment where communication failures are often seen as a fault. Systems for mobile computers must address this issue. I have devloped a prefetching technique for object oriented programs and databases that allow accurate prefetching and continued operation in the presence of communication failures.

In addition, collaborative applications often require high levels of concurrency. I am investigating epidemic communication, concurrency methods and schedulers, event based programming, and reconciliation techniques. For more information please refer to Mokan project.

I am further interested in and have developed reflective/adaptive libraries. These libraries explore the boundary between the programmer's intent and the library's implementation through the use of dynamic properties. In these systems/libraries the the user specifies what is needed and the system is allowed to choose how accomplish the task.

This research has been done with the collaboration of my advisor Ambuj Singh.


Publications

Kristian Kvilekval and Ambuj K. Singh SPREE: Object Prefetching for Mobile Computers [ps] Distributed Objects and Applications, Cyprus, Oct 2004
Abstract
Mobile platforms combined with large databases promise new opportunities for mobile applications. However, mobile computing devices may experience frequent communication loss while in the field. In order to support database applications, mobile platforms are required to cache portions of the available data which can speed access over slow communication channels and mitigate communication disruptions. We present a new prefetching technique for databases in mobile environments based on program analysis. SPREE generates maps of a client program's use of structured data to be used by our prefetching runtime system. We apply SPREE in the context of mobile programming for object structured databases demonstrating an effective way to prefetch/hoard over unreliable networks with speedups up to 80% over other techniques.
Roman Vitenberg, Kristian Kvilekval and Ambuj K. Singh Increasing Concurrency in Databases using Program Analysis [ps] [ppt] European Conference on Object-Oriented Programming (ECOOP), Oslo, Norway, June 2004
Abstract
Programmers have come to expect better integration between databases and the programming languages they use. While this trend continues unabated, database concurrency scheduling has remained blind to the programs. We propose that the database client programs provide a large untapped information resource for increasing database throughput. Given this increase in expressive power between programmers and databases, we investigate how program analysis can increase database concurrency. In this paper, we demonstrate a predictive locking scheduler for object databases. In particular we examine the possibility to predict the client's use of locks. Given accurate predictions, we can increase concurrency through early lock release, perform deadlock detection and prevention, and determine whether locks should be granted before or during a transaction.
Mathias Kolsch, Kristian Kvilekval, Kevin Almeroth Improving Speaker Training with Interactive Lectures ED MEDIA Conference ,Honolulu, Hawaii, June 2003
Abstract
Feedback has always been a cornerstone of the learning process. Advances in mobile devices and wireless connectivity promise closer and better feedback between speakers and audiences. In this paper we discuss a system allowing both real-time and reflective feedback for speakers. By means of online video annotations the audience can augment a lecture with personal notes and give the speaker valuable feedback both instantaneously and retrospectively. The strengths and weaknesses of the system based on lecture hall experiments are presented and discussed.

Kristian Kvilekval, Ambuj Singh Prefetching for mobile computers using shape graphs [pdf] [ppt] Languages, Compilers, and Run-time Systems for Scalable Computers(LCR),Washington DC, March 2002
Abstract
We introduce a prefetching technique that is able to accurately prefetch complex pointer-based data structures. Compile time shape analysis is used to determine the set of possible future objects accessed by a program. We use the reachability graph generated during the shape analysis to create prefetching schedules for selected program points. The program is annotated to visit the reachability graph with the set of accessible objects at any program point, generating a superset of future object references. The technique is applicable to both static and dynamically created object structures. We demonstrate this technique in the context of mobile computing and show a speedup for a variety of Java benchmarks in the presence of disconnections.

Projects

Mokan
A system for distributed programming on mobile platforms
Adaptive Graph Library
AGL is a graph library toolkit for implementing graph algorithms.

Software

Software I have developed recently is located here

Reading

Current Reading
up level
Kristian G. Kvilekval
Last modified: Thu Oct 7 17:52:01 PDT 2004