The Complexity of Querying External Memory and Streaming Data
The Complexity of Querying External Memory and Streaming Data
复制标题
查询外部内存和流数据的复杂性
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Nicole Schweikardt
中科院分区：
文献类型：
--
作者：
Martin Grohe;Christoph E. Koch;Nicole Schweikardt
我们回顾了最近引入的对流和外部存储器数据的计算模型。该模型的一个重要特征是，它区分了从外部存储器(通过主存储器)顺序读取(流)数据和在特定存储器位置随机访问外部存储器数据；众所周知，后者在实践中要昂贵得多。我们解释了如何在该模型中获得一些下界结果，以及如何将它们应用于证明XML查询处理的下界。
We review a recently introduced computation model for streaming and external memory data. An important feature of this model is that it distinguishes between sequentially reading (streaming) data from external memory (through main memory) and randomly accessing external memory data at specific memory locations; it is well-known that the latter is much more expensive in practice. We explain how a number of lower bound results are obtained in this model and how they can be applied for proving lower bounds for XML query processing.