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.
Source link
