4 ms·

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.

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

elil17 4y ago
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?
- bitsinthesky 4y ago
  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.
  - elil17 4y ago
    Seems like the kind of thing that is great in theory but would end up with a high error rate in practice.
    - pavel_lishin 4y ago
      It also seems like it would actually be fairly difficult to explain to a majority of people, especially in a non-verbal way.
  - michaelmior 4y ago
    > 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.
    - infogulch 4y ago
      Ah, a perfect bloom filter. https://www.researchgate.net/publication/260163952_Minimal_perfect_hashing_and_bloom_filters_made_practical 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.
      - michaelmior 4y ago
        Maybe, but I think educating transit riders on how to use them correctly would be a major challenge.
captn3m0 4y ago
Wondering if Emoji Sequences would be a more user-friendly approach for visualization.
- bitsinthesky 4y ago
  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.
vineyardmike 4y ago
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.
alexvoda 4y ago
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.
- alexvoda 4y ago
  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.
  - bobthepanda 4y ago
kodah 4y ago
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.

elil17 4y ago

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?

bitsinthesky 4y ago
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.
- elil17 4y ago
  Seems like the kind of thing that is great in theory but would end up with a high error rate in practice.
  - pavel_lishin 4y ago
    It also seems like it would actually be fairly difficult to explain to a majority of people, especially in a non-verbal way.
- michaelmior 4y ago
  > 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.
  - infogulch 4y ago
    Ah, a perfect bloom filter. https://www.researchgate.net/publication/260163952_Minimal_perfect_hashing_and_bloom_filters_made_practical 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.
    - michaelmior 4y ago
      Maybe, but I think educating transit riders on how to use them correctly would be a major challenge.

captn3m0 4y ago

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

bitsinthesky 4y ago
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.

vineyardmike 4y ago

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.

alexvoda 4y ago

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.

alexvoda 4y ago
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.
- bobthepanda 4y ago

kodah 4y ago

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.