|
|
|
@inproceedings{DBLP:conf/pods/HuangL88,
author = {Bing-Chao Huang and
Michael A. Langston},
editor = {Chris Edmondson-Yurkanan and
Mihalis Yannakakis},
title = {Stable Set and Multiset Operations in Optimal Time and Space},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, March 21-23, 1988, Austin,
Texas, USA},
publisher = {ACM},
year = {1988},
isbn = {0-89791-263-2},
pages = {288-293},
ee = {http://doi.acm.org/10.1145/308386.308458, db/conf/pods/HuangL88.html},
crossref = {DBLP:conf/pods/88},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
The focus of this paper is on demonstrating the existence of methods for stably performing set and multiset operations on sorted files of data in both optimal time and optimal extra space. It is already known that stable merging and stable duplicate-key extraction permit such methods. The major new results reported herein are these
1) an asymptotically optimal time and space algorithm is devised for stably selecting matched records from a sorted file,
2) this selection strategy is employed, along with other algorithmic tools, to prove that all of the elementary binary set operations can be stably performed in optimal time and space on sorted files, and
3) after generalizing these operations to multisets in a natural way for file processing, it is proved that each can be stably performed in optimal time and space on sorted files.
Copyright © 1988 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.
Data released under the ODC-BY 1.0 license — See also our legal information page