The Research On Two Data Structures In External Memory Algorithms

In recent years, we have been deluged by a torrent of data from a variety ofincreasingly data-intensive applications. Data sets in large applications are often toomassive to fit completely inside the computer's internal memory. The resultinginput/output communication (or I/O) between fast internal memory and slowerexternal memory (such as disks) can be a major performance bottleneck. Especially,in those fields such as: massive geometric data in spatial database, science of statistics,geographical information system(GIS), logical constraints, computer graphics, virtualreality system and so on. Hence, the field that design and analyze the externalmemory algorithms and data structures has appeared, whose goal is to exploiteffectiveness in order to reduce the I/O costs as for as possible.Firstly, according to the Fibonacci heap's characteristics in internal memory, anew data structure for external memory algorithm is proposed. Then, the timecomplexity of its operations is analyzed. Later, the feasibility and availability of thedata structure is illustrated by the application of Fibonacci heap in the Dijkstraalgorithm.Secondly, because the double ended priority queues are data structures whichsupport the operations of both delete-max and delete-min at the same time. Therefore,we propose a new double ended priority queue which is based on the research of heapin external memory algorithms in this paper. which is based on the research of heap inexternal memory algorithms. Then, the time complexity of its operations is analyzed,it is proved that the operations can be finished with logarithmic number of pagetransfers except for the operation of search with unit time. Later, an application of thedata structure in external memory is realized through the packet buffer of the networktransmission.Primary researches and innovations in this paper are as follows.(1) For the problem of the data structure in external memory algorithms, withoutan operation can be finished in unit time. According to the Fibonacci heap'scharacteristics in internal memory, a new data structure for external memoryalgorithm is proposed, which need unit time to complete the operations.. Finally, thefeasibility and availability of the data structure is illustrated by an example.(2) Based on the research of heap in external memory algorithms, a new doubleended priority queues is proposed, which support the operations of findmax, findmin,deletemax, deletemin at the same time. Then, the time complexity of its operations isanalyzed, it is proved that the operations can be finished with logarithmic number of page transfers except for the operation of search with unit time. The applications ofdouble ended priority are further expanded thought designing this data structure, andthey laid the foundation for the effective treatment of mass data in the network.