Academic
Publications
Fully Persistent Arrays for Efficient Incremental Updates and Voluminous Reads

Fully Persistent Arrays for Efficient Incremental Updates and Voluminous Reads,10.1007/3-540-55253-7_7,Tyng-ruey Chuang

Fully Persistent Arrays for Efficient Incremental Updates and Voluminous Reads   (Citations: 5)
BibTex | RIS | RefWorks Download
The array update problem in a purely functional language is the following: oncean array is updated, both the original array and the newly updated one mustbe preserved to maintain referential transparency. We devise a very simple, fullypersistent data structure to tackle this problem such thatffl each incremental update costs O(1) worst--case time,ffl a voluminous sequence of r reads cost in total O(r) amortized time, andffl the data structure use O(n + u) space,where n is the size ...
Conference: European Symposium on Programming - ESOP , pp. 110-129, 1992
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Chuang’s paper [7] and to Christine Paulin for encouraging us to perform a verification proof in Coq...

    Sylvain Conchonet al. A persistent union-find data structure

    • ...Trailer arrays [2, 1, 3, 4] are a popular choice with a particular set of trade os. The method is easy to implement, requires constant space for singleelement updates, and supports many common access patterns in constant time or constant amortized time (see Section 7 for a comparison with other techniques)...
    • ...Chuang [3, 4] suggests two possible enhancements to the basic ideas of trailer arrays, each of which can reduce the length of a chain of deltas at the cost of creating additional ephemeral arrays...
    • ...In his first paper [3], he waits until a long (> 2n) reroot is performed and then splits the tree after every ( n) deltas...

    Laura Effinger-Deanet al. Garbage Collection for Trailer Arrays

    • ...Persistent data structures [1, 6, 5, 7, 2, 3, 14, 13] are particularly hard to garbage collect...

    Laura Effinger-Deanet al. Extending Garbage Collection to Complex Data Structures

Sort by: