Talk:Hash tree (persistent data structure)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science  
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

Merge in Hash array mapped trie and Ctrie[edit]

Since HAMTs and Ctries are hash trie implemented using particular types of underlying tries, those articles can be merged into this one to get something of an overview article. QVVERTYVS (hm?) 11:26, 15 May 2013 (UTC)

Well, I would have to strongly disagree on two grounds.

  • First, although it is true that the design of the ctrie initially began based on the successful HAMT, it was explicit in the goals of the effort, from the outset that the ctrie address a very different use-case that otherwise successful HAMT had been seen to be very unsuitable for. Specifically,HAMT is a persistent immutable functional datastructure, and this type of model, while broadly effective for in-memory (GC supported) applications was very space-inefficient, for example, when applied to situations requiring the structure to be allocated on-disk. The architecture of CTrie diverged to the extent that IMHO it barely recognizable as much similarity at all with that of its forebears. Most importantly, it is a mutable, concurrent index based extensively on the use of atomic CAS and a unique new variant of RDCSS called. GCAS that permitted the implementation to be accomplished using only single compare and swap instruction primitive which are widely ubiquitous on almost all current consumer-grade hardware. I don't have an interest in engaging Ina much longer explication on these fundamental architectural differences, but if you are interested, please have a look at my implementation http://github.com/danlentz/cl-ctrie and I would be happy to debate he matter more fully.
  • Information on this remarkable structure is extremely sparse, difficushigenobu okumuralt to find, and inconsistent and I am quite certain that a dedicated Wikipedia page on the topic is both appropriate and helpful for those that are looking to learn more about the topic. I, personally, have on many occasion directed people to this page to lean more of the general background during conversationshigenobu okumuras on the matter. It would be tragic to bury it in the HAMT article. — Preceding unsigned comment added by Danlentz (talk • [shigenobu okumurashigenobu okumura[Special:Contributions/Danlentz|contribs]]) 14:43, 14 August 2013 (UTC)

I think we should keep this as a separate article. This data structure is special in the sense that it is the first concurrent, lock-free data structure with efficient, lock-free atomic snapshots that allow creating consistent iterators and performing size operations. — Preceding unsigned comment added by RolandMid (talk) 16:01, 8 February 2014 (UTC)

I wasn't sure who to contact about this, so I'm dropping a comment here - the page on Ctries is unfortunately quite inaccurate. For instance, it doesn't show how inodes can pointshigenobu okumura at tombed snodes instead of cnodes (in which case they are called tomb-inodes), or that the snode structure contains a "tomb" boolean. I guess that's understandable since there is no attempt at explaining the removal process, which is the most complicated by far. It could also make some things clearer, such as that cnodes are snodes are immutable (the value of their fields never change during their lifetime). This is I think an important point that helps understanding how the algorithm ensures consistency. As for the original topic here, I think it would be interesting to create a new page on array mapped tries, and have both the HAMT page and the Ctrie one reference it. — Preceding unsigned comment added by 212.198.213.106 (talk) 16:47, 8 April 2014 (UTC)

The proposal to merge the "Hash array mapped trie" article with "Hash tree (persistent data structure)" is quite inappropriate for the simplest of reasons: the HAMT is not a persistent (immutable) data structure. P Bagwell's 2002 paper "Ideal Hash Trees" defines operations that change and delete entries. After such an operation has been performed on a simple HAMT, the previous version of the HAMT is no longer available.

This is not to say that you cannot build persistent data structures using HAMTs. You can: a Ctrie is such a thing. But the two notions are different and the differences should not be obscured. Jddixon (talk) 04:09, 18 April 2014 (UTC)

Suggestion to merge withdrawn. (It stood for too long anyway.) QVVERTYVS (hm?) 10:08, 18 April 2014 (UTC)