It's a nice idea, I quite like how it visualizes how bloom filters works!

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.

Apps are great until you have a dead phone or you lose it or you lose internet. I can see something like this being useful as an adjunct to the normal format: more skillful users can save time, less skillful users can use the old method.

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.

> more skillful users can save time

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.

For the main idea, basically, you get a small "fingerprint" of the stop you want to go to. Every train that comes has a "fingerprint" of all its stops overlaid. So you can immediately see if this train will take you to your stop by seeing whether all the bits of your fingerprint are displayed within the fingerprint of the train.

Likewise, 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).

I think optimizing for that O(1) lookup is the wrong optimization.

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.

I have even taken this strategy to a bit of an extreme for simple cases intentionally complicating switching in order to gain time or comfort.

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.

Public transit users in practice have some aversion to transfers.

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

What I detailed, I do in real life because I don't like waiting, because waiting in the station is far less comfortable than being in the vehicle and because timetables are reliable enough that I do not worry about missing a connection.

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.

It seems to me that the 0.5% false positive rate makes this unusable for practical purposes (since that would mean that 1 in 200 passengers gets on the wrong bus). How big would the sign need to be to have no false positives?

The parameters can be configured based upon system complexity etc. but there is always going to be some level of false positive. But that still may be okay if there are still those i x m x n lists posted around, one can quickly focus in on which lists are, let's say, 99.5% likely to be the relevant bus stop lists.

> there is always going to be some level of false positive

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.

Ah, a perfect bloom filter. https://www.researchgate.net/publication/260163952_Minimal_p...

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.

Maybe, but I think educating transit riders on how to use them correctly would be a major challenge.

Seems like the kind of thing that is great in theory but would end up with a high error rate in practice.

It also seems like it would actually be fairly difficult to explain to a majority of people, especially in a non-verbal way.

Technically, the lookup using O(1) since you need to find your fingerprint in a grid. I fail to see how that’s much faster than finding your stop in a list. Especially considering the false positives.

First, very cool project and a pretty novel idea to use bloom filters for this.

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.

Wondering if Emoji Sequences would be a more user-friendly approach for visualization.

I was wondering about emoji's too. That could work rather well. I think if you had a 2d array of like 200 unique emojis, with some subsection-ing of like, quartile, you could simply say, "If your train has a crocodile in the top left square, a star eyed in bottom right..."

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.

1. riders must not read signage in a given language or alphabet

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.

Thanks, I've added a note saying the video doesn't add new information. It's just a different avenue of explaining the idea. I think "modern art" isn't so far off the mark, but I'm hoping somebody smarter with more resources will adapt it or improve upon it in some way.

I mean to be fair, they're being used as symbols here so the fact that they're latin alphabet doesn't make a particularly big difference. Replacing the letters with very easily distinguishable non-language symbols would probably be better though.

At the very least, pick one case and stick with it, don’t mix upper and lower.

Really cool, but 0.5% false positive is pretty much totally unacceptable.

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.

In Germany, Google Maps is essentially useless for public transport. There is an app by Deutsche though Bahn which routes pretty much perfectly. Speaking of, I don't understand the problem this system would be solving, because you already get a list of platform numbers for your route

this feels like some hellish thing you would be faced with when you first try to use a bus in germany. so in that sense you have succeeded!

While not nessesary hellish to me, it is very very very German.

Das stimmt.

German buses are very straightforward in reality. Only issue is the risk of getting on in the wrong direction IME, but that’s really on you.

I’m not with the haters here, I think this is a very clever solution that encodes a lot of information concisely. Human beings have an amazing ability to understand symbology no matter how complex and while it might take a few days for folks to get used to it, once they do it’ll be simple and intuitive. I don’t buy the arguments here that it’s cryptic - labeling a bus M74 tells me nothing and is a totally opaque synthetic identifier that requires a lookup in a table i may not have. Knowing my destination symbol I can quickly ascertain from this scheme if this bus is one I want. Someone pointed out though that many lines can service the same stop and some are more optimal than others. So I think you need to encode some ordering somehow, which I know adds another element of information to encode.

While hypothetically useful if it were Harvard bus lines, grandma and disabled people won't be able to understand this.

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

I’m not sure this is a good comparison. Nix competes with a ton of other os, most of whom are established. If you had only nix, which most people agree is generally an excellent Unix distribution if a bit opaque, you would have an excellent Unix distribution that wouldn’t be opaque any more because everyone knows how to use it. The lack of choice in transit system labeling allows you to choose something that has a higher initial cognitive load but has a lower amortized load and/or provides superior information etc simply because people have no choice but climb the learning curve. And once it’s become part of a regional culture it ceases to have a learning curve at all and is simply superior to the alternatives (like nix)

Because disabled people don't go to Harvard?!

It's interesting, but I don't see any way it might be adopted.

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:

  From Osnabrück Hbf:

  ...

  Stendal Hbf: 06:04 IC2241*, 08:05 IC245**, 10:08 IC141, 12:08 IC143, 14:08 IC145, 16:08 IC147, 18:08 IC149. Plat. 11.

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

That's a good point. Because of this chaos, there would need to be a way to update track state etc.

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 :)

Honestly it took me longer than I would like to understand what I was looking at, that said once it made sense it's a neat idea. I know from experience though that your target audience is people who already understand it, getting this 'standard' will be very challenging to have mass public transport users adopt.

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 don't have plans. I'm not in a position as of now to even know what to do next.

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.

> riders must not read signage in a given language or alphabet

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…

I would love to understand this, but the readme seems to get ahead of itself. Can you frame the problem for 5 year olds who have never seen a bus stop (and who need to be reminded of what a bloom filter is)?

Cool idea in theory, but in practice you shift the cognitive load to the pattern recognition capabilities of the user, which might be even worse. The example fingerprints differ in just a couple cells, out of 48! What's worse, the general "shape" induced by the pattern is the same, they only differ in subtle details that cover small total area without changing the overall shape.

The visualization you provide is more appropriate for machine recognition, but for a human the difference is so subtle that the fingerprints are genuinely hard to tell apart. Making a mistake while distracted or tired will land you into a wrong bus.

You may want to dive into the cognitive science to construct a better visualization that relies on actual visual capabilities of humans, rather than on math. Start with the provable fundamentals of human perception, and answer the question - what exactly maximizes the visual difference between patterns? What exactly makes them obviously, strikingly different at the first glance? Color and value contrast, shapes, real life object resemblance, optical illusions, etc. This will also make the idea intuitively apparent to the user, without having to explain it.

Be aware that these questions are not easy to answer; it's a rabbit hole which goes down to the Earth core.

Visual complexity is also a thing, and bandwidth as well. You can only fit so much bits of information into the pattern, even if your mapping between the underlying logic and the presentation fits human perception perfectly.

It’s a fun idea but the system would probably be impenetrable to most riders. Wouldn’t it make more sense to base it on a map? A map of lines and stops already gives you a pretty good birds-eye view of where you can go from a particular stop, but perhaps there are ways to make it faster to recognize a particular stop. So for example, your bloom filter visualization could be applied to a certain geographic region, and would only need to cover stops in that area.

But this will only work if you already know route on which you are travelling and somewhat memorized patterns which occur there. For people non famililiar with this this is useless gibberish.

Also I find it more hard to navigate trought list with (for me) meaningless alphabet. It gives me vibes of being in China and not able to read what's on the signs.

Neat! I also used a bloom filter as a temporal spatial index, different problem but the property that they can be merged into a tree is very nice.

Could be used as an overlay for augmented reality glasses.

If we are bringing in AR glasses in the mix, there's no need for the bloom filter. Just highlight the relevant bus if its the one for you. Let the computer handle the mental load of matching schedules.

Just to make it clear, the motivation for this is when you're running to your stop, which might have many different platforms or maybe platforms for different lines just a block a part (I'm thinking downtown Essen), and trains are already arriving. You don't have time to check every platform individually before your tram is already leaving.

As I said in a different comment, I think this is simply the wrong optimization.

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.

I live in India. Here all public transport is already shown on Google maps. Just enter where you want to go and select public transport, it'll show you everything like buses and metro with ETA for everything. It takes care of switching bus stops or train lines. Nice concept, but no. I'm not going to be using this.

While the idea is nice for encoding routes, there is a cognitive overload in trying to decipher/comprehend that.

As an example of an alternative, I found the London Tube map much more intuitive to follow for humans. Colored lines with list of stops along the way and transfer points where you could switch to another line.

For what it's worth, stations in London and bus shelters have similar maps for buses, showing a network.

https://content.tfl.gov.uk/bus-route-maps/fulham-and-putney-... (if you see this map, you will be at one of the red circles on the real bit of the map.)

Bus stops have similar maps showing only buses from that stop.

https://skyscraperpage.com/forum/showthread.php?t=178402&pag...

i mean i assume if you gated things by city, the i x m x n isn't that high that you cant do a naive inefficient implementation rather than using bloom filters. but hey whatever rocks your boat! would be better if you had a live/standing service so pple can try it out

is it O(n) for those lists/posters or O(log n)? they're usually sorted, aren't they?

I don't know about Germany, but sometimes they are sorted in the order they are visited by a bus (describing the route), not alphabetically. Which makes it harder (O(n)) if you know the name, but don't know where it is located on the route.

Listing them alphabetically would be closer to this approach though, and likely more accessible.

That's a very cool idea. Thanks for the blog, it's well written. I love how you've applied the idea of a hashmap to a 2d foam board. I'm on the verge of having a breakthrough of improving my visualization but so far it hasn't arrived. If you think of anything feel free to let me know.

I don't understand the advantage of this system. If you have to look up the "seed" of the route, why not just look it up on DB and get the platform number for every stop?

I feel like this is a cool idea for a way to visually communicate information that just needs the right application. Seems like it would be a great videogame mechanic (like some sort of hacking or lockpicking minigame)

The idea has something - and I'm surprised how fast visually scanning for the pattern actually is (once you got the principle).

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/

in Paris they created a overview bus map which in each node lists all bus lines passing through this node. if your source and target list the same number just take that one.

it folded out to A4

and that is all I've ever needed to get around by bus in Paris. and I was missing similar bus maps in Berlin and in London.

that said I'd love to see some usability feedback on the bloom filter proposal. my intuition is that it's too esoteric, i.e. only for the few who get it.

If vim users designed bus signage...

Yes I am a vim user

So we are working on very similar things. Here is a WIP re-working of the NYC subway nomenclature. Line coloring, names, and service labels organized into meaningful patterns.

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