NDLI: Strongly History Independent Hashing with Deletion (2006)

Please wait, while we are loading the content...

Strongly History Independent Hashing with Deletion (2006)

Content Provider	CiteSeerX
Author	Blelloch, Guy E. Golovin, Daniel
Abstract	We present a strongly history independent (SHI) hash table that is fast, space efficient, and supports deletions. A hash table that supports deletions is SHI if it has a canonical memory representation up to randomness. That is, the string of random bits and current hash table contents (the set of (key, object) pairs in the hash table) uniquely determine its layout in memory, independently of the sequence of operations from initialization to the current state. Thus, the memory representation of a SHI hash table reveals exactly the information available through the hash table interface, and nothing more. Our construction also reveals a subtle connection between history independent hashing and the Gale-Shapley stable marriage algorithm [7], which may be of independent interest. Additionally, we give a general technique for converting data structures with canonical representations in a pure pointer machine model into RAM data structures of comparable performance and that are SHI with high probability. Thus we develop the last ingredient necessary to efficiently implement a host of SHI data structures on a RAM. This research is supported by NSF ITR grants CCR-0122581 (The Aladdin Center) and IIS-0121678.
File Format	PDF
Publisher Date	2006-01-01
Access Restriction	Open
Subject Keyword	History Independent Hash Table Canonical Representation Independent Interest Aladdin Center Nsf Itr Grant Ccr-0122581 Random Bit Gale-shapley Stable Marriage Shi Hash Table Reveals Hash Table Interface Space Efficient Last Ingredient Pure Pointer Machine Model Support Deletion Current Hash Table Content Comparable Performance Canonical Memory Representation Subtle Connection History Independent Hashing General Technique Shi Data Structure Ram Data Structure Memory Representation
Content Type	Text

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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