Show HN: Public transportation signage based on bloom filters (rough mockup)
For the main idea, basically, you get a small &quot;fingerprint&quot; of the stop you want to go to. Every train that comes has a &quot;fingerprint&quot; 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.<p>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&#x27; fingerprints together. If any bit of your destination fingerprint is missing from any train or station, then this train&#x2F;station is irrelevant to getting you to where you want to go.<p>Thus lookup is now O(1).