Estimando um percentil entre nós distribuídos sem revelar valores

23

Tenho um problema bastante único para resolver e espero que alguém aqui possa me dar algumas dicas sobre a melhor forma de enfrentá-lo.


Problema: Suponha que uma lista de N números seja compartilhada entre um conjunto de participantes de tal maneira que nenhum participante realmente conheça algum dos números que compartilha. Todos os participantes conhecem N (o tamanho da lista de números) e a soma de todos os números da lista, mas nada mais a priori.

Trabalhando juntos, é possível comparar dois números compartilhados aeb de tal maneira que os participantes aprendam se a afirmação "a <b" é verdadeira, mas nada mais. No entanto, isso é extremamente caro (leia-se: pode levar muitos segundos, talvez até minutos, para concluir uma única comparação). Veja o final deste post para obter mais informações sobre como isso é possível.

No final do dia, as partes desejam exibir quais índices na lista correspondem ao "percentual K superior" (o K% que é o maior) números compartilhados na lista. Obviamente, isso pode ser feito classificando ou usando um algoritmo de seleção "top K". No entanto, eles tendem a usar muitas comparações, o que deve ser evitado. (Estes são O (n log n) ou O (n), com constantes ocultas razoavelmente grandes.)

Outra alternativa é "adivinhar" um número X para o qual (1-K)% são menores que X e K% são maiores. Em seguida, você pode comparar cada elemento com X e ver quantos são maiores e quantos são menores. Se seu palpite estava errado, revise-o usando algo como uma pesquisa binária até convergir para uma solução correta. Isso leva muito menos comparações se o seu palpite for bom.

Então, minha pergunta é:

Dado apenas N e a soma, qual é a melhor maneira de "prever" X?

Obviamente, isso dependerá da distribuição subjacente. Para diferentes casos de uso, a distribuição subjacente provavelmente será diferente, mas será conhecida, por isso estou interessado em boas soluções para todas as comuns (normal, uniforme, exponencial, talvez algumas outras). Eu também adoraria ouvir sugestões sobre a melhor forma de fazer a pesquisa "binária" para minimizar o número de etapas, considerando-se a distribuição subjacente.


APÊNDICE: Cada valor da lista é compartilhado entre os participantes usando o esquema de compartilhamento secreto de Shamir. Suponha que haja M participantes e a lista tenha comprimento N. Então, o i-ésimo número da lista é representado por um polinômio de grau M-1 sobre algum campo finito F. O termo constante de é o número que é compartilhados, todos os outros coeficientes são escolhidos uniformemente aleatoriamente a partir de F. As ações do j-ésimo participante são então ,f i f i ( j ) 1 i Nfififi(j)1iN. Dada essa participação, o participante não possui informações (no sentido teórico da informação) sobre o número; de fato, nenhum subconjunto apropriado de participantes pode combinar conhecimento para obter informações sobre os números compartilhados. No entanto, usando uma técnica sofisticada de computação segura com várias partes, é possível determinar se um valor compartilhado é menor que outro sem revelar mais informações. Essa técnica envolve a cooperação de todos os participantes, razão pela qual é tão dispendiosa e deve ser realizada o menor número de vezes possível.

Kaveh
fonte
MMNNa<b
1
Como essa pergunta parece ser mais algorítmica do que estatística (uma solicitação de esclarecimento a esse respeito não obteve resposta) e a comunidade de estatísticas não ofereceu uma resposta viável, vamos migrar para o TCS para ver se isso gera algum interesse.
whuber
6
A verdadeira questão parece ser simplesmente o seguinte: "Se conhecemos a distribuição, como podemos explorar essas informações no design de um algoritmo de seleção baseado em comparação ? O algoritmo deve usar o mínimo de comparações possível (na expectativa; os fatores constantes importam)." Eu entendi direito?
Jukka Suomela
2
Você já considerou o problema dos milionários de Yao ? Permite uma comparação segura com muito menos computação.
MS Dousti
3
(k,n) nk(n,n)k<<n
Massimo Cafaro

Respostas:

1

Você parece fazer duas perguntas relacionadas:

  1. "Quais índices na lista correspondem ao topo"
  2. "Estimando um percentil", "um número X para o qual ... K% são maiores"

Estes podem precisar de números muito diferentes de comparações aos pares.

Outro aspecto que pode ter um impacto significativo é o que as informações são compartilhadas. Todo mundo sabe o número que recebeu, sabe a soma e os resultados sim / não das comparações em que participaram. No entanto, você também diz que “as partes desejam exibir quais índices na lista correspondem ao topo”, portanto, você sugere que algumas informações sobre os índices serão compartilhadas. Dependendo do que exatamente é compartilhado, você poderá obter soluções muito diferentes novamente.


fonte
Desculpe, não devo ter sido suficientemente claro. Ninguém conhece um único número na lista; em vez disso, cada um deles possui uma lista de N "compartilhamentos de números" (usando o esquema de Compartilhamento Secreto de Shamir, se você não estiver familiarizado com os conceitos de compartilhamento de um número). Portanto, a única informação a priori que um único participante possui é N e a soma de todos os números na lista. Cada um deles possui um pouco de informação sobre cada número, mas não informações suficientes para saber qual é esse número.
No que diz respeito às duas questões relacionadas, a segunda pergunta implica uma solução eficiente para a primeira. Se eu conseguir encontrar X usando poucas comparações (o que posso fazer se conseguir uma estimativa inicial razoavelmente boa), então os índices de todos os valores maiores que X usarão apenas N mais comparações (essas comparações também são mais baratas, pois conhecer X em vez de ter uma parte de X reduz o custo de uma comparação em cerca de 1 terço.) Os algoritmos de uso geral para encontrar o K superior normalmente usam muito mais comparações para grandes tamanhos de lista, supondo que eu possa encontrar X usando ~ log ( X) comparações
Obrigado pelas respostas dos comentários e pelo apêndice da pergunta original. Agora o problema parece diferente.