Return to Faculty Listing
Alberto Segre Ph.D.
alberto-segreuiowadotedu
Professor of Computer Science

The focus of my research is on nagging, a distributed search paradigm that exploits the speedup anomaly by playing multiple reformulations of the problem -- or portions of the problem -- against each other. Originally developed within the relatively narrow context of distributed automated deduction, we have recently shown how nagging can be generalized and used to parallelize three other standard search algorithms (i.e., A* search, alpha-beta-minimax game tree search, and the Davis-Putnam search algorithm from the artificial intelligence literature. Our results clearly show, both empirically and analytically, the performance advantage of nagging over partitioning for some search algorithms and problem domains. Aside from performance considerations, we note that nagging holds several additional practical advantages over partitioning; it is intrinsically fault tolerant, naturally load-balancing, requires relatively brief and infrequent interprocessor communication, and is robust in the presence of reasonably large message latencies. These properties contribute directly to nagging's demonstrated scalability, making it particularly well suited for use on geographically-distributed networks of processing elements. More recently, I have begun to work on applications of nagging to two important biological optimization problems, both of which have become the topic of ongoing multidisciplinary collaborations between our laboratory and other University of Iowa faculty in the life sciences. The first involves finding the ``best'' three-dimensional conformation of a protein (or portion of a protein) with respect to some model of protein energetics, while The second involves using patterns of heritability to find the ``most likely'' location of the DNA mutation responsible for a disease. All of these projects are based on the NICE infrastructure, which is actively under development in our laboratory. My research is supported by the National Science Foundation.

Selected Publications

A.M. Segre and C.P. Elkan, "A High Performance Explanation- Based Learning Algorithm," Artificial Intelligence 69:1-2, North Holland (September 1994), pp. 1-50.

A.M. Segre, G.J. Gordon, and C.P. Elkan, "Exploratory Analysis of Speedup Learning Data Using Expectation Maximization," Artificial Intelligence 85:1-2, North Holland (August 1996), pp. 301-319.

D.B. Sturgill and A.M. Segre, "Nagging: A Distributed Adversarial Search-Pruning Technique Applied to First-Order Logic," Journal of Automated Reasoning 19:3, Kluwer Academic (December 1997), pp. 347-376.

S. Kim and A.M. Segre, "AMASS: A Structured Pattern Matching Approach to Shotgun Sequence Assembly," Journal of Computational Biology 6:2 (Spring 1999), pp. 163-186.

A.M. Segre, S. Forman, G. Resta, and A. Wildenberg, "Nagging: A Scalable, Fault-Tolerant, Distributed Search Paradigm," Artificial Intelligence 140:1-2, North Holland (September 2002), pp. 71-106