File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: An improved scheme for set equality testing and updating

TitleAn improved scheme for set equality testing and updating
Authors
Issue Date1998
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 1998, v. 201 n. 1-2, p. 85-97 How to Cite?
AbstractThis 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 Identifierhttp://hdl.handle.net/10722/152311
ISSN
2015 Impact Factor: 0.643
2015 SCImago Journal Rankings: 0.720
References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_US
dc.contributor.authorLee, KHen_US
dc.date.accessioned2012-06-26T06:37:05Z-
dc.date.available2012-06-26T06:37:05Z-
dc.date.issued1998en_US
dc.identifier.citationTheoretical Computer Science, 1998, v. 201 n. 1-2, p. 85-97en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://hdl.handle.net/10722/152311-
dc.description.abstractThis 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.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_US
dc.relation.ispartofTheoretical Computer Scienceen_US
dc.titleAn improved scheme for set equality testing and updatingen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/S0304-3975(97)00024-8-
dc.identifier.scopuseid_2-s2.0-0347599194en_US
dc.identifier.hkuros40762-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0347599194&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume201en_US
dc.identifier.issue1-2en_US
dc.identifier.spage85en_US
dc.identifier.epage97en_US
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridLee, KH=9277028400en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats