Show HN: Public transportation signage based on bloom filters (rough mockup) (github.com)
Hello,
I was running around Germany, hectically navigating public transportation, and getting lost all the time. I noticed that every station had i platforms, each used lists of n buses (trains, whatever) arriving, each has their list of m destinations. That means I would be scanning i x n x m items just to see if I was at the correct stop. As I was nervous, for every bus that arrived, I would rescan the list of stops to double check. I began thinking how I could make a better system.
Linked is a very shoddy mockup of how bloom filters could be used to allow passengers O(1) lookup time for which platform+bus is the correct one. I believe it's likely for public transportation to grow increasingly more complex in the future, as population grows, and under the current list-based system, this will make the signage ever more complex. I think some bloom filter mechanism could reduce that complexity.
So, here is my fantasy, my day dream. What do you think?
66 comments
[ 4.8 ms ] story [ 111 ms ] threadLikewise, you can tell if waiting at a bus-stop will bring a bus that will take you to your destination, by overlaying all of the busses' fingerprints together. If any bit of your destination fingerprint is missing from any train or station, then this train/station is irrelevant to getting you to where you want to go.
Thus lookup is now O(1).
That's not necessarily true. Even if you're dealing with a large number of stops, routes generally aren't changing very frequently. This means you can afford to spend some time tweaking the output to get the false positive rate down to zero.
This isn't strictly a Bloom filter anymore, but I think any level of false positive makes this a non-starter. I can't imagine any transit agency would knowingly to put up signs that will misdirect customers.
Low accuracy filters could still be useful if they are small enough, and paired with the raw table. Maybe you could get 93% true negative rate with just a 5x7 grid.
There's some paper discussing how high dimensional parameters can be visualized with human faces, because aspects of the face are quickly identified by humans. I think they used ideas such as, How far the eyebrows are apart etc. Maybe making (disfigured) human faces with binary features would be easier to parse too.
In any case, what I've come up with is well below optimal. I'm not sure I even need the number of bits I've included, but I show them as some kind of worst case.
Someone who knows the target station well most probably already knows what arrives in the target station and therefore is not helped by this. Someone who only knows the name of the destination, probably needs routing assistance from a person or from an app. The lookup of the platform is probably not the difficult part. Also this gets more complicated if different vehicles have different speeds, different journey lengths to the destination and different price ranges.
Also, this method only applies to traveling from A to D with only 1 vehicle. If you ever change vehicles at B, or get off at B then walk to C then get on a different vehicle towards D, or if traveling to E instead of D is just as good an option, then this kind of signage does not help.
I do not know about Germany, but I have not yet encountered issues finding the right platform.
Also, where I am from, ever since ticketing changed from 1 ticket/trip to 1 ticket/x amount of time, my use of transportation changed. I simply get on the first vehicle that brings me closer to my destination and take care to maximize my options of switching. For such a thing I need a map with all the lines and all the stations and the assumption that arrivals are so closely spaced that waiting does not matter.
If I need to optimize temporally due to waiting times I am just going to use an app and choose one of the suggested routes.
Let's assume:
- I want to get from B to G.
- Line 1 goes A-B-C-D-E-F-G-H. It is an obvious choice.
- Line 2 goes -A-B-C-D-K-. Line 3 goes -I-C-D-E-O-. Line 4 goes -J-D-E-F-M-. Line 5 goes -L-F-G-N-.
I might choose to take 2->D,3->E,4->F,5->G just because it is quicker because line 1 would have a longer waiting time. Or I might even choose to take 2->D,3->E,4->F,1->G (at the end taking the original line 1 that would have taken me the entire journey, therefore not saving any time) because it is too cold or too hot and I prefer to wait 4 shorter periods instead of one continuous long period.
Things get more complicated when routes diverge and converge and when taking timing into account.
For creating such combos the system you proposed would not help but a map does.
* people don’t like waiting, and often perceive waits as longer than they actually are, particularly if they’re uncomfortable
* a scheduled connection is one thing, but missing a connection is stressful, and compounds the first factor
* people are lazy and like being comfortable. If I get a seat on the first bus I take, do I want to give it up and potentially be forced to stand on the second one?
Various places model this differently, but IIRC the most “friendly” transit planning model in North America assumes 1 minute of connection to be equivalent to 1.75 minutes of motion time.
Besides, in the simple linear example I have given , it is impossible to miss the direct connection. It either catches up to me in which case I just take the direct connection when it does (and as a result I split my waiting time into shorter periods) or I arrive to the destination before the direct connection does (therefore saving time).
> If I get a seat on the first bus I take, do I want to give it up and potentially be forced to stand on the second one
This is never a scenario. I never get off a bus that takes me to my destination. I get off a bus when it no longer goes in the desired direction. I get ON the first bus that goes in the desired direction even if it doesn't reach the destination. If the first bus to arrive is the direct connection, I take it of course, and no longer bother with a combo.
Compared to when tickets were per ride so combos were disincentivized, I vastly prefer the current system and I do these combos almost on a daily basis.
An unreliable transportation system results in aversion to transfers. That is not the case in the cities relevant for me. Transportation is reliable enough that transfers are an opportunity for optimization instead of being something to avoid.
Sometimes I even ended up missing the initial bus at the starting point that would normally be the last direct connection with my destination before a critical time point, but I manage to still make it in time by doing a combo instead.
Someone already brought up the false positive rate, which I could see getting down to zero, but is route optimization able to be a factor? The problem I'm thinking of is if Route A takes 10 minutes but Route B has additional stops (or a longer trip) and takes 20. If I'm getting around by bus I probably won't want to be operating on larger and larger time windows the more I take public transportation, especially as it scales.
Could be used as an overlay for augmented reality glasses.
But will have to read a manual in a language they understand on how to read signage.
Confused tourists who doesn’t speak German looking at sign in utter confusion…
The existing directions are "From Osnabrück Hbf platform 11, take train IC2241, IC245, IC141, IC143, IC145, IC147 or IC149 with the direction 'Berlin Hbf'". The old timetables (not sure if these are still present in German stations) would give information like this:
(I have made up the * and **, which might annotate things like "Mon-Fri only".)Given a current time of 16:00, that becomes "From Osnabrück Hbf platform 11, take train IC 147" or "the 16:08 train from platform 11".
The platform number is useful, as they're almost always numbered and signed in order. Once there, matching "IC 147" or "16:08" is easier and more reliable for most people than a collection of shapes and symbols.
You will note that in the 1990s, it was perfectly reasonable to give an 11 year old the directions "take the train from platform 9¾ at 11:00".
Edit: I'm mixed up. German stations seem to have the backward timetable (ordered by time, so I can arrive at the station at 16:00 and can see where I could go). The easy improvement is to format them like the British do.
British stations have an indexed timetable. Every directly-connected station is listed in alphabetical order, the trains listed by departure time. If appropriate, important towns needing a connection will also be listed.
Here's a general image: https://www.alamy.com/stock-image-national-rail-notice-board...
And here's a higher resolution part of a different one: https://www.alamy.com/stock-photo-uk-railway-train-timetable...
Even works at the largest stations: https://www.alamy.com/paddington-railway-station-london-uk-w...
Either my implementation would need high-res displays showing current bloom filter data, or there would have to be interns running big printed paper posters all around showing "updates"
EDIT: I misread your comment. The chaos I was referring to was that trains change which platforms that they land on, and the same trains at different times/days may go to different places.
The British way does sound like a cheap improvement. Very obvious, I can't help but laugh. Thanks for the comment :)
In practice it is probably a bit too complicated to be used - especially once you take into account things like routing (you can either travel A-B-D or A-C-D) and indirect lines (One line goes A-B, another goes A-C-D-E-F-G-B. You obviously would prefer the second).
In my experience, the problem has mostly been solved by public transport apps, which simply provide you with an itinerary. For example:
Option 1: At 13:14, take bus 5 heading to Hauptbahnhof. At 13:45, take the train with destination Berlin-Spandau departing from platform 3 until it arrives at Sudkreuz. At 14:15, take bus 30 heading towards Tempelhof departing from stop A until you reach Paradestrasse.
Option 2: At 13:20, take bus 6 heading to Hauptbahnhof. At 13:45, ....
Combine that with a neat little GUI and there is zero thinking involved. No need to care about timetables and destinations, just follow the instructions to the letter. It can even auto-update when there are delays if the vehicles have GPS trackers.
However it is a big investment to change all the signs and public utilities are not known for sophistication, so it will never become a reality.
I think more skilful users already get by quite fine even with the current system – I never felt lost or had difficulties the way the OP described, even when travelling outside of my hometown.
I think this could be really useful for visually impaired people. Just imagine, that instead of colors and letters you'd have unique shapes or to keep it simple something like a raster with holes. Every bus stop could have one of those raster plates while the people would have a sort of "key", designed to fit in "their bus".
I came up with a very similar approach to explain HyperLogLog a while ago and see some parallels.
Have a look at the (yet very ugly) illustrations I made a while ago: https://geo.rocks/post/hyperloglog-simply-explained/
I guess the key/lock principle is very similar to both, bloom filter and HyperLogLog and could yield other benefits as well, like counting distinct buses passing a stop and map them for city. In this way, one could easily create a heat map of the cities best- and worst-served areas.
it's literally in a specific alphabet. If you were an Arabic speaker these letters would be just as much gibberish to you as Arabic letters would be to an English speaker. Not just gibberish, but hard to tell apart.
2. very quick to see where you need to be and which bus you should board
I watched the video to just to be sure i wasn't missing something but... no. So very much _no_. I assume that to _you_ this is clear. To me this is modern art. I think if you explained it to 10 non-geeks you'd get... 10 people saying "no, this is not fast or easy" maybe with sufficient training, but even if you got 100% adoption amongst locals any foreigner passing through would be absolutely screwed.
However, the visual appearance of it right now is daunting. Keep in mind, people are already overwhelmed by a map with hexagons [1] - I think the chances are slim they will want to engage with a complicated grid full of cryptic letters and symbols (unless they already work in IT or public administration).
I think at the very least, you'd have to style it in a way that makes clear that the graphic as a whole is a visual indicator - and that you don't have to make sense of each individual symbol or letter.
I'm just wildly guessing here, but I'd get rid of the letters and only use shapes or symbols to prevent confusion with footnotes. Also you could give the entire thing a recognizable shape, e.g. use concentric circles with segments instead of a grid.
A graphical designer would probably have better ideas how to approach this.
The biggest problem I see is that the way bloom filters work doesn't match the intuition of how to use this signage and misuse could easily lead to confusion and disappointment:
If I'm a traveler scanning for my fingerprint, I'd expect that if I found the fingerprint on some bus or platform then I could trust that this is the way to my destination. However, that's not what bloom filters do: They only guarantee that if you don't see the fingerprint, then that way definitely won't lead to your destination - but they can easily produce false positives, where your fingerprint is present in the signage, but the bus will still be the wrong one.
So imagine you're some traveller, already stressed out and trying to understand an unfamiliar system. You've actually wrapped your head around the system and have finally found your fingerprint - on a bus, which is about to depart, so you jump on it in the last minute with no time to double-check the destinations. You're glad you made it, until you realize that it's in fact the wrong bus, even though the fingerprint said it was the "right" bus. You have never studied CS and have no idea what a bloom filter is, so you're just confused and angry that someone must have put up the wrong sign - and probably not inclined to use the system again for the remainder of the trip.
Edit: Overlooked that you already mentioned the 0.5% false positive rate. I'd agree with the other posters though, that probably no false positives are acceptable here.
[1] https://www.vrminfo.de/fahrkarten/tarif/tarifwabenplan/
I do have some concerns too about the failure rate, although I haven't quite figured out how you're actually calculating that, still going through it. But seems worrying, do you have some plans to address it in the future ?
I meant it as a proof of concept. If an industrial player would like to experiment with an easy to use variation, i would be thrilled, but i don't have the tools.
While it maybe efficient like Haskell or Nix, the popularity potential of it is impaired by being too abstract for enough people to reason about it easily.
https://en.wikipedia.org/wiki/Worse_is_better
When you are running to your stop you better know already what train you want to take. Plan the route then go to the platform instead of get to the platform and panic about what train to take.
I never ever had to "check every platform individually" and this was never something that took any time because this was never an action. The flow was always, decide on a route(choose train)->buy tickets if needed->get to the station->check the central announcement panel for platform corresponding to train number->get to platform->get on train. The choice was already made in the first step. The only difference before the internet existed was that ticket purchase was done after getting to the station. The choice of train was still done ahead of time using the train book or the train information telephone line.
https://i.imgur.com/UNAT0ZV.png
To fill in some blanks, I am using information channels in a very similar way to your bloom filters. I divide the type of information into the type of visual indicator. Colors are for the broad outline of route, names are for specific route, shapes are for stopping pattern information (express or local). Eg A train going from the Bronx down to Coney Island would have to be in the red-brown palate, its name would be a two digit number with the second digit <5, and depending on if it skips over any segments (indicated dotted lines) it would either have a <> label or a [] label.
I had thought about your "fingerprint" idea. In fact I almost came on it accidentally when outlines of labels in my table changed but the interior didn't. I figured having two colors, a major one for the general palate and then an outline for further specifying, would solve a ton of encoding issues. But ultimately I rejected that idea because I found it too confusing to be able to lookup in either direction (from seeing train to knowing map AND from seeing map to knowing train). It became unclear to me where I should be matching the interior color to a line and where I should be matching the outline color to a line. It was too hard to follow.
The major advantage of colors is that you don't have to mentally trace the whole line on the map to figure out where a service goes. Its very quick to see that the red line which started at X must be the same one you glimpse latter at Y.
To my estimation, you can encode at most 4 bits on colors (1 bit RGB + dark/light), Perhaps 2 bits on shape (circle, triangle, square, diamond), and the rest has to go on to the name. So, reasonably, at a glance your labels can tell people 6 bits of information. Organize it by most significant bit first. If you could only tell me one bit of information about a bus service, which bit would it be? Color that first bit of difference with red / green. Then look for your next bit. For my map, the very first bit was either turns right around 50th St into Queens or keeps going north towards the Bronx. At first I colored everything in these two categories, and when I was done I was left with a handful of lines that all had Broadway Junction in common. Those became the blue pallate in my map. Sometimes, as you start to fill it in, the underlying symmetries of the transit system pop out at you and the amount of complexity seemingly evaporates. A good map should per-generate this insight on behalf of the readers. You are on the right path.
I'd love to talk at length but this is all the length I can afford right now. So here's is my take away message for you.
192 bits is way more bandwidth than you can reasonably hope to communicate in the service label. Look closely at the map of services and figure out the most important 3 or 4 bits, then communicate that. Stick to one color per label, possibly with black or white outlines/fills to encode more information. Be consistent, one type of information gets one type of encoding. A shape is not just an additional color for design purposes.
Edit: I dug up my old comment ranting about my map if you want to read more. https://news.ycombinator.com/item?id=34666190
Listing them alphabetically would be closer to this approach though, and likely more accessible.
Why not just list every destination in one list, with the list of busses and platforms for each one, as in:
Hoxton Center(287 P1, 76 P4)
Allowing one to then go straight to P1 and P4 and find the times for 287 and 76?
Ultimately this kind of this is easily done by computers though, Google Maps routing is usually great although it's occasionally possible to find a better route than them if you know one bus is always off schedule (I'm in the US).
They could have AI powered voice assistant kiosks for phoneless people, you could walk up and say "How to I get to Mornington Crescent" and it would tell you, or they could just hire attendants with tablets if such things were within budget.