Saya memiliki masalah yang cukup unik untuk dipecahkan dan saya berharap seseorang di sini dapat memberi saya wawasan tentang cara terbaik untuk mengatasinya.
Masalah: Misalkan daftar nomor N dibagikan di antara sekumpulan peserta sedemikian rupa sehingga tidak ada satu pun peserta yang benar-benar mengetahui angka yang dibagikan. Semua peserta tahu N (ukuran daftar angka) dan jumlah semua angka dalam daftar, tetapi tidak lebih apriori.
Dengan bekerja bersama, dimungkinkan untuk membandingkan dua angka bersama a dan b sedemikian rupa sehingga para peserta belajar apakah pernyataan "a <b" itu benar, tetapi tidak lebih. Namun, ini adalah hal yang sangat mahal untuk dilakukan (baca: mungkin butuh beberapa detik, bahkan mungkin beberapa menit, untuk menyelesaikan satu perbandingan). Lihat akhir posting ini untuk informasi lebih lanjut tentang bagaimana hal itu mungkin terjadi.
Pada akhirnya, para pihak ingin menampilkan indeks mana dalam daftar yang sesuai dengan "persen K atas" (% K yang merupakan terbesar) nomor bersama dalam daftar. Ini tentu saja dapat dilakukan dengan menyortir, atau menggunakan algoritma seleksi "top K". Namun, ini cenderung menggunakan banyak sekali perbandingan, yang harus dihindari. (Ini adalah O (n log n) atau O (n), dengan konstanta tersembunyi yang cukup besar.)
Alternatif lain adalah "menebak" pada angka X yang (1-K)% lebih kecil dari X dan K% lebih besar. Kemudian Anda dapat membandingkan setiap elemen dengan X dan melihat berapa banyak yang lebih besar dan berapa banyak yang lebih kecil. Jika tebakan Anda salah, perbaiki menggunakan sesuatu seperti pencarian biner sampai Anda menemukan solusi yang tepat. Ini membutuhkan perbandingan yang jauh lebih sedikit jika tebakan Anda bagus.
Jadi, pertanyaan saya adalah,
Hanya diberi N dan jumlahnya, apa cara terbaik untuk "memprediksi" X?
Tentu saja ini akan tergantung pada distribusi yang mendasarinya. Untuk kasus penggunaan yang berbeda, distribusi yang mendasarinya mungkin akan berbeda tetapi akan diketahui, jadi saya tertarik pada solusi yang baik untuk semua yang umum (normal, seragam, eksponensial, mungkin beberapa lainnya). Saya juga ingin mendengar saran mengenai cara terbaik untuk melakukan pencarian "seperti biner" untuk meminimalkan jumlah langkah yang diberikan asumsi tentang distribusi yang mendasarinya.
LAMPIRAN: Setiap nilai dalam daftar dibagi di antara peserta menggunakan skema berbagi rahasia Shamir. Misalkan ada peserta M dan daftar panjangnya N. Kemudian, nomor ke-10 dalam daftar tersebut diwakili oleh polinomial derajat M-1 di atas beberapa bidang hingga F. Istilah konstanta adalah angka yang dibagikan, semua koefisien lainnya dipilih secara seragam secara acak dari F. Bagian peserta j-th kemudian ,f i f i ( j ) 1 ≤ i ≤ N. Mengingat bagian ini, peserta tidak memiliki informasi (dalam arti informasi-teoretis) tentang nomor tersebut; pada kenyataannya, tidak ada subset yang tepat dari peserta yang dapat menggabungkan pengetahuan untuk mempelajari informasi apa pun tentang angka bersama. Namun, dengan menggunakan teknik perhitungan multi-pihak aman yang canggih, dimungkinkan untuk menentukan apakah satu nilai yang dibagikan kurang dari yang lain tanpa mengungkapkan informasi lebih lanjut. Teknik ini melibatkan semua peserta yang bekerja sama, itulah sebabnya sangat mahal untuk dilakukan dan harus dilakukan sesingkat mungkin.
Jawaban:
Anda sepertinya mengajukan dua pertanyaan terkait:
Ini mungkin membutuhkan jumlah perbandingan berpasangan yang sangat berbeda.
Aspek lain yang mungkin memiliki dampak signifikan adalah informasi apa yang dibagikan. Semua orang tahu jumlah yang diterimanya, mengetahui jumlah, dan hasil perbandingan ya / tidak yang telah mereka ikuti. Namun, Anda juga mengatakan bahwa "para pihak ingin menampilkan indeks mana dalam daftar yang sesuai dengan bagian atas" sehingga Anda menyarankan bahwa beberapa informasi tentang indeks akan dibagikan. Bergantung pada apa yang dibagikan secara persis, Anda mungkin mendapatkan solusi yang sangat berbeda lagi.
sumber