Verificarea echivalenței între mulțimile distribuite

• Am elemente din $\{0, 1\}^{n}$ (gama unei funcții hash)
• Maestrul $A$ poate avea orice subset din acest interval.
• Există clienți care au fiecare un subset din spațiu.
• Vreau să mă asigur că unirea seturilor clienților este egală cu setul principal
• Comunicarea ar trebui să fie cât mai puțin posibil.
• Elementele sunt secrete. (această cerință poate fi relaxată cu o soluție care ar putea curge)

multumesc lui @kelalaka pentru rafinarea intrebarii.

O posibilă opțiune ar fi utilizarea Filtre de Bloom pentru a identifica potenţial dublează probabil, apoi verifică dacă sunt într-adevăr duplicate trimițând cele câteva potențiale. Dacă utilizați filtre de înflorire suficient de mari, acest lucru ar fi suficient pentru orice dimensiune.

Alternativ, ceea ce s-ar putea să nu se potrivească foarte bine până la urmă, ați putea folosi minischetă.

Din citiți-mă,

Schițele, așa cum sunt produse de această bibliotecă, pot fi văzute ca „sume de verificare setate” cu două proprietăți deosebite:

1. Schițele au o capacitate predeterminată, iar atunci când numărul de elemente din set nu este mai mare decât capacitatea, libminisketch va recupera întotdeauna întregul set din schiță. O schiță a elementelor b-bit cu capacitatea c poate fi stocată în bc biți.
2. Schițele a două seturi pot fi combinate prin adăugarea lor (XOR) pentru a obține o schiță a diferenței simetrice dintre cele două seturi (adică toate elementele care apar într-unul, dar nu în ambele seturi de intrare).

Deci, presupunând că utilizați o capacitate suficient de mare, puteți doar XOR schițele pentru a identifica elementele unice și a elimina restul.