OverviewExploreTrending
Nostr Archives
OverviewExploreTrending
elsat16d ago
Thanks for taking interest. I will add methodology overview to the readme. To your questions: 1. I extracted the algorithms from nostr outbox implementations to a typescript library. 2. In the TS library we have nostr algos from the real world (e.g. from amethyst, nostrudel, nostur etc) 3. In the TS library we also have the general CS algorithms not yet found in nostr apps 4. The computer science problem of “outbox” maps to “weighted set cover problem” AKA “maximum coverage problem”. https://en.wikipedia.org/wiki/Maximum_coverage_problem 5. The “winning” algo for long term event retrieval MAB is used in real world applications in online ads, a/b testing https://web.stanford.edu/class/cme241/lecture_slides/Mult… https://web.mit.edu/6.7950/www/lectures/L15-2022fa.pdf 6. I answer two questions to the above: Given a npub (e.g. fiatjaf who has 400/whatever follows) run a ~~dozen or so algos A) “assignment coverage” phase 1(academic/no network ) if every relay is online, and no events are deleted, how many of your follows are reached by this algo? B) “event recall” phase 2 (real world like/pull events from relays) given realistic conditions of relays being down, events being pruned/deleted, relays gating event retrieval (via auth or otherwise) what are the numbers? C) given phase 2 above, what happens if we triage relays first via nip-66 liveness monitor events, relays, services like nostr.watch by @e771af0b…8e8ed66f 7. I have not gone into a dozen apps to measure in app the outbox results. All of this is done in deno/typescript 8. The real world results are vastly different than the academic ones. I’m measuring more details on nip-66 - the hypotheses are 1) improved coverage, and 2) drastically reduced number of calls to relays to find the info being sought
💬 3 replies

Thread context

Root: bcb29c08a3ef…

Replying to: c765fa0e18f0…

Replies (3)

Mike Dilger ☑️13d ago
IMHO regarding coverage: clients don't need to find a minimum set with maximum coverage. Clients can just connect to 500 relays to follow 500 people. It still works. But of course it is more efficient to do otherwise, and especially if some relays are down, to find the set that is up and covers everyone. I think (as you describe in (8) that real world considerations probably far outweigh theoretical algorithm choices. But that doesn't mean we shouldn't bother to get the algorithms right.
0000 sats
semisol16d ago
I should also say that writes to 1 relay can fail. So, outbox algorithm should read from multiple of users’ inboxes.
0000 sats
elsat16d ago
I made the report less academic, and more actionable. Specific to your question on how to implement the cs algo - mab - see https://github.com/nostrability/outbox/blob/main/IMPLEMEN… And https://github.com/nostrability/outbox/blob/main/IMPLEMEN… MAB complements nip-66 well - nip-66 checks liveness before asking relays, whereas MAB tracks relay health *after* asking the relay, and scores it. Nosotros @c6603b0f…a728019e looks like has a “seen” table (event created at x seen on relay y), and it is not providing feedback to relay selection for future lookups.
0000 sats