  In recent years, there has been much research in Ranked Retrieval model in
structured databases, especially those in web databases. With this model, a
search query returns top-k tuples according to not just exact matches of
selection conditions, but a suitable ranking function. This paper studies a
novel problem on the privacy implications of database ranking. The motivation
is a novel yet serious privacy leakage we found on real-world web databases
which is caused by the ranking function design. Many such databases feature
private attributes - e.g., a social network allows users to specify certain
attributes as only visible to him/herself, but not to others. While these
websites generally respect the privacy settings by not directly displaying
private attribute values in search query answers, many of them nevertheless
take into account such private attributes in the ranking function design. The
conventional belief might be that tuple ranks alone are not enough to reveal
the private attribute values. Our investigation, however, shows that this is
not the case in reality.
  To address the problem, we introduce a taxonomy of the problem space with two
dimensions, (1) the type of query interface and (2) the capability of
adversaries. For each subspace, we develop a novel technique which either
guarantees the successful inference of private attributes, or does so for a
significant portion of real-world tuples. We demonstrate the effectiveness and
efficiency of our techniques through theoretical analysis, extensive
experiments over real-world datasets, as well as successful online attacks over
websites with tens to hundreds of millions of users - e.g., Amazon Goodreads
and Renren.com.
