期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We obtain improved lower bounds for a class of static and dynamic
data structure problems that includes several problems of searching
sorted lists as special cases.
These lower bounds nearly match the upper bounds given by recent
striking improvements in searching algorithms given by Fredman and
Willard's fusion trees and Andersson's search data structure.
Thus they show sharp limitations on the running time improvements
obtainable using the unit-cost word-level RAM operations that those
algorithms employ.
关键词：Cell-Probe Model, Communication complexity, data structures, lower bounds, Searching
