Spring 1997
April 14, 1997
The increasing ability to interconnect computers through internetworking, wireless networks, high-bandwidth satellite, and cable networks has spawned a new class of information-centered applications based on “data dissemination.” These applications employ broadcast to deliver data to very large client populations. In data dissemination, the data transfer is initiated by the server, inverting the traditional relationship between the client and the server. We have proposed a novel “multi-disk” framework for data dissemination called “Broadcast Disks.” The Broadcast Disks approach significantly improves upon the previous work in dissemination-based systems and raises a number of fundamentally new research challenges.
In the talk, we will first motivate why the rise of “symmetric” networks (i.e., networks which have a significantly higher bandwidth available from servers to clients than in the reverse direction) and the scale of the emerging distributed information systems is causing a shift from the traditional pull-based client-server model to a push-based dissemination model. We will then highlight the specific contributions of the Broadcast Disks paradigm including a framework for designing the algorithms for prefetching and dissemination of updates. Finally, we describe our experience in building a Broadcast Disks prototype and discuss some of the open issues in design of dissemination-based information systems.
(Joint work with M. Franklin and S. Zdonik)
May 8, 1997
Curve approximation problems appear in many application areas, such as image processing, computer graphics, cartography, and data compression. In this talk, we present several geometric techniques and observations for solving polygonal curve approximation problems. Given an $$n$$-vertex polygonal curve $$P = [p_1, p_2, \ldots, p_n]$$ in space $$R^d$$ ($$d = 3$$ or $$d = 2$$), we consider the problem of approximating $$P$$ by finding another polygonal curve $$P’ = [p’_1, p’_2, \ldots, p’_m]$$ of $$m$$ vertices in $$R^d$$ such that the vertex sequence of $$P’$$ is an ordered subsequence of the vertices along $$P$$. The goal is to either minimize the size $$m$$ of $$P’$$ for a given error tolerance $$\epsilon$$, or minimize the deviation error $$\epsilon$$ between $$P$$ and $$P’$$ for a given size $$m$$ of $$P’$$. We develop a number of efficient algorithms for solving 3-D and 2-D polygonal curve approximation problems under two commonly-used error criteria. Our algorithms improve substantially the time and/or space bounds of the previously best known results on the same problems.