Bus Stop Bloom Filter

Imagine you’re sitting on a nice bench, the sun shines warmly, and a bus pulls up. You’re headed to Stendal from Osnabrück, how can you tell if you should get on that bus? [Julian Vanecek] is trying to turn that from an O(n) problem to an O(1) one with a Bloom filter right at the bus stop.

In [Julian’s] sample code, each stop is a 3-bit number that can be encoded into a 192-bit array. Your ticket is just that 3-bit number encoded, so you can look at the graphic on the side of the incoming bus, match it against your ticket, and hop on. Gone are the days of waiting for the little LED screen to cycle through all the stops, waiting for yours to come up. Your ticket should have just a few boxes filled in so it is relatively quick to search against the bus’s graphic.

Of course, there is a potential for a false positive rate. [Julian] points out that this can be tuned to prevent errors and has achieved a < 0.5% false positive rate using the Deutsche Bahn bus system. The code is written in Python and available on GitHub. Perhaps buses could have a large flip-dop display on the side, to adjust to show which stops they’re headed to next. Additionally, it doesn’t encode which stops are next, just which stops the bus will eventually go to.

In the video after the break, [Julian] explains how the system works. Whether it would be ultimately adopted is somewhat beside the point. We love the seeing people re-imagining ideas and trying to apply new techniques to improve the things around them.

19 thoughts on “Bus Stop Bloom Filter

  1. Whats wrong with the line number on the front of the bus? If you have a bus stop with multiple lines stopping there, they have a map with all the line numbers so you see wich ones could go your way.

    The front of the bus is the best way to put the signs anyway as that part of the bus is visible the longest time. If you have to look at the side, you are too late already and the bus is leaving.

    Changing a single number in a simgle color scheme ( with the end of the line destination) to a supermarket isle of multicolored chaos is not an improvement, unless you are a member of the League of Incognito Sadists (LIS) who try to make hell on earth.

    Nice try, but no thanks.

    1. “Whats wrong with the line number on the front of the bus?”

      Nothing… but that’s beside the point and it was more of a thought experiment. You have taken this idea way too seriously.

        1. The horror! We need to prevent that and stop spreading new ideas, they should be tightly controlled and only a select group with proper licenses should be allowed to use them.

    2. Don’t let the pundits discourage you. I see a glimmer of utility in your research. Keep on plugging! What concerns me about this specific embodiment is the limits of human cognition and it’s impact on *usability.* The good news is, while a sudoku-style grid of emojis might confound me and other humans, it is a no-brainer for the camera+AI in your phone. So maybe the superpower of your technique is to make a machine-mediated solution more viable (cheaper, faster, scalable). With your smart phone in-hand and a bar code on each vehicle, you could quickly confirm which bus to get on without your brain straining to puzzle-out patterns of dots, stripes, and smileys -or- taxing expensive cloud servers and wireless networks simultaneously when a million commuters in your mega-metropolis all want to know at 3:10 one fine afternoon: am I getting on the right train?

      1. If a person has to use their cell telephone to tell if a stop or bus is the correct one why not use a Bluetooth beacon instead? This wouldn’t require any action on the part of the user for each arriving bus.

  2. There are many problems with many public transportation networks, and for me, the biggest one is the lack of standardization of information channels and real time information.

    – There are many existing technologies, such as GTFS, but strangely, public transportation agencies haven been reluctant to adopt them and to publish their schedules using this method. I don’t know why, since almost everyone has a smartphone.

    – Strangely, public transportation agencies insists in reinventing their own service with their own API and buggy apps over and over again. Ugh!

    – In my city, you’re required to go to the driver and get a ticket, regardless if you have a travel card or if you’re paying with cash. This is stupid and greatly increases stop times by at least 2 extra minutes, which really adds up to the end of the day. You can easily fit one or two extra round trips per line (thus improving the service) if you allow people to validate their ticket on an onboard machine.

  3. They stopped using tickets here in Washington. They have a card system. ORCA cards.
    At the stop, there is a list of what busses stop there, and the times they stop there along with the bus destination. It’s just a matter of waiting for the number of the bus you want. As you ride the bus, the bus itself indicates the next upcoming stop. You pull the cord, the bus indicates “STOP REQUEST”.
    The driver stops and you disembark.

  4. Lol WTF? Do people just show up at a bus stop, any bus stop, and then get on a random bus and expect it to somehow get them where they are going!? Then get confused as to why this doesn’t work? And this happens over and over? I guess I’m glad they aren’t driving cars holy cow.

    1. Nope, but sometimes finding a proper bus stop (one of 20) in a cluster of buildings interconnected by different walkways is pretty hard. Having such system which tells you if this walkway will bring you closer to your bus stop could be a godsend. Alternative is a clear directions system which as we know seems impossible for transit companies.

  5. Oh dear. The opportunities for this to go horribly wrong are manyfold. People with impaired vision would have problems, as would those who are colourblind. What’s wrong with having the route number on the front and a list of rotating destinations, like normal? It’s an interesting experiment but I think they’ve not really taken the requirements of those with disabilities into account.

  6. Likewise, a bus ticket here is purchased on the bus, and simply says “adult” or “adult day pass”. That would make every bus a candidate for my journey!

    Thankfully, our busses have a simple line number, each of which has colour scheme, so I can spot my bus half a mile down the road by colour.

    1. To correct myself by further study. it is 192 chose 3 which is 1161280 unique combinations. But how many can you make independent? A lot less. would be fun to figure out but I have a day job.

      1. I only read the article and the comments, and from yours i gather that it’s NOT a 3bit number!

        More like 3 letters from a 192 character alphabet?
        That’ll give 192^3 combinations. When restricted to “choose 3”, it would still be close, something like 192^3-192^2-192

Leave a Reply to piachooCancel reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.