Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it.


Problem: Suppose a list of N numbers is shared among a set of participants in such a way that no single participant actually knows any of the numbers they share. All participants know N (the size of the list of numbers) and the sum of all of the numbers on the list, but nothing more a priori.

By working together, it is possible to compare two shared numbers a and b in such a way that the participants learn whether the statement "a < b" is true, but nothing more. However, this is an extremely expensive thing to do (read: it could take many seconds, perhaps even minutes, to complete a single comparison). See the end of this post for a bit more information on how such a thing is possible.

At the end of the day, the parties wish to output of which indices in the list correspond to the "top K percent" (the K% which is largest) shared numbers in the list. This can of course be done by sorting, or using a "top K" selection algorithm. However, these tend to use an aweful lot of comparisons, which is to be avoided. (These are either O(n log n) or O(n), with fairly large hidden constants.)

Another alternative is to "guess" at a number X for which (1-K)% are smaller than X and K% are larger. Then you can compare each element with X and see how many are larger and how many are smaller. If your guess was wrong, revise it using something like a binary search until you converge on a correct solution. This takes far fewer comparisons if your guess is good.

So, my question is,

Given only N and the sum, what is the best way to "predict" X?

Of course this will depend on the underlying distribution. For different use-cases the underlying distribution will likely be different but will be known, so I am interested in good solutions for all the common ones (normal, uniform, exponential, perhaps a few others). I would also love to hear suggestions regarding how best to do the "binary-like" search to minimize the number of steps given an assumption about the underlying distribution.


APPENDIX: Each value on the list is shared among participants using Shamir's secret sharing scheme. Suppose there are M participants and the list is of length N. Then, the i-th number on the list is represented by a polynomial $f_i$ of degree M-1 over some finite field F. The constant term of $f_i$ is the number that is shared, all other coefficients are chosen uniformly at random from F. The j-th participant's shares are then $f_i(j)$, $1\leq i\leq N$. Given this share, the participant has no information (in an information-theoretic sense) about the number; in fact, no proper subset of participants can combine knowledge to learn any information about the shared numbers. However, using a sophisticated secure multi-party computation technique, it is possible to determine if one shared value is less than another without revealing any more information. This technique involves all participants cooperating, which is why it is so costly to do and should be done the fewest number of times possible.

share|improve this question

migrated from stats.stackexchange.com Apr 10 '11 at 17:15

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

    
This sounds interesting, but I don't fully understand the process yet. Can you clarify, particularly the second paragraph? How many participants $M$? Is $M$ greater than, less than, or equal to $N$? Does each participant know some subset of the numbers? Obviously they can't all just know $N$ and the sum since then there is no way to ask any question or collaborate in a way that aggregates information about $a < b$. Are there restrictions on the kinds of questions that can be asked? I look forward to your edit. –  cardinal Apr 1 '11 at 13:34
1  
Because this question appears to be more algorithmic than statistical (a request for clarification in this regard got no response) and the statistics community has not offered a viable reply, let's migrate to TCS to see whether it generates any interest there. –  whuber Apr 10 '11 at 17:14
6  
The real question seems to be simply the following: "If we know the distribution, how can we exploit this information in the design of a comparison-based selection algorithm? The algorithm should use as few comparisons as possible (in expectation; the constant factors matter)." Did I get this right? –  Jukka Suomela Apr 10 '11 at 17:55
2  
Have you considered Yao's Millionaires' Problem? It allows secure comparison with much less computation. –  Sadeq Dousti Apr 11 '11 at 17:53
3  
Please note that your assumption "in fact, no proper subset of participants can combine knowledge to learn any information about the shared numbers" is false. Indeed, the Shamir's secret sharing scheme is actually a $(k, n)$ threshold scheme in which you distributes $n$ shares of your secret so that at least $k$ shares can successfully reconstruct the secret (using interpolation). Even in the case of a $(n, n)$ scheme all of the participants together are able to reconstruct the secret. Of course, you usually use this scheme with $k << n$. –  Massimo Cafaro Feb 8 '12 at 17:20

1 Answer 1

You seem to ask two related questions:

  1. “which indices in the list correspond to the top”
  2. “Estimating a percentile”, “a number X for which … K% are larger”

These may need very different numbers of pairwise comparisons.

An other aspect that may have significant impact is what information is shared. Everybody knows the number he received, knows the sum, and the yes/no results of comparisons they have taken part in. However, you also say that “parties wish to output of which indices in the list correspond to the top” thus you suggest that some information about the indices will be shared. Depending on what exactly is shared you may get very different solutions again.

share|improve this answer
    
Sorry, I must not have been sufficiently clear. Nobody knows a single number on the list; instead, they each have a list of N "shares of numbers" (using Shamir's Secret Sharing scheme, if you aren't familiar with the concepts of shares of a number). So, the only a priori information that any single participant has is N and the sum of all numbers in the list. They each have a bit of information about each number, but not enough information to know what that number is. –  ryan Apr 1 '11 at 13:48
    
As far as the two related questions go, the second question implies an efficient solution to the first. If I can find X using few comparisons (which I can do if I can come up with a reasonably good initial guess), then I find the indices of all values larger than X using just N more comparisons (these comparisons are also cheaper, since knowing X instead of having a share of X cuts the cost of a comparison down by about 1 third.) General purpose algorithms for finding the top K will typically use far more comparisons for large list sizes, assuming I can find X using ~log(X) comparisons –  ryan Apr 1 '11 at 13:52
    
Thanks for the comment answers and the appendix to the original question. Now the problem looks different. –  GaBorgulya Apr 1 '11 at 15:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.