论文部分内容阅读
近年来,随着信息科技的日益发展,人们已经淹没在数据的海洋里,各种各样的数据充斥着人们的生活。其中一部分数据由于其数据量比较庞大,需要海量的存储空间,而目前的计算机内存空间不足以满足这种需求,只能将其存储在外存储器中。因此处于内外存之间传输数据的I/O通道就成为了制约算法运行效率的主要瓶颈。这种现象在如下几个方面表现的尤为明显,比如:空间数据库中的海量几何数据、数据库、统计学、地理信息系统(GIS)、约束逻辑规划、计算机图形学、虚拟现实系统等。由此产生了外存储算法与数据结构的设计和分析领域,其主要目标就是研究算法的有效性,以尽量减小程序运行过程中的输入/输出代价。本文首先研究了已有的适用于外存储算法的数据结构。基于Fibonacci堆在内存储算法中的特点,进一步改进得出了一种新的适合外存储算法的数据结构,并分析了该数据结构中各种操作的时间复杂度。并以这种数据结构在Dijkstra算法中的应用为实例证明了该数据结构的可行性和有效性。其次,双端优先级队列是一种可同时支持针对最大、最小数据进行插入,删除操作的数据结构,本文利用外存储算法中对堆的研究,设计了一种新的适合外存储算法的双端优先级队列。并分析它的操作复杂度,其中除查找操作具有单位时间的页面置换次数以外,其他操作都具有对数时间的页面置换次数。最后借助网络传输中的包缓存实现了该数据结构在外存中的应用。本文的创新点主要包括以下两个方面:(1)针对外存储算法中的数据结构问题,目前还没有支持单位时间操作复杂度的外存储算法。本文根据Fibonacci堆在内存储算法中的特点,设计出了一种针对海量数据支持单位时间操作复杂度的外存储算法。并通过实例证明了算法的可行性和有效性。(2)基于外存储算法中对堆的研究,经过一些改进得到了一种新的适应于外存储算法的双端优先级队列。该数据结构可以同时支持针对最大、最小数据的查找,删除操作。并且其查找操作的页面置换次数为O(1),其他操作的页面置换次数为O(logN)。通过这种数据结构的设计使双端优先级队列的应用得到进一步扩展,为网络中海量数据的有效处理打下了基础。