Greedy Algorithms for Approximating the Diameter of Machine Learning Datasets in Multidimensional Euclidean Space: Experimental Results
<p class="Abstract">Finding the diameter of a dataset in multidimensional Euclidean space is a well-established problem, with well-known algorithms. However, most of the algorithms found in the literature do not scale well with large values of data dimension, so the time complexity g...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ediciones Universidad de Salamanca
2018-12-01
|
| Series: | Advances in Distributed Computing and Artificial Intelligence Journal |
| Subjects: | |
| Online Access: | https://revistas.usal.es/index.php/2255-2863/article/view/18623 |
| _version_ | 1819010783732826112 |
|---|---|
| author | Ahmad HASSANAT |
| author_facet | Ahmad HASSANAT |
| author_sort | Ahmad HASSANAT |
| collection | DOAJ |
| description | <p class="Abstract">Finding the diameter of a dataset in multidimensional Euclidean space is a well-established problem, with well-known algorithms. However, most of the algorithms found in the literature do not scale well with large values of data dimension, so the time complexity grows exponentially in most cases, which makes these algorithms impractical. Therefore, we implemented 4 simple greedy algorithms to be used for approximating the diameter of a multidimensional dataset; these are based on minimum/maximum l2 norms, hill climbing search, Tabu search and Beam search approaches, respectively. The time complexity of the implemented algorithms is near-linear, as they scale near-linearly with data size and its dimensions. The results of the experiments (conducted on different machine learning data sets) prove the efficiency of the implemented algorithms and can therefore be recommended for finding the diameter to be used by different machine learning applications when needed.</p> |
| first_indexed | 2024-12-21T01:17:45Z |
| format | Article |
| id | doaj.art-8eb04b4175e64e9f96b8c88659e144a2 |
| institution | Directory Open Access Journal |
| issn | 2255-2863 |
| language | English |
| last_indexed | 2024-12-21T01:17:45Z |
| publishDate | 2018-12-01 |
| publisher | Ediciones Universidad de Salamanca |
| record_format | Article |
| series | Advances in Distributed Computing and Artificial Intelligence Journal |
| spelling | doaj.art-8eb04b4175e64e9f96b8c88659e144a22022-12-21T19:20:44ZengEdiciones Universidad de SalamancaAdvances in Distributed Computing and Artificial Intelligence Journal2255-28632018-12-0173153010.14201/ADCAIJ201873153016228Greedy Algorithms for Approximating the Diameter of Machine Learning Datasets in Multidimensional Euclidean Space: Experimental ResultsAhmad HASSANAT0Mutah University<p class="Abstract">Finding the diameter of a dataset in multidimensional Euclidean space is a well-established problem, with well-known algorithms. However, most of the algorithms found in the literature do not scale well with large values of data dimension, so the time complexity grows exponentially in most cases, which makes these algorithms impractical. Therefore, we implemented 4 simple greedy algorithms to be used for approximating the diameter of a multidimensional dataset; these are based on minimum/maximum l2 norms, hill climbing search, Tabu search and Beam search approaches, respectively. The time complexity of the implemented algorithms is near-linear, as they scale near-linearly with data size and its dimensions. The results of the experiments (conducted on different machine learning data sets) prove the efficiency of the implemented algorithms and can therefore be recommended for finding the diameter to be used by different machine learning applications when needed.</p>https://revistas.usal.es/index.php/2255-2863/article/view/18623furthest paircomputational geometryhill climbingtabu searchbeam search |
| spellingShingle | Ahmad HASSANAT Greedy Algorithms for Approximating the Diameter of Machine Learning Datasets in Multidimensional Euclidean Space: Experimental Results Advances in Distributed Computing and Artificial Intelligence Journal furthest pair computational geometry hill climbing tabu search beam search |
| title | Greedy Algorithms for Approximating the Diameter of Machine Learning Datasets in Multidimensional Euclidean Space: Experimental Results |
| title_full | Greedy Algorithms for Approximating the Diameter of Machine Learning Datasets in Multidimensional Euclidean Space: Experimental Results |
| title_fullStr | Greedy Algorithms for Approximating the Diameter of Machine Learning Datasets in Multidimensional Euclidean Space: Experimental Results |
| title_full_unstemmed | Greedy Algorithms for Approximating the Diameter of Machine Learning Datasets in Multidimensional Euclidean Space: Experimental Results |
| title_short | Greedy Algorithms for Approximating the Diameter of Machine Learning Datasets in Multidimensional Euclidean Space: Experimental Results |
| title_sort | greedy algorithms for approximating the diameter of machine learning datasets in multidimensional euclidean space experimental results |
| topic | furthest pair computational geometry hill climbing tabu search beam search |
| url | https://revistas.usal.es/index.php/2255-2863/article/view/18623 |
| work_keys_str_mv | AT ahmadhassanat greedyalgorithmsforapproximatingthediameterofmachinelearningdatasetsinmultidimensionaleuclideanspaceexperimentalresults |