File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1016/S03043975(97)000248
 Scopus: eid_2s2.00347599194
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Article: An improved scheme for set equality testing and updating
Title  An improved scheme for set equality testing and updating 

Authors  
Issue Date  1998 
Publisher  Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs 
Citation  Theoretical Computer Science, 1998, v. 201 n. 12, p. 8597 How to Cite? 
Abstract  This paper is concerned with data structures for representing an arbitrary number of sets such that we can dynamically update each individual set and test whether any two sets are equal. Previous schemes (Yellin, 1990; Sundar and Tarjan, 1990) can support an equality testing in constant time and an insert or delete operation in O(log2 m) time, where m is the number of insert operations performed. The space requirement is O(m log m). Note that m is an upper bound of n, the sum of the sizes of the sets, but maybe a loose one. When we have performed a lot of delete operations, having few elements left in the sets, it is natural to expect the operations to be performed faster. Yet existing schemes are not favored when n is much smaller than m. It is desirable to have a scheme whose performance is in terms of n instead of m. This paper presents a new scheme which is more dynamic in nature, leading to two improved results: (i) An insert or delete operation can be performed in O(log n) time, with the constant time complexity of equality testing maintained. The space requirement is O(n2 log n). (ii) The space requirement can be reduced to O(n log n), while the time complexity of an insert or delete operation increases to O(log1.5 n). © 1998  Elsevier Science B.V. All rights reserved. 
Persistent Identifier  http://hdl.handle.net/10722/152311 
ISSN  2015 Impact Factor: 0.643 2015 SCImago Journal Rankings: 0.720 
References 
DC Field  Value  Language 

dc.contributor.author  Lam, TW  en_US 
dc.contributor.author  Lee, KH  en_US 
dc.date.accessioned  20120626T06:37:05Z   
dc.date.available  20120626T06:37:05Z   
dc.date.issued  1998  en_US 
dc.identifier.citation  Theoretical Computer Science, 1998, v. 201 n. 12, p. 8597  en_US 
dc.identifier.issn  03043975  en_US 
dc.identifier.uri  http://hdl.handle.net/10722/152311   
dc.description.abstract  This paper is concerned with data structures for representing an arbitrary number of sets such that we can dynamically update each individual set and test whether any two sets are equal. Previous schemes (Yellin, 1990; Sundar and Tarjan, 1990) can support an equality testing in constant time and an insert or delete operation in O(log2 m) time, where m is the number of insert operations performed. The space requirement is O(m log m). Note that m is an upper bound of n, the sum of the sizes of the sets, but maybe a loose one. When we have performed a lot of delete operations, having few elements left in the sets, it is natural to expect the operations to be performed faster. Yet existing schemes are not favored when n is much smaller than m. It is desirable to have a scheme whose performance is in terms of n instead of m. This paper presents a new scheme which is more dynamic in nature, leading to two improved results: (i) An insert or delete operation can be performed in O(log n) time, with the constant time complexity of equality testing maintained. The space requirement is O(n2 log n). (ii) The space requirement can be reduced to O(n log n), while the time complexity of an insert or delete operation increases to O(log1.5 n). © 1998  Elsevier Science B.V. All rights reserved.  en_US 
dc.language  eng  en_US 
dc.publisher  Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs  en_US 
dc.relation.ispartof  Theoretical Computer Science  en_US 
dc.title  An improved scheme for set equality testing and updating  en_US 
dc.type  Article  en_US 
dc.identifier.email  Lam, TW:twlam@cs.hku.hk  en_US 
dc.identifier.authority  Lam, TW=rp00135  en_US 
dc.description.nature  link_to_subscribed_fulltext  en_US 
dc.identifier.doi  10.1016/S03043975(97)000248   
dc.identifier.scopus  eid_2s2.00347599194  en_US 
dc.identifier.hkuros  40762   
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.00347599194&selection=ref&src=s&origin=recordpage  en_US 
dc.identifier.volume  201  en_US 
dc.identifier.issue  12  en_US 
dc.identifier.spage  85  en_US 
dc.identifier.epage  97  en_US 
dc.publisher.place  Netherlands  en_US 
dc.identifier.scopusauthorid  Lam, TW=7202523165  en_US 
dc.identifier.scopusauthorid  Lee, KH=9277028400  en_US 