Efficient external sorting and indexing on flash memory embedded devices

• Κύριος συγγραφέας: Σταθοπούλου, Ρουμπίνη
• Άλλοι συγγραφείς: Stathopoulou Roumpini
• Γλώσσα: Greek
• Έκδοση: 2023
• Θέματα: External sorting; Embedded devices; Ενσωματωμένες συσκευές; Εξωτερική ταξινόμηση

External sorting is a technique used to sort large datasets that cannot fit into the memory of a single computing device. It is particularly important in the context of embedded devices and the Internet of Things (IoT), where resources such as memory and I/O bandwidth are often limited. External sorting involves dividing the dataset into smaller parts, runs, which can be sorted individually and then merged together to produce the final sorted output.Several algorithms can be used for the run generation phase of external sorting, depending on the characteristics of the data being sorted and the available resources. The in-memory insertion sort algorithm is one such algorithm, which sorts small chunks of data in memory before writing them to disk as runs. The replacement selection algorithm is another algorithm, which involves dividing the dataset into fixed-size blocks, selecting the smallest item from each block, and merging them using a priority queue.For the merge phase of external sorting, NOBsort is a commonly used algorithm that minimizes I/O operations by merging runs in a way that minimizes the number of block reads and writes. This algorithm is particularly useful for large datasets that require multiple passes to sort.Adaptive algorithms for data distribution are also important in external sorting. These algorithms adapt the size and number of runs based on the characteristics of the input data and the resources available, allowing for efficient sorting even when resources are limited. One such algorithm is the adaptive sorting algorithm, which adjusts the number of runs based on the number of available disk blocks and the size of the input data. External sorting has several benefits for embedded devices and the IoT. By reducing the number of I/O operations required and minimizing memory usage, external sorting can help to optimize the performance of these devices and ensure that they operate efficiently. In addition, external sorting can help to reduce power consumption and increase the lifespan of the devices.Overall, external sorting is an important technique for managing and processing large datasets in a variety of contexts. By using efficient run generation and merge algorithms, as well as adaptive algorithms for data distribution, external sorting can help to ensure that computing devices and IoT systems operate effectively and efficiently, even with limited resources.