Umut A. Acar

Abstract An Experimental Analysis of Self-Adjusting Computation (2008)

We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be...

Selective Memoization \Lambda (2008)

Dependence graphs and memoization can be used to efficiently update the output of a program as the input changes dynamically. Recent work has studied techniques for combining these approaches to...

Abstract An Experimental Analysis of Self-Adjusting Computation (2008)

Abstract We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that...

Abstract Adaptive Memoization ∗ (2008)

Dependence graphs and memoization can be used to efficiently update the output of a program as the input changes dynamically. Recent work has studied techniques for combining these approaches to...

Stability, Adaptivity, and Dynamic Algorithms (2008)

Memoization may be reviewed as a mechanism for re-using a computation—if a function is re-applied to the same argument we may re-use the previous computation to determine the result, rather than...

Umut A. Acar, Daniel D. Sleator

A dynamic algorithm maintains the relationship between its input and output as the input changes online. In previous work, researchers developed dynamic algorithms on a per problem basis by using...

ABSTRACT A Proposal for Parallel Self-Adjusting Computation (2008)

Matthew Hammer, Umut A. Acar

We present an overview of our ongoing work on parallelizing self-adjusting-computation techniques. In self-adjusting computation, programs can respond to changes to their data (e.g., inputs, outcomes...

hulls.

hulls.

Abstract An Experimental Analysis of Self-Adjusting Computation (2008)

Dependence graphs and memoization can be used to efficiently update the output of a program as the input changes dynamically. Recent work has studied techniques for combining these approaches to...

and (2008)

Abstract Adaptive Memoization ∗ (2008)

We present techniques for incremental computing by introducing adaptive functional programming. As an adaptive program executes, the underlying system represents the data and control dependences in...

Umut A. Acar, Alexander T. Ihler, Ramgopal R. Mettu, Özgür Sümer

Memoization may be viewed as a mechanism for re-using a computation—if a function is re-applied to the same argument we may re-use the previous computation to determine the result, rather than...

Abstract (2008)

Motivated by stochastic systems in which observed evidence and conditional dependencies between states of the network change over time, and certain quantities of interest (marginal distributions,...

Imperative self-adjusting computation (2008)

Umut A. Acar, Amal Ahmed, Matthias Blume

Self-adjusting computation enables writing programs that can automatically and efficiently respond to changes to their data (e.g., inputs). The idea behind the approach is to store all data that can...

Imperative self-adjusting computation (2008)

Umut A. Acar, Amal Ahmed, Matthias Blume

Recent work on self-adjusting computation showed how to systematically write programs that respond efficiently to incremental changes in their inputs. The idea is to represent changeable data using...

Adaptive Bayesian inference (2008)

Umut A. Acar, Alexander T. Ihler, Ramgopal R. Mettu, Özgür Sümer

Motivated by stochastic systems in which observed evidence and conditional dependencies between states of the network change over time, and certain quantities of interest (marginal distributions,...

Adaptive Memoization (2007)

Provenance as dependency analysis (2007)

Memoization may be viewed as a mechanism for re-using a computation---if a function is re-applied to the same argument we may re-use the previous computation to determine the result, rather than...

James Cheney, Amal Ahmed, Umut A. Acar

Abstract. Provenance is information recording the source, derivation, or history of some information. Provenance tracking has been studied in a variety of settings; however, although many design...

Provenance as dependency analysis (2007)

James Cheney, Amal Ahmed, Umut A. Acar

Abstract. Provenance is information recording the source, derivation, or history of some information. Provenance tracking has been studied in a variety of settings; however, although many design...

A consistent semantics of self-adjusting computation (2007)

SVR: Practical engineering of a fast 3D meshing algorithm (2007)

This paper presents a semantics of self-adjusting computation and proves that the semantics is correct and consistent. The semantics integrates change propagation with the classic idea of memoization...

Umut A. Acar, Benoît Hudson, Gary L. Miller, Todd Phillips

Summary. The recent Sparse Voronoi Refinement (SVR) Algorithm for mesh generation has the fastest theoretical bounds for runtime and memory usage. We present a robust practical software...

Kinetic algorithms via self-adjusting computation (2006)

Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, Jorge L. Vittes

Abstract. Define a static algorithm as an algorithm that computes some combinatorial property of its input consisting of static, i.e., non-moving, objects. In this paper, we describe a technique for...

A consistent semantics of self-adjusting computation (2006)

A consistent semantics of self-adjusting computation (2006)

Abstract. This paper presents a semantics of self-adjusting computation and proves that the semantics is correct and consistent. The semantics integrates change propagation with the classic idea of...

A consistent semantics of self-adjusting computation (2006)

This paper presents a semantics of self-adjusting computation and proves that the semantics is correct and consistent. The semantics integrates change propagation with the classic idea of memoization...

Traceable Data Structures (2006)

This paper presents a semantics of self-adjusting computation and proves that the semantics is correct and consistent. The semantics integrates change propagation with the classic idea of memoization...

Umut A. Acar, Guy E. Blelloch, Srinath Sridhar, Virginia Vassilevska

We consider the problem of tracking the history of a shared data structure so that a user can efficiently view any previous version of the structure (persistence), and efficiently recover information...

Kinetic algorithms via self-adjusting computation (2006)

Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, Jorge L. Vittes

Abstract. Define a static algorithm as an algorithm that computes some combinatorial property of its input consisting of static, i.e., non-moving, objects. In this paper, we describe a technique for...

An experimental analysis of self-adjusting computation (2006)

Umut A. Acar, Guy E. Blelloch, Matthias Blume, Robert Harper

Self-adjusting computation uses a combination of dynamic dependence graphs and memoization to efficiently update the output of a program as the input changes incrementally or dynamically over time....

Self-adjusting computation / (2005)

Acar, Umut A.

Abstract: "This thesis investigates a model of computation, called self-adjusting computation, where computations adjust to any external change to their data (state) automatically. The external...

Self-adjusting computation / (2005)

Acar, Umut A.

Thesis (Ph. D.)--Carnegie Mellon University, 2005.

Self-Adjusting Computation (2005)

Self-Adjusting Computation (2005)

From the algorithmic perspective, we describe novel data structures for tracking the dependences ina computation and a change-propagation algorithm for adjusting computations to changes. We show that...

Umut A. Acar, Daniel Dominic, Kaplan Sleator

document are those of the author and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring institution, the U.S. government or any other...

Self-Adjusting Computation (2005)

Umut A. Acar, Daniel Dominic, Kaplan Sleator

document are those of the author and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring institution, the U.S. government or any other...

Adaptive Memoization (2004)

Dynamizing Static Algorithms, with Applications to Dynamic Trees and History Independence (2004)

We combine adaptivity and memoization to obtain an incremental computation technique that dramatically improves performance over adaptivity and memoization alone. The key contribution is adaptive...

Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, Shan Leung

We describe a machine model for automatically dynamizing static algorithms and apply it to historyindependent data structures. Static programs expressed in this model are dynamized automatically by...

Selective memoization (2003)

Adaptive Memoization (2003)

We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be...

Selective Memoization (2003)

We combine adaptivity and memoization to obtain an incremental computation technique that dramatically improves performance over adaptivity and memoization alone. The key contribution is adaptive...

Adaptive memoization (2003)

We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be...

Selective Memoization (2003)

We combine adaptivity and memoization to obtain an incremental computation technique that dramatically improves performance over adaptivity and memoization alone. The key contribution is adaptive...

Selective memoization (2003)

We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be...

Adaptive memoization (2003)

Although memoization is a powerful technique and can dramatically improve performance, it is often difficult to apply effectively. This is because significant performance improvements require the...

We combine adaptivity and memoization to obtain an incremental computation technique that dramatically improves performance over adaptivity and memoization alone. The key contribution is adaptive...

An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...

An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...

An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remained limited in...

An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remained limited in...

An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...

An adaptive computation adapts its output to match changes to the input. Many techniques have been proposed for certain classes of adaptive computations, especially for particular applications such...

An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...

Adaptive Functional Programming \Lambda (2002)

An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain limited in...

Adaptive Functional Programming (2001)

Abstract An adaptive computation maintains the relationship between its input and output as the input changes. Although various techniques for adaptive computing have been proposed, they remain...