Thursday, March 20, 2008

Private query with ranking

The following problem has been studied: Alice has a bit array A and Bob has a query index i. Bob needs to lookup A[i]. The protocol needs to ensure that Alice is unaware of i and Bob remains unaware of everying except A[i].

Now imagine A is some search engine and Bob has a query word w. The problem to make the query without A knowing w. This may be related to the above problem if A[w] is say the ranked list of answers to the query w.

Going further, what if Bob's query comprised two words w_1 and w_2, or three words, and so on. Search engines may not precompute A array for all combinations of query words, and it is not just desirable to privately retrieve the ranked lists A[w_i] for each w_i in a query and try to combine the ranking on one's own. Is there a nice formulation of the problem of retrieving the ranked list of answers for the combination of the words in the query?

[This is a stream of consciousness question. I am not an expert in private queries or searching.]


Post a Comment

<< Home