Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Universal Method to Sort Complex Information Found

quantamagazine.org

Post reply on HN
Print view View original

61–68 of 68 posts

Re: Universal Method to Sort Complex Information Found

#61

Post by ZeikJT »

sshine wrote: post #42
gumby wrote: post #10

Earlier quoted context omitted.

Really?? Is that true only when there are multiple paths between A & B or is there something else involved?

For busses, the B stop on the way out may be in another zone as the B stop on the way back because they're geographically displaced. For busses and trains, depending on your type of ticket (2-8 zones, 8+ zones, commuter card) and whether the zone intersection is on or between stops/stations, you may have to pay for that zone one way but not the other. Those are edge cases. But the most confusing part is the ring topo…

What the... that was painful to read and comprehend. Was this kind of complexity really necessary? Did someone get a promotion for coming up with this?

Re: Universal Method to Sort Complex Information Found

#62

Post by exikyut »

DonaldFisk wrote: post #31
buckminster wrote: post #27

Earlier quoted context omitted.

It is illegal because the railway byelaws make it illegal. The railway doesn't just have its own law, it also has its own police force, The British Transport Police, though as far as I know they don't do the ticket enforcement. You are not allowed to break a journey either, so a ticket inspector can spot a ticket for a longer journey at one end of the other. The multiple tickets ruse is more of a grey area.

BREAK OF JOURNEY Rules vary by train company and route. In general you cannot break your outward journey (except for necessary changes of train) but you can break your return journey. Source: https://www.splityourticket.co.uk/info/fare-types.aspx I've already dealt with the legality of split ticketing in another post.

Huh. I wonder if it would be cheaper to do a ticket like

start -> actual destination (stay on train) -> overshoot destination (get off) (get back on) -> (turn around; begin return trip) -> actual destination (get off) (get back on) -> start

?

Seems utterly unintuitive, and it probably is, but I am curious.

Re: Universal Method to Sort Complex Information Found

#63

Post by mikhailfranco »

hinkley wrote: post #26

> For example, “Manhattan” distance forces you to make 90-degree turns, as if you were walking on a street grid. Using Manhattan distance, a point 5 miles away as the crow flies might require you to go across town for 3 miles and then uptown another 4 miles. It's interesting that this is called Manhattan distance because it's only relevant in a town where everyone jaywalks... Like Manhattan. It's far from true anywhe…

Yes, this is the value of optionality, as N.N.Taleb would say.

I had exactly the same thought about crossing streets when reading one of his books. Always choose a route where you have the choice to keep walking in some direction towards your destination, with a delayed jaywalk to cross to the side you want during a gap in traffic, rather than wait on a corner when a crossing is blocked. The reason for blockage can be a crosswalk light (if you obey them) or traffic itself - the rule applies even without any signal-controlled junctions.

Re: Universal Method to Sort Complex Information Found

#64

Post by curious1212 »

thesasho wrote: post #51
macleginn wrote: post #2

The 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.

The method gives a data structure for any metric space, and the quality of the data structure is controlled by how well expanders embed in the metric space. This implies interesting results for metrics which are not norms, like geodesics on certain manifolds. The surprise to us was how well this approach works for any norm, however. (I am one of the authors.) Also, a math correction: spaces which obey the triangle in…

I don't think the general property of expander graphs is needed, perhaps a relaxed property, such as the following definition:

A graph G is a distance(k)-expander if #edges(U, V-U) > c min(#U,#(V-U)) where U is a set of diameter I am also curious about what happens if one use SVM to classify vertices of an expander graph: Let G be an expander graph and let u1,u2 be vertices of G such that d(u1,u2) = diameter of G = an even number 2k. We classify the vertices of G like this: f(u) = 0 if d(u,u1)=1, then using SVM applied to the vertices encoded by the rows of the adjancecy matrix. I would expect the SVM algorith to have some special property but I don't know what to expect, the best or worst classification, or the support vectors can gives us some information about symmetries in the graph.

Re: Universal Method to Sort Complex Information Found

#65

Post by sshine »

ZeikJT wrote: post #61
sshine wrote: post #42

Earlier quoted context omitted.

For busses, the B stop on the way out may be in another zone as the B stop on the way back because they're geographically displaced. For busses and trains, depending on your type of ticket (2-8 zones, 8+ zones, commuter card) and whether the zone intersection is on or between stops/stations, you may have to pay for that zone one way but not the other. Those are edge cases. But the most confusing part is the ring topo…

What the... that was painful to read and comprehend. Was this kind of complexity really necessary? Did someone get a promotion for coming up with this?

I copied and translated a quite limited subset of the official traveller guidelines.

There are several reasons why it ended up like this, and I don't know all of them.

But two reasons I can think of:

1) With the introduction of RFID-based commuter cards, the zone system was revised for traditional ticket types as well. It appears convenient that a price can always be determined by knowing the check-in point, the check-out point and the shortest path in the graph. Unfortunately, with the old ticket types, you have to perform the calculation instead.

2) It is the odd shape of zone 2 that causes some tickets to not work on the way back, even though the trip goes in a straight line. But for a large part of all trips, you only need zone 1 and 2, or zone 2 and zone (30, 31, 32, 33). Only the ones that start in zone 2, go through zone 1, go back into zone 2 and farther into another zone (or vice versa) have the anomaly. (Trips that actually bend can have this too, but it is slightly more intuitive.)

Re: Universal Method to Sort Complex Information Found

#66

Post by ColinWright »

DonaldFisk wrote: post #28
buckminster wrote: post #12

Earlier quoted context omitted.

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.

It's legal: https://www.telegraph.co.uk/money/consumer-affairs/fare-spli... https://www.bbc.co.uk/news/uk-england-19217111 and there are web sites which do split ticketing: http://www.raileasy.co.uk/home/split-ticketing/ http://www.splitticketing.co.uk https://www.splityourticket.co.uk

To be clearer, splitting tickets is legal, and while the second ticket may become invalid if the first train runs late, train companies now honour the second ticket if the reason you miss your train is because the incoming train has run late.

However, what can be in breach of the terms and conditions is to buy a ticket for a longer journey than desired and then get off at an intermediate station. If you read the comment to which you're replying, it's the "overlength ticket" that he is saying can be illegal.

Re: Universal Method to Sort Complex Information Found

#67

Post by ColinWright »

DonaldFisk wrote: post #31
buckminster wrote: post #27

Earlier quoted context omitted.

It is illegal because the railway byelaws make it illegal. The railway doesn't just have its own law, it also has its own police force, The British Transport Police, though as far as I know they don't do the ticket enforcement. You are not allowed to break a journey either, so a ticket inspector can spot a ticket for a longer journey at one end of the other. The multiple tickets ruse is more of a grey area.

BREAK OF JOURNEY Rules vary by train company and route. In general you cannot break your outward journey (except for necessary changes of train) but you can break your return journey. Source: https://www.splityourticket.co.uk/info/fare-types.aspx I've already dealt with the legality of split ticketing in another post.

The National Conditions of Carriage actually permit breaking an outbound journey, provided the ticket remains valid for the continuation. Outbound tickets are usually only valid on the day, so in that case you can't continue the journey the next day. But a regular standard (or first-class) ticket on a train that's not the last train of the day can be broken on the outbound journey.

For most tickets.

Some tickets, such as Advance and some Super-Off-Peak, have additional conditions. However, I do have a letter from a train company saying that they were wrong to have charged for an extra ticket, and wrong to have tried to start proceedings.

So breaking an outbound journey can be legal, and in such cases buying an over-length ticket is possible. It's circumstances like these that led in part to some of the specifics of the recent shake-up of the fare structures.

Re: Universal Method to Sort Complex Information Found

#68

Post by ColinWright »

exikyut wrote: post #62
DonaldFisk wrote: post #31

Earlier quoted context omitted.

BREAK OF JOURNEY Rules vary by train company and route. In general you cannot break your outward journey (except for necessary changes of train) but you can break your return journey. Source: https://www.splityourticket.co.uk/info/fare-types.aspx I've already dealt with the legality of split ticketing in another post.

Huh. I wonder if it would be cheaper to do a ticket like start -> actual destination (stay on train) -> overshoot destination (get off) (get back on) -> (turn around; begin return trip) -> actual destination (get off) (get back on) -> start ? Seems utterly unintuitive, and it probably is, but I am curious.

That can be possible, and I have done it.

Part of the reason for all this is that the train system has been broken up into a collection of franchises. Some companies will then incentivise some journeys, and so the fare doesn't always reflect the time or distance of the journey being made. As a result you can find and exploit anomalies, but only if you're willing to spend the (sometimes considerable) time and effort.

Post reply on HN