We describe a computational architecture of a collision early-warning system for vehicles and other principals. Early-warnings allow drivers to make good judgments and to avoid emergency stopping or dangerous maneuvering. With many principals (vehicles, pedestrians, bicyclists, etc.) coexisting in a dense intersection, it is difficult to predict, even a few seconds in advance, since there are many possible scenarios. It is a major challenge to manage computational resources and human attention resources so that only the more plausible collisions are tracked, and of those, only the most critical collisions prompt warnings to drivers. In this paper, we propose a two-stage collision risk assessment process, including the following: 1) a preliminary assessment via simple efficient geometric computations, which thoroughly considers surrounding principals and identifies likely potential accidents, and 2) a specialized assessment that computes more accurate collision probabilities via sophisticated statistical inference. The whole process delivers an expected utility assessment to available user interfaces (UIs), allowing the UIs to make discriminating choices of when to warn drivers or other principals.

We consider the problem of information dissemination in wireless ad-hoc networks. Capacity constraints and the varying needs of applications lead to the need for delivering data at varying resolutions as a function of distance. We introduce a primitive, which we call visibility, to quantify the variable-resolution requirement. We design and analyze new variable resolution multicast algorithms based on simple probabilistic schemes to achieve a required visibility. We also examine how multi-path effects influence visibility and propagation algorithms. Finally, we consider the problem of designing the visibility function to maximize an overall utility function (specified by applications) over the network. We derive a condition relating optimal utility and visibility, which can be used to derive the optimal visibility for a class of utility functions. 1

The memory required to store the context model for a PPM-style compressor increases exponentially with the order of the model (i.e., length of context). It is a challenging research problem to find ways to reduce the memory requirement of a large context model without sacrificing its coding efficiency. In this paper, we focus on bi-level image coding and investigate context reduction by clustering: that is, contexts predicting similar probability distributions are grouped together to share a common entropy coder. We give an O(kn) algorithm for optimally grouping n contexts into k clusters so that the total loss in coding efficiency is minimized. Previously no algorithm was known for solving this problem. We demonstrate the effectiveness of clustering by implementing a two-level compression scheme. Experimental results on the CCITT test images show that, using the same amount of memory, our scheme achieves better compression than the two-level PPM method of A. Moffat (1991).

We describe a technique for building hash indices for a large dictionary of strings. This technique permits robust retrieval of strings from the dictionary even when the query pattern has a significant number of errors. This technique is closely related to the classical Turan problem for hypergraphs. We propose a general method of multi-index construction by generalizing certain Turan hypergraphs. We also develop an accompanying theory for analyzing such hashing schemes. The resulting algorithms have been implemented and can be applied to a wide variety of recognition and retrieval problems.>

A single physical computer memory may be used for more than one type of page, with the amount of memory devoted to each type under software control.For example, the effective size of memory can be increased by storing some pages in compressed form and decompressing on demand.This introduces another level to the memory hierarchy, and the sizes of two adjacent levels may be varied dynamically.We present an algorithm for varying the mixture of pages in a two-type cache, and then analyze the "competitiveness" of our algorithm.We also report progress in partially automating the design and analysis of on-line algorithms.

Motivated by applications in data compression, debugging, and physical simulation, we consider the problem of adaptively choosing locations in a long computation at which to save intermediate results.Such checkpoints allow faster recomputation of arbitrary requested points within the computation.We abstract the problem to a server problem in which k servers move along a line in a single direction, modeling the fact that most computations are not reversible.Since checkpoints may be arbitrarily copied, we allow a server to jump to any location currently occupied by another server.We present online algorithms and analyze their competitiveness.We give lower bounds on the competitiveness of any online algorithm and show that our algorithms achieve these bounds within relatively small factors.

In a clustering problem, the aim is to partition a given set of n points in d-dimensional space into k groups, called clusters, so that points within each cluster are near each other. Two objective functions frequently used to measure the performance of a clustering algorithm are, for any L4 metric, (a) the maximum distance between pairs of points in the same cluster, and (b) the maximum distance between points in each cluster and a chosen cluster center; we refer to either measure as the cluster size.

Whru a dilt~lhSC is replicated at, many sites2 maintaining mutual consistrnry among t,he sites iu the fac:e of updat,es is a signitirant problem.This paper descrikrs several randomized algorit,hms for dist,rihut.ingupdates and driving t,he replicas toward consist,c>nc,y.The algorit Inns are very simple and require few guarant,ees from the underlying conllllunicat.iollsystem, yc+ they rnsutc t.hat.the off(~c~t, of ('very update is evcnt,uwlly rf+irt-ted in a11 rq1ica.s.The cost, and parformancc of t,hr algorithms arc tuned I>? c%oosing appropriat,c dist,rilMions in t,hc randoinizat,ioii step.TIN> idgoritlmls ilr(' c*los~*ly analogoIls t,o epidemics, and t,he epi-dcWliolog)-litc\ratiirc, ilitlh iii Illld~~rsti4lldill~ tlicir bc*liavior.One of tlW i$,oritlims 11&S brc>n implrmcWrd in the Clraringhousr sprv(brs of thr Xerox C'orporat~c~ Iiitcrnc4, solviiig long-standing prol>lf~lns of high traffic and tlatirl>ilsr inconsistcllcp.

Geometric algorithms are usually designed with continuous parameters in mind. When the underlying geometric space is intrinsically discrete, as is the case for computer graphics problems, such algorithms are apt to give invalid solutions if properties of a finite-resolution space are not taken into account. In this paper we discuss an approach for transforming geometric concepts and algorithms from the continuous domain to the discrete domain. As an example we consider the discrete version of the problem of finding all intersections of a collection of line segments. We formulate criteria for a satisfactory solution to this problem, and design an interface between the continuous domain and the discrete domain which supports certain invariants. This interface enables us to obtain a satisfactory solution by using plane-sweep and a variant of the continued fraction algorithm.