SoylentNews

canopic jug [soylentnews.org] writes:

Quanta Magazine is covering a notable advancement in a well-studied computer science algorithm for sorting books or files or database contents or other similar physical or digital objects. The foundation is a 1981 study which was followed by a significant advancement in 2004 and just recently by reaches rather close to the theoretical ideal in the list labeling problem aka the library sorting problem: [quantamagazine.org]

Bender, Kuszmaul and others made an even bigger improvement with last year’s paper. They again broke the record, lowering the upper bound to (log n) times (log log n)³ — equivalent to (log n)^1.000…1. In other words, they came exceedingly close to the theoretical limit, the ultimate lower bound of log n.

Once again, their approach was non-smooth and randomized, but this time their algorithm relied on a limited degree of history dependence. It looked at past trends to plan for future events, but only up to a point. Suppose, for instance, you’ve been getting a lot of books by authors whose last name starts with N — Nabokov, Neruda, Ng. The algorithm extrapolates from that and assumes more are probably coming, so it’ll leave a little extra space in the N section. But reserving too much space could lead to trouble if a bunch of A-name authors start pouring in. “The way we made it a good thing was by being strategically random about how much history to look at when we make our decisions,” Bender said.

There are also significant implications for application as well.

Previously:
(2017) Google Algorithm Goes From Sorting Cat Pics to Analyzing DNA [soylentnews.org]
(2014) A Dating Site for Algorithms [soylentnews.org]
(2014) New Algorithm Simplifies the Categorization of Large Amount of Data [soylentnews.org]

Original Submission