NDLI: Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Sundar, Rajamani Tarjan, Robert E.
Copyright Year	1994
Abstract	This paper studies the problem of representing sets over an ordered universe by unique binary search trees, so that dictionary operations can be performed efficiently on any set. Although efficient randomized solutions to the problem are known, its deterministic complexity has been open. The paper exhibits representations that permit the execution of dictionary operations in optimal deterministic time when the dictionary is sufficiently sparse or sufficiently dense. The results demonstrate an exponential separation between the deterministic and randomized complexities of the problem.Unique representations are applied to obtain efficient data structures for maintaining a dynamic collection of sets/sequences under queries that test the equality of a pair of objects. The data structure for set equality testing tests equality of sets in constant time and processes set updates in $O(\log m)$ amortized time and $O(\log m)$ space, where m denotes the total number of updates performed. It is based on an efficient implementation of cascades of CONS operations on uniquely stored S-expressions. The data structure for sequence equality testing tests equality of sequences in constant time and processes updates in $O(\sqrt {n\log m} = \log m)$ amortized time and $O(\sqrt n )$ amortized space where n denotes the length of the sequence that is updated and m denotes the total number of updates performed.
Starting Page	24
Ending Page	44
Page Count	21
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539790189733
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1
Volume Number	23
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-31
Access Restriction	Subscribed
Subject Keyword	Analysis of algorithms and problem complexity dictionary sets binary search tree unique representation Data structures data structures S-expressions programming languages sequences Combinatorics equality testing
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

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

Unique binary search tree representations and equality-testing of sets and sequences

Treewidth versus clique number. II. Tree-independence number

On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences

Binary Search on a Tape

New Tight Bounds on Uniquely Represented Dictionaries

Binary search tree visualization algorithm

On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof

Testing systems of real quadratic equations for approximate solutions

Locally checkable problems parameterized by clique-width

Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences

Similar Documents

Unique binary search tree representations and equality-testing of sets and sequences

Treewidth versus clique number. II. Tree-independence number

On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences

Binary Search on a Tape

New Tight Bounds on Uniquely Represented Dictionaries

Binary search tree visualization algorithm

On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof

Testing systems of real quadratic equations for approximate solutions

Locally checkable problems parameterized by clique-width

Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences