Link (from the article) to the paper with details: https://www.ilyaraz.org/static/papers/spectral_gap.pdf
Universal Method to Sort Complex Information Found
11–20 of 68 posts
Re: Universal Method to Sort Complex Information Found
#12The 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.
The rail network in the UK is also strange. On some routes it is cheaper to split your journey across multiple tickets. On others it is cheaper to buy a ticket for a longer journey. However, this is illegal and the train companies do attempt prosecutions.
Re: Universal Method to Sort Complex Information Found
#13The 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.
my gut feeling tells me - ln((1+Similarity_cosine(A,B))/2) would satisfy the triangle inequality.
Re: Universal Method to Sort Complex Information Found
#14Link (from the article) to the paper with details: https://www.ilyaraz.org/static/papers/spectral_gap.pdf
The article announces the algorithm, which isn't published yet. This first paper contains the proof that the result is possible, not yet the efficient algoithm.
Re: Universal Method to Sort Complex Information Found
#15Earlier quoted context omitted.
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?
Other possibilities: Trains going in different directions don't make the same stops (express vs local), and time-based fares applying to a specific direction based on commuting patterns.
In the US, on Amtrak, a ticket is specific to an exact train, like buying a plane ticket. There's no generalized "I want a ticket from DC to NYC."
Re: Universal Method to Sort Complex Information Found
#16The 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.
[deleted]
Re: Universal Method to Sort Complex Information Found
#17Link (from the article) to the paper with details: https://www.ilyaraz.org/static/papers/spectral_gap.pdf
The article announces the algorithm, which isn't published yet. This first paper contains the proof that the result is possible, not yet the efficient algoithm.
I await this paper with eager anticipation.
Re: Universal Method to Sort Complex Information Found
#18Earlier quoted context omitted.
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.
The rail network in the UK is also strange. On some routes it is cheaper to split your journey across multiple tickets. On others it is cheaper to buy a ticket for a longer journey. However, this is illegal and the train companies do attempt prosecutions.
Why is it illegal and how do they enforce it?
I know that something similar happens with airplane tickets but they get you with the luggage and with terms & conditions AFAIK.
How is it similar/different with train tickets?
Re: Universal Method to Sort Complex Information Found
#19Link (from the article) to the paper with details: https://www.ilyaraz.org/static/papers/spectral_gap.pdf
The article announces the algorithm, which isn't published yet. This first paper contains the proof that the result is possible, not yet the efficient algoithm.
One assumes its an extension of their previous work (https://arxiv.org/pdf/1501.01062.pdf), which was only valid for Euclidian and Hamming spaces?
Edit: The author says its https://ilyaraz.org/static/papers/daher.pdf, but he got marked dead by HN.
Re: Universal Method to Sort Complex Information Found
#20Earlier quoted context omitted.
The article announces the algorithm, which isn't published yet. This first paper contains the proof that the result is possible, not yet the efficient algoithm.
I await this paper with eager anticipation.
This is the second paper, where we present an actual fast algorithm for general normed spaces: https://ilyaraz.org/static/papers/daher.pdf . Enjoy!