ICS Theory Group

ICS 269, Winter 2004: Theory Seminar

30 Jan 2004:
Split flows and elusive outliers: solving two problems in modern computing
Amic Chaudhary, UCI

The world of computing is witnessing simultaneous explosions in data and connectivity. We need computer systems that meet the challenges of this evolving world while exploiting the benefits inherent in it. In this talk we shall look at two case studies of constructing algorithms for such systems.

A simple technique harnesses the large connectivity of modern networks to provide not only fault tolerance, but also information security --- insisting that all flow (or, communication) is split through edge disjoint paths. The question is: How does the amount of possible flow change under the splitting constraint? Or, more particularly, can we solve, in this scenario, the admission control type, or route (path) coloring type, or any other type of problems that have been studied for regular flows? In the first case study, we shall present results and algorithms that answer some of these questions.

In the second case study, we shall present an implementation for very fast detection of outliers from large data sets in high dimensional space. Detecting outliers is important in catching network intrusions and other fraud, in detecting bio-terrorist attacks, and, in our particular application, finding unique objects in astronomical databases. We shall show that a simple twist to the ubiquitous k-d tree leads to a method that makes no assumption about an underlying probability model, but when compared to state-of-the-art implementations of data mining algorithms that do make such assumptions, performs just as well.