Computer scientists have developed a new algorithm that significantly improves the organization of items in a list, minimizing insertion time. This 'library sorting' problem, which also applies to data storage, has plagued researchers for over 40 years. The new approach, presented at the Foundations of Computer Science conference, combines past usage data with controlled randomness, coming close to the theoretical ideal.
Computer scientists often deal with abstract problems that are hard to comprehend, but an exciting new algorithm matters to anyone who owns books and at least one shelf. The algorithm addresses something called the library sorting problem . The challenge is to devise a strategy for organizing books in some kind of sorted order—alphabetically, for instance—that minimizes how long it takes to place a new book on the shelf.
These results showed that for any smooth or deterministic algorithm, you could not achieve an average insertion time better than 2, which was the same as the upper bound established in the 1981 paper. In other words, to improve that upper bound, researchers would need to devise a different kind of algorithm. “If you’re going to do better, you have to be randomized and non-smooth,” said Michael Bender, a computer scientist at Stony Brook University.
ALGORITHM COMPUTER SCIENCE LIBRARY SORTING RANDOMNESS DATA STORAGE
United States Latest News, United States Headlines
Similar News:You can also read news stories similar to this one that we have collected from other news sources.
Estée Lauder's New Double Wear Concealer Solves Skin Concerns at Every AgeSamantha Holender is the Senior Beauty Editor at Marie Claire, where she reports on the best new launches, dives into the science behind skincare, and shares the breakdown on the latest and greatest trends in the beauty space.
Read more »
J. Cole Launches New ‘The Algorithm’ BlogThe Carolina rapper needed somewhere to post random things that he's currently into.
Read more »
Global internet grid could better detect earthquakes with new algorithmEarly detection of earthquakes could be vastly improved by tapping into the world's internet network with a groundbreaking new algorithm, researchers say.
Read more »
New AI Algorithm 'Torque Clustering' Mimics Natural Intelligence for Autonomous LearningResearchers at the University of Technology Sydney have developed a groundbreaking AI algorithm called Torque Clustering that significantly enhances unsupervised learning capabilities. Torque Clustering, inspired by the physical concept of torque, enables AI systems to independently analyze vast amounts of data and uncover patterns without human guidance. This new approach holds immense potential for various fields, including biology, chemistry, astronomy, psychology, finance, and medicine.
Read more »
This New Algorithm for Sorting Books or Files Is Close to PerfectionThe library sorting problem is used across computer science for organizing far more than just books. A new solution is less than a page-width away from the theoretical ideal.
Read more »
Your computer told us its New Year's resolutionAnd don’t worry, it’s cheaper than a gym membership
Read more »