China
Africa
Explore chapters and articles related to this topic
External Memory Data Structures
Published in Suman Saha, Shailendra Shukla, Advanced Data Structures, 2019
Early work on I/O algorithms concentrated on algorithms for sorting and permutation-related problems in the single disk model, as well as in the extended version of the I/O model. In the single disk model, external sorting requires O(nlogmN) I/Os, which is the external equivalent of the well-known (N log N) internal sorting bound. Searching for an element among N elements requires O(logBN) I/Os. More recently external algorithms and data structures have been developed for a number of problems in different areas.
Big data processing with 1D-Crosspoint Arrays
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
As a consequence of the lower hardware complexity, however, the time complexity of the algorithm increases. Assuming that the time complexity of a single execution of a searching or sorting algorithm for an n-element list is as before, its contribution to the is , since the model requires the execution of the algorithm times. Therefore, the time complexity of searching or sorting N data elements on Model 2-C may be expressed as If n is kept small to avoid excessive hardware complexity, will be large and increase . On the other hand, if is made small to keep the term small, n will be large and increase the hardware complexity. Similar to Model 2-B, the can be reduced by increasing the bandwidth of the data channel. In such a case, the best time complexity can be achieved by reducing the as much as possible, ideally reducing it to . It is established in Section 4 that the 1D-Crosspoint Array performs searching and sorting an n element list in time, which thus makes the overall time complexity of external sorting on Model 2C for any given n.