Sorting Data via a Look-Up-Table Neural Network and Self-Regulating Index
The so-called learned sorting, which was first proposed by Google, achieves data sorting by predicting the placement positions of unsorted data elements in a sorted sequence based on machine learning models. Learned sorting pioneers a new generation of sorting algorithms and shows a great potential...
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2020/4793545 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832567289999785984 |
|---|---|
| author | Ying Zhao Dongli Hu Dongxia Huang You Liu Zitong Yang Lei Mao Chao Liu Fangfang Zhou |
| author_facet | Ying Zhao Dongli Hu Dongxia Huang You Liu Zitong Yang Lei Mao Chao Liu Fangfang Zhou |
| author_sort | Ying Zhao |
| collection | DOAJ |
| description | The so-called learned sorting, which was first proposed by Google, achieves data sorting by predicting the placement positions of unsorted data elements in a sorted sequence based on machine learning models. Learned sorting pioneers a new generation of sorting algorithms and shows a great potential because of a theoretical time complexity ON and easy access to hardware-driven accelerating approaches. However, learned sorting has two problems: controlling the monotonicity and boundedness of the predicted placement positions and dealing with placement conflicts of repetitive elements. In this paper, a new learned sorting algorithm named LS is proposed. We integrate a back propagation neural network with the technique of look-up-table in LS to guarantee the monotonicity and boundedness of the predicted placement positions. We design a data structure called the self-regulating index in LS to tentatively store and duly update placement positions for eliminating potential placement conflicts. Results of three controlled experiments demonstrate that LS can effectively control the monotonicity and boundedness, achieve a better time consumption than quick sort and Google’s learned sorting, and present an excellent stability when the data size or the number of repetitive elements increases. |
| format | Article |
| id | doaj-art-1b2efafcb03c401292065607e035a8c6 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-1b2efafcb03c401292065607e035a8c62025-02-03T01:01:52ZengWileyComplexity1076-27871099-05262020-01-01202010.1155/2020/47935454793545Sorting Data via a Look-Up-Table Neural Network and Self-Regulating IndexYing Zhao0Dongli Hu1Dongxia Huang2You Liu3Zitong Yang4Lei Mao5Chao Liu6Fangfang Zhou7School of Computer Science and Engineering, Central South University, Changsha 410083, ChinaSchool of Computer Science and Engineering, Central South University, Changsha 410083, ChinaSchool of Computer Science and Engineering, Central South University, Changsha 410083, ChinaSchool of Computer Science and Engineering, Central South University, Changsha 410083, ChinaSchool of Automation, Central South University, Changsha 410083, ChinaSchool of Computer Science and Engineering, Central South University, Changsha 410083, ChinaInstitute of Systems Engineering, Academy of Military Sciences, People’s Liberation Army, Beijing 100000, ChinaSchool of Computer Science and Engineering, Central South University, Changsha 410083, ChinaThe so-called learned sorting, which was first proposed by Google, achieves data sorting by predicting the placement positions of unsorted data elements in a sorted sequence based on machine learning models. Learned sorting pioneers a new generation of sorting algorithms and shows a great potential because of a theoretical time complexity ON and easy access to hardware-driven accelerating approaches. However, learned sorting has two problems: controlling the monotonicity and boundedness of the predicted placement positions and dealing with placement conflicts of repetitive elements. In this paper, a new learned sorting algorithm named LS is proposed. We integrate a back propagation neural network with the technique of look-up-table in LS to guarantee the monotonicity and boundedness of the predicted placement positions. We design a data structure called the self-regulating index in LS to tentatively store and duly update placement positions for eliminating potential placement conflicts. Results of three controlled experiments demonstrate that LS can effectively control the monotonicity and boundedness, achieve a better time consumption than quick sort and Google’s learned sorting, and present an excellent stability when the data size or the number of repetitive elements increases.http://dx.doi.org/10.1155/2020/4793545 |
| spellingShingle | Ying Zhao Dongli Hu Dongxia Huang You Liu Zitong Yang Lei Mao Chao Liu Fangfang Zhou Sorting Data via a Look-Up-Table Neural Network and Self-Regulating Index Complexity |
| title | Sorting Data via a Look-Up-Table Neural Network and Self-Regulating Index |
| title_full | Sorting Data via a Look-Up-Table Neural Network and Self-Regulating Index |
| title_fullStr | Sorting Data via a Look-Up-Table Neural Network and Self-Regulating Index |
| title_full_unstemmed | Sorting Data via a Look-Up-Table Neural Network and Self-Regulating Index |
| title_short | Sorting Data via a Look-Up-Table Neural Network and Self-Regulating Index |
| title_sort | sorting data via a look up table neural network and self regulating index |
| url | http://dx.doi.org/10.1155/2020/4793545 |
| work_keys_str_mv | AT yingzhao sortingdataviaalookuptableneuralnetworkandselfregulatingindex AT donglihu sortingdataviaalookuptableneuralnetworkandselfregulatingindex AT dongxiahuang sortingdataviaalookuptableneuralnetworkandselfregulatingindex AT youliu sortingdataviaalookuptableneuralnetworkandselfregulatingindex AT zitongyang sortingdataviaalookuptableneuralnetworkandselfregulatingindex AT leimao sortingdataviaalookuptableneuralnetworkandselfregulatingindex AT chaoliu sortingdataviaalookuptableneuralnetworkandselfregulatingindex AT fangfangzhou sortingdataviaalookuptableneuralnetworkandselfregulatingindex |