检索结果-内蒙古大学图书馆

28th International Computing and Combinatorics Conference (COCOON)

作者： Ma, Hengzhao Li, Jianzhong Gao, Xiangyu Gao, Tianpeng Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Peoples R China Harbin Inst Technol Harbin Peoples R China

ISBN: (纸本)9783031221040;9783031221057

The input/output complexity, which is the complexity of data exchange between the main memory and the external memory, has been elaborately studied by a lot of former researchers. However, the existing works failed to consider the input/output complexity in a computation model point of view. In this paper we remedy this by proposing three variants of Turing machine that include external memory and the mechanism of exchanging data between main memory and external memory. Based on these new models, the input/output complexity is deeply studied. We discuss the relationship between input/output complexity and the other complexity measures such as time complexity and parameterized complexity, which is not considered by former researchers. We also define the external access trace complexity, which reflects the physical behavior of magnetic disks and gives a theoretical evidence of IO-efficient algorithms.

关键词： Computational theory Computational model input/output complexity

来源：评论

学校读者我要写书评

暂无评论

Turing machines with two-level memory: New computational models for analyzing the input/output complexity

引用

THEORETICAL COMPUTER SCIENCE 2024年 985卷

作者： Ma, Hengzhao Li, Jianzhong Gao, Tianpeng Gao, Xiangyu Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Peoples R China Harbin Inst Technol Weihai Peoples R China

The input/output complexity, which is the complexity of data exchange between the main memory and the external memory, has been elaborately studied by a lot of former researchers. However, the existing works failed to consider the input/output complexity in a computational model point of view. In this paper we remedy this by proposing four variants of Turing machine that include external memory and the mechanism of exchanging data between main memory and external memory. Based on these new models, the input/output complexity is deeply studied. We discuss the relationship between input/output complexity and the other complexity measures such as time complexity and parameterized complexity, which is not considered by former researchers. We also define the external access trace complexity, which reflects the physical behavior of magnetic disks and gives a theoretical evidence of IO-efficient algorithms. Finally, we generalize the model into parallel computation environments, and discuss the relationship between input/output complexity and communication complexity.

关键词： Computational theory Computational model input/output complexity

来源：评论

学校读者我要写书评

暂无评论

Blocking for external graph searching

引用

ALGORITHMICA 1996年第2期16卷 181-214页

作者： Nodine, MH Goodrich, MT Vitter, JS JOHNS HOPKINS UNIV DEPT COMP SCI BALTIMORE MD 21218 USA DUKE UNIV DEPT COMP SCI DURHAM NC 27708 USA

In this paper we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for complete d-ary trees and d-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex. We also show that, for the special case, of grid graphs blocked with isothetic hypercubes,there is a provably better speed-up if even a small amount of redundancy is permitted.

关键词： external searching isothetic hypercubes blocking input/output complexity redundancy

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：