Universal Method to Sort Complex Information Found
quantamagazine.org
Universal Method to Sort Complex Information Found
1–10 of 68 posts
Re: Universal Method to Sort Complex Information Found
#2The subtitle claims that a “universal way” was found to solve the nearest-neighbour-search problem for any kind of data, but actually the result is restricted to the (rather huge, of course) set of normed spaces, i.e. spaces whose distance measures obey the triangle inequality.
Re: Universal Method to Sort Complex Information Found
#3Ah that's so cool. I've been reading about expander graphs lately. Their interesting properties make them pertinent to lots of questions. In particular, you can use expander graphs to cook up error correcting codes and prove the PCP theorem. There's a class of expander graphs called Ramanujan graphs which are characterized by an analogue to the Riemann hypothesis involving a zeta function that counts the prime cycles in a graph.
Re: Universal Method to Sort Complex Information Found
#4The subtitle claims that a “universal way” was found to solve the nearest-neighbour-search problem for any kind of data, but actually the result is restricted to the (rather huge, of course) set of normed spaces, i.e. spaces whose distance measures obey the triangle inequality.
It's a rather large set, but it's got some noteworthy holes. Cosine distance, for example.
Re: Universal Method to Sort Complex Information Found
#5The subtitle claims that a “universal way” was found to solve the nearest-neighbour-search problem for any kind of data, but actually the result is restricted to the (rather huge, of course) set of normed spaces, i.e. spaces whose distance measures obey the triangle inequality.
Incidentally, the zone system for the Danish public transit system is not a metric space. (The ticket you need from A to B is not necessarily the same as from B to A.)
That's a kind of practical graph where you want efficient shortest path algorithms for.
Re: Universal Method to Sort Complex Information Found
#6I wonder what this can mean for fuzzing, optimization, learning or any kind of task that has to do with tip-toeing into potentially high dimensional spaces?
Re: Universal Method to Sort Complex Information Found
#7The subtitle claims that a “universal way” was found to solve the nearest-neighbour-search problem for any kind of data, but actually the result is restricted to the (rather huge, of course) set of normed spaces, i.e. spaces whose distance measures obey the triangle inequality.
Incidentally, the zone system for the Danish public transit system is not a metric space. (The ticket you need from A to B is not necessarily the same as from B to A.) That's a kind of practical graph where you want efficient shortest path algorithms for.
[deleted]
Re: Universal Method to Sort Complex Information Found
#8Curious to see Timothy Chan develop some screaming fast C code using their method.
Re: Universal Method to Sort Complex Information Found
#9The subtitle claims that a “universal way” was found to solve the nearest-neighbour-search problem for any kind of data, but actually the result is restricted to the (rather huge, of course) set of normed spaces, i.e. spaces whose distance measures obey the triangle inequality.
> spaces whose distance measures obey the triangle inequality
That would be a metric space, and a distance obey the triangle inequality by definition. The element of the space are otherwise quite arbitrary.
Unfortunately, Normed spaces are a subset of metric spaces which are much less general (in particular they have to be vector spaces).
Re: Universal Method to Sort Complex Information Found
#10The subtitle claims that a “universal way” was found to solve the nearest-neighbour-search problem for any kind of data, but actually the result is restricted to the (rather huge, of course) set of normed spaces, i.e. spaces whose distance measures obey the triangle inequality.
Incidentally, the zone system for the Danish public transit system is not a metric space. (The ticket you need from A to B is not necessarily the same as from B to A.) That's a kind of practical graph where you want efficient shortest path algorithms for.
Really?? Is that true only when there are multiple paths between A & B or is there something else involved?