文章基本信息

标题：On The Implementation of Recursive Data Structures for Cache-Oblivious Algorithms
本地全文：下载
作者：M. Imani ; A. Moeini ; F. Ghasemi 等
期刊名称：International Journal of Mechatronics, Electrical and Computer Technology
印刷版ISSN：2305-0543
出版年度：2016
卷号：6
期号：21
页码：3032-3042
出版社：Austrian E-Journals of Universal Scientific Organization
摘要：This paper presents implementation of two important recursive data structures. First data structure is k-funnel that can merge k sorted input lists into a single sorted list. The k-funnel is an integral part of Funnelsort. The second data structure is cache-oblivious search tree that using the van Emde Boas layout for mapping from the nodes in the tree to positions in memory. We focus on the challenges in implementing them. A clever implicit navigation method of Brodal is used in the search navigation process. We also experimentally compare cache-oblivious data structures with traditional RAM model data structures.
关键词：data structure; cache-oblivious; k-funnel; Funnelsort; van Emde Boas layout; RAM model