NDLI: Confluently Persistent Tries for Efficient Version Control

Content Provider	Springer Nature Link
Author	Demaine, Erik D. Langerman, Stefan Price, Eric
Copyright Year	2009
Abstract	We consider a data-structural problem motivated by version control of a hierarchical directory structure in a system like Subversion. The model is that directories and files can be moved and copied between two arbitrary versions in addition to being added or removed in an arbitrary version. Equivalently, we wish to maintain a confluently persistent trie (where internal nodes represent directories, leaves represent files, and edge labels represent path names), subject to copying a subtree between two arbitrary versions, adding a new child to an existing node, and deleting an existing subtree in an arbitrary version.Our first data structure represents an n-node degree-Δ trie with O(1) “fingers” in each version while supporting finger movement (navigation) and modifications near the fingers (including subtree copy) in O(lg Δ) time and space per operation. This data structure is essentially a locality-sensitive version of the standard practice—path copying—costing O(dlg Δ) time and space for modification of a node at depth d, which is expensive when performing many deep but nearby updates. Our second data structure supporting finger movement in O(lg Δ) time and no space, while modifications take O(lg n) time and space. This data structure is substantially faster for deep updates, i.e., unbalanced tries. Both of these data structures are functional, which is a stronger property than confluent persistence. Without this stronger property, we show how both data structures can be sped up to support movement in O(lg lg Δ), which is essentially optimal. Along the way, we present a general technique for global rebuilding of fully persistent data structures, which is nontrivial because amortization and persistence do not usually mix. In particular, this technique improves the best previous result for fully persistent arrays and obtains the first efficient fully persistent hash table.
Starting Page	462
Ending Page	483
Page Count	22
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	57
Issue Number	3
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2009-05-29
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Data Structures, Cryptology and Information Theory Computer Systems Organization and Communication Networks Algorithms Mathematics of Computing Theory of Computation Algorithm Analysis and Problem Complexity
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology

Universal Asymptotics for Random Tries and PATRICIA Trees

Efficient Algorithms for k Maximum Sums

An Experimental Study of Compression Methods for Dynamic Tries

Energy-Efficient Paths in Radio Networks

An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem

Using Nondeterminism to Design Efficient Deterministic Algorithms

Efficient Regular Data Structures and Algorithms for Dilation, Location, and Proximity Problems

Efficient Reorganization of Binary Search Trees

Confluently Persistent Tries for Efficient Version Control

Similar Documents

The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology

Universal Asymptotics for Random Tries and PATRICIA Trees

Efficient Algorithms for k Maximum Sums

An Experimental Study of Compression Methods for Dynamic Tries

Energy-Efficient Paths in Radio Networks

An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem

Using Nondeterminism to Design Efficient Deterministic Algorithms

Efficient Regular Data Structures and Algorithms for Dilation, Location, and Proximity Problems

Efficient Reorganization of Binary Search Trees

Confluently Persistent Tries for Efficient Version Control