فا   |   En
ورود به سایت

Progressive sorting in the external memory model

نویسنده: Amir Mesrikhani, Mohammad Farshi

Executing all steps of an algorithm that face with massive input data may take a long time. A progressive algorithm solves the problem step by step, and produces a partial solution in each step which approximates the final solution. So, the user can decide to stop the algorithm or continue to get better solutions. In this paper, we consider the problem of sorting a set of N real numbers and design a progressive algorithm with O(log_{M/B} N/B) steps that takes O(N/B) I/O operations in each step in the external memory model. The upper bound of the error of the partial solution in step r is O(N/{(M/B)^{r/2}}).

فایل مقاله