Jove
Visualize
Contact Us

Related Experiment Videos

Sorting with self-organizing maps

M Budinich1

  • 1INFN, Trieste, Italy.

Neural Computation
|November 1, 1995
PubMed
Summary

Self-organizing feature maps sort numbers in linear time O(n) by leveraging data distribution. However, certain data distributions can lead to quadratic O(n^2) sorting time, revealing an emergent sorting algorithm.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

RadioLab project: knowledge of radon gas in Italy.

Scientific reports·2024
Same author

Adaptive calibration of imaging array detectors.

Neural computation·1999
Same author

A self-organizing neural network for the traveling salesman problem that is competitive with simulated annealing.

Neural computation·1996
See all related articles
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Area of Science:

  • Computational Neuroscience
  • Machine Learning
  • Algorithm Analysis

Background:

  • Self-organizing feature maps (SOFMs) are unsupervised neural networks.
  • SOFMs are known for their ability to perform dimensionality reduction and clustering.
  • Their computational complexity for sorting tasks has not been fully explored.

Purpose of the Study:

  • To analyze the time complexity of sorting real numbers using a self-organizing feature map.
  • To investigate the conditions under which SOFMs achieve linear time sorting.
  • To identify potential performance limitations and pathological cases.

Main Methods:

  • Theoretical analysis of the self-organizing feature map algorithm.
  • Examination of sorting time complexity based on input data distribution.
  • Identification of worst-case scenarios for sorting performance.

Main Results:

  • Self-organizing feature maps can sort n real numbers in O(n) time under uniform data distribution.
  • This linear time performance appears to violate the theoretical O(n log n) sorting bound.
  • Pathological data distributions can result in O(n^2) sorting time, though these are exponentially rare.

Conclusions:

  • The learning process in SOFMs can result in efficient, emergent sorting algorithms.
  • Performance is highly dependent on input data distribution.
  • SOFMs offer a unique approach to sorting with potential advantages in specific data scenarios.

Related Experiment Videos