Оценка процентиля среди распределенных узлов без раскрытия значений

23

У меня есть довольно уникальная проблема, которую я хочу решить, и я надеюсь, что кто-то здесь может дать мне некоторое представление о том, как лучше всего ее решить.


Проблема: Предположим, что список из N номеров распределяется среди набора участников таким образом, что ни один участник не знает ни одного из номеров, которые они разделяют. Все участники знают N (размер списка чисел) и сумму всех чисел в списке, но ничего более априори.

Работая вместе, можно сравнить два общих числа a и b таким образом, чтобы участники узнали, верно ли утверждение «a <b», но не более того. Однако это чрезвычайно дорогое занятие (читай: на завершение отдельного сравнения может потребоваться много секунд, возможно, даже минут). Смотрите в конце этого поста немного больше информации о том, как это возможно.

В конце дня стороны хотят, чтобы индексы в списке соответствовали «верхним K процентам» (K%, который является наибольшим) общими номерами в списке. Это, конечно, можно сделать путем сортировки или использования алгоритма выбора «top K». Тем не менее, они, как правило, используют очень много сравнений, которых следует избегать. (Это либо O (n log n), либо O (n) с довольно большими скрытыми константами.)

Другой альтернативой является «угадать» число X, для которого (1-K)% меньше, чем X, а K% больше. Затем вы можете сравнить каждый элемент с X и увидеть, сколько их больше, а сколько меньше. Если ваше предположение было неверным, пересмотрите его, используя что-то вроде бинарного поиска, пока не найдете правильное решение. Это займет гораздо меньше сравнений, если ваше предположение хорошо.

Итак, мой вопрос,

Учитывая только N и сумму, каков наилучший способ «предсказать» X?

Конечно, это будет зависеть от основного распределения. Для разных вариантов использования базовое распределение, вероятно, будет другим, но будет известно, поэтому я заинтересован в хороших решениях для всех общих (нормальных, равномерных, экспоненциальных, возможно, некоторых других). Я также хотел бы услышать предложения о том, как лучше всего выполнить «бинарный» поиск, чтобы минимизировать количество шагов с учетом предположения о базовом распределении.


fififi(j)1iN, Учитывая эту долю, участник не имеет информации (в теоретико-информационном смысле) о числе; на самом деле, ни одна надлежащая группа участников не может объединить знания, чтобы узнать какую-либо информацию об общих номерах. Однако, используя сложную безопасную технику многопартийных вычислений, можно определить, меньше ли одно общее значение, чем другое, не раскрывая больше информации. Этот метод вовлекает всех участников сотрудничества, поэтому это так дорого и должно быть сделано как можно меньше раз.

Кава
источник
MMNNa<b
1
Поскольку этот вопрос представляется более алгоритмическим, чем статистическим (запрос на разъяснение в этом отношении не получил ответа), а сообщество статистики не дало жизнеспособного ответа, давайте перейдем к TCS, чтобы посмотреть, вызывает ли оно там какой-либо интерес.
whuber
6
Реальный вопрос, по-видимому, заключается в следующем: «Если мы знаем распределение, как мы можем использовать эту информацию при разработке алгоритма выбора на основе сравнения ? Алгоритм должен использовать как можно меньше сравнений (в ожидании; постоянные факторы дело)." Я правильно понял?
Юкка Суомела
2
Рассматривали ли вы проблему миллионеров Яо ? Это позволяет безопасное сравнение с гораздо меньшими вычислениями.
MS Dousti
3
(k,n) nk(n,n)k<<n
Массимо Кафаро

Ответы:

1

Вы, кажется, задаете два связанных вопроса:

  1. «Какие показатели в списке соответствуют верхним»
  2. «Оценка процентиля», «число X, для которого… K% больше»

Это может потребовать очень разных чисел парных сравнений.

Другим аспектом, который может оказать существенное влияние, является то, какая информация передается. Каждый знает номер, который он получил, знает сумму и результаты «да / нет» сравнений, в которых они принимали участие. Однако вы также говорите, что «стороны хотят выводить, какие индексы в списке соответствуют верхним», поэтому вы предлагаете что некоторая информация об индексах будет передана. В зависимости от того, чем именно вы делитесь, вы снова можете получить очень разные решения.


источник
Извините, я не должен был быть достаточно ясным. Никто не знает ни одного числа в списке; вместо этого каждый из них имеет список из N «долей чисел» (используя схему секретного обмена Шамира, если вы не знакомы с понятиями долей числа). Таким образом, единственная априорная информация, которую имеет любой отдельный участник, - это N и сумма всех чисел в списке. У каждого из них есть немного информации о каждом номере, но недостаточно информации, чтобы узнать, что это за номер.
Что касается двух связанных вопросов, то второй вопрос подразумевает эффективное решение первого. Если я могу найти X, используя несколько сравнений (что я могу сделать, если смогу дать достаточно хорошее начальное предположение), то я найду индексы всех значений, превышающих X, используя только N больше сравнений (эти сравнения также дешевле, так как Знание X вместо доли X снижает стоимость сравнения примерно на 1 треть.) Алгоритмы общего назначения для поиска верхнего K обычно используют гораздо больше сравнений для больших размеров списка, предполагая, что я могу найти X с помощью ~ log ( X) сравнения
Спасибо за комментарии, ответы и приложение к оригинальному вопросу. Теперь проблема выглядит иначе.