Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Making data structures confluently persistent
Fiat A., Kaplan H. Journal of Algorithms48 (1):16-58,2003.Type:Article
Date Reviewed: Aug 5 2004

This paper presents a general technique to transform any pointer-based data structure into one that is “confluently persistent,” thus answering a longstanding open problem posed by Driscoll, Sarnak, Sleator, and Tarjan [1], and refined by Driscoll, Sleator, and Tarjan [2]. An initial configuration of a data structure is version zero, and every subsequent update operation creates a new version of the data structure. A “fully persistent data structure” has the property that every version can be both accessed and modified. “Confluently persistent” refers to fully persistent data structures that support meld operations that combine two different versions of a structure, as in set union or list catenation. The main contribution of this paper is to show that confluently persistent data structures are feasible.

The paper is organized into sections. The introductory section is quite good at setting the framework for how this paper differs in approach from the foundational works cited above. The heart of the approach taken is a “version DAG” (DAG stands for acyclic directed graph) that allows an update to any version of the underlying data structure that coexists with all previous versions. The second section presents a lower bound on the space requirement for any general scheme that will make a data structure confluently persistent. The third section contains a brief overview of the previous “fat node method” for fully persistent data structures. The fourth section addresses the “full path method,” which is a straightforward means of making a data structure confluently persistent. The fifth section describes the “compressed path method,” which provides certain advantages for some data structures. The sixth section is concerned with randomized variations of the full path and compressed path methods that can provide significant time speedup results. As one would expect, the constant theme throughout this paper is one of tradeoffs between space and time. The final section provides brief concluding remarks that include a suggestion for future work.

The general presentation of the paper is effective, carefully written, rigorous, and complete, with helpful tables and figures that illustrate and support the text. This paper represents a significant contribution to the design and analysis of algorithms.

Reviewer:  M. G. Murphy Review #: CR129965 (0501-0058)
1) Driscoll, J.R.; Sarnak, N.; Sleator, D. Making data structures persistent. J. Comput. System Sci. 38, (1989), 86–124.
2) Driscoll, J.; Sleator, D.; Tarjan, R. Fully persistent lists with catenation. J. ACM 41, 5 (1994), 943–959.
Bookmark and Share
  Featured Reviewer  
 
Distributed Data Structures (E.1 ... )
 
 
Lists, Stacks, And Queues (E.1 ... )
 
 
Representations, Data Structures, And Transforms (I.2.10 ... )
 
 
Vision And Scene Understanding (I.2.10 )
 
 
Data Structures (E.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Distributed Data Structures": Date
LH*RS--a highly-available scalable distributed data structure
Litwin W., Moussa R., Schwarz T. ACM Transactions on Database Systems 30(3): 769-811, 2005. Type: Article
Jan 19 2006
Skip graphs
Aspnes J., Shah G. ACM Transactions on Algorithms 3(4): 37-es, 2007. Type: Article
Apr 16 2008
Replicated abstract data types: building blocks for collaborative applications
Roh H., Jeon M., Kim J., Lee J. Journal of Parallel and Distributed Computing 71(3): 354-368, 2011. Type: Article
Jul 21 2011
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy