D. ?. and ?. {1, Also, for every t j ? Q we set in the proximity vector, after p + 1, the next x ij = unseen_users(D p [i], t j ) values to top p (H), making also D p [i] present in each of these users' lists for t j . By doing so, the exact score of each D p [i], k}, is equal to the maximal possible one at step p; after max i,j (x ij ) steps, all these k scores Score(D p [i], Q) would be computed. For item r, for each t j ? Q for which we do not have t f (r, t j ), since r must come later in IL(t j ) (after v j ), we can assume that t f (r, t j ) = partial_t f (r, t j ) (this makes unseen_users(r, t j ) = 0). Also, for every t j ? Q for which we do know t f (r, t j ), after the required max i,j (x ij ) proximity values set as described previously, we set the next unseen_users(r, t j ) in the proximity vector to 0, with each of these users having tagged r with t j . All this ensures that MinScore p (r, Q) = Score(r, Q)

. Hence, But since D ? and D are indistinguishable by algorithm A, which stops at step p outputting r in the result, this contradicts A's correctness. Case 2: A does not output r as a top-k item, which means that A assumes that the final score of r, Score(r, Q) is not in the top-k scores for

S. Maniu, T. Abdessalem, and B. Cautis, Casting a web of trust over Wikipedia, Proceedings of the 20th international conference companion on World wide web, WWW '11, 2011.
DOI : 10.1145/1963192.1963237

[. Maniu and B. Cautis, Taagle, Proceedings of the 2012 international conference on Management of Data, SIGMOD '12, 2012.
DOI : 10.1145/2213836.2213926
URL : https://hal.archives-ouvertes.fr/hal-00711465

[. Maniu and B. Cautis, Context-aware top-k processing using views. Preliminary version published in BDA 2012
URL : https://hal.archives-ouvertes.fr/hal-00927307

S. Maniu, B. Cautis, and T. Abdessalem, Building a signed network from interactions in Wikipedia, Databases and Social Networks on, DBSocial '11, 2011.
DOI : 10.1145/1996413.1996417
URL : https://hal.archives-ouvertes.fr/hal-00703506

S. Maniu, B. Cautis, and T. Abdessalem, Enabling networkaware search in online social bookmarking applications. Preliminary version published in BDA 2011

. Maniu, O. Neil, L. M. Hare, L. Aiello, A. Chiarandini et al., Search behaviour on photo sharing platforms, 2013 IEEE International Conference on Multimedia and Expo (ICME)
DOI : 10.1109/ICME.2013.6607496

B. T. Adler, K. Chatterjee, L. De-alfaro, M. Faella, I. Pye et al., Assigning trust to Wikipedia content, Proceedings of the 4th International Symposium on Wikis, WikiSym '08, 2008.
DOI : 10.1145/1822258.1822293

B. T. Adler and L. De-alfaro, A content-driven reputation system for the wikipedia, Proceedings of the 16th international conference on World Wide Web , WWW '07, 2007.
DOI : 10.1145/1242572.1242608

N. Ailon, M. Charikar, and A. Newman, Aggregating inconsistent information: Ranking and clustering, J. ACM, 2008.

S. Amer-yahia, M. Benedikt, L. Lakshmanan, and J. Stoyanovich, Efficient network aware search in collaborative tagging sites, VLDB, 2008.

S. Amer-yahia, J. Huang, and C. Yu, Building community-centric information exploration applications on social content sites, Proceedings of the 35th SIGMOD international conference on Management of data, SIGMOD '09, 2009.
DOI : 10.1145/1559845.1559953

S. Amer-yahia, L. Lakshmanan, and C. Yu, Socialscope: Enabling information discovery on social content sites, CIDR, 2009.

B. Bahmani, A. Chowdhury, and A. Goel, Fast incremental and personalized PageRank, PVLDB, 2010.
DOI : 10.14778/1929861.1929864

B. Bahmani and A. Goel, Partitioned multi-indexing, Proceedings of the 21st international conference on World Wide Web, WWW '12, 2012.
DOI : 10.1145/2187836.2187891

S. Bao, G. Xue, X. Wu, Y. Yu, B. Fei et al., Optimizing web search using social annotations, Proceedings of the 16th international conference on World Wide Web , WWW '07, 2007.
DOI : 10.1145/1242572.1242640

A. Bernstein, Fully dynamic (2 + ?) approximate all-pairs shortest paths with fast query and close to linear update time, FOCS, 2009.

B. Bi, S. Lee, B. Kao, and R. Cheng, CubeLSI: An effective and efficient method for searching resources in social tagging systems, 2011 IEEE 27th International Conference on Data Engineering, 2011.
DOI : 10.1109/ICDE.2011.5767863

U. Brandes, P. Kenis, J. Lerner, D. Van-raaij, G. Cong et al., Network analysis of collaboration structure in Wikipedia Retrieving top-k prestige-based relevant spatial web objects, WWW PVLDB, 2009.

X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi, Collective spatial keyword querying, Proceedings of the 2011 international conference on Management of data, SIGMOD '11, 2011.
DOI : 10.1145/1989323.1989363

D. Carmel, N. Zwerdling, I. Guy, S. Ofek-koifman, N. Har-'el et al., Personalized social search based on the user's social network, Proceeding of the 18th ACM conference on Information and knowledge management, CIKM '09, 2009.
DOI : 10.1145/1645953.1646109

L. J. Chen and Y. Papakonstantinou, Supporting top-K keyword search in XML databases, 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), 2010.
DOI : 10.1109/ICDE.2010.5447818

K. Chiang, N. Natarajan, A. Tewari, and I. S. Dhillon, Exploiting longer cycles for link prediction in signed networks, Proceedings of the 20th ACM international conference on Information and knowledge management, CIKM '11, 2011.
DOI : 10.1145/2063576.2063742

F. Chierichetti, R. Kumar, S. Lattanzi, M. Mitzenmacher, A. Panconesi et al., On compressing social networks, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '09, 2009.
DOI : 10.1145/1557019.1557049

M. Christoforaki, J. He, C. Dimopoulos, A. Markowetz, and T. Suel, Text vs. space, Proceedings of the 20th ACM international conference on Information and knowledge management, CIKM '11, 2011.
DOI : 10.1145/2063576.2063641

C. Chu, S. K. Kim, Y. Lin, Y. Y. Yu, G. Bradski et al., Map-Reduce for machine learning on multicore, NIPS, 2006.

G. Cong, C. S. Jensen, and D. Wu, Efficient retrieval of the top-k most relevant spatial web objects, VLDB, 2009.
DOI : 10.14778/1687627.1687666

G. Das, D. Gunopulos, N. Koudas, and D. Tsirogiannis, Answering top-k queries using views, VLDB, 2006.

J. Dean and S. Ghemawat, MapReduce, OSDI, 2004.
DOI : 10.1145/1327452.1327492

E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica, Correlation clustering in general weighted graphs, Theoretical Computer Science, vol.361, issue.2-3, 2006.
DOI : 10.1016/j.tcs.2006.05.008

E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, vol.4, issue.1, 1959.
DOI : 10.1007/BF01386390

Z. Dou, R. Song, and J. Wen, A large-scale evaluation and analysis of personalized search strategies, Proceedings of the 16th international conference on World Wide Web , WWW '07
DOI : 10.1145/1242572.1242651

C. Dwork, R. Kumar, M. Naor, and D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the tenth international conference on World Wide Web , WWW '01, 2001.
DOI : 10.1145/371920.372165

R. Fagin, R. Kumar, M. Mahdian, D. Sivakumar, and E. Vee, Comparing and aggregating rankings with ties, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '04, 2004.
DOI : 10.1145/1055558.1055568

R. Fagin, R. Kumar, and D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proceedings of the 2003 ACM SIGMOD international conference on on Management of data , SIGMOD '03, 2003.
DOI : 10.1145/872757.872795

R. Fagin, A. Lotem, and M. Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '01, 2001.
DOI : 10.1145/375551.375567

L. Gou, X. L. Zhang, H. Chen, J. Kim, and C. L. Giles, Social network document ranking, Proceedings of the 10th annual joint conference on Digital libraries, JCDL '10, 2010.
DOI : 10.1145/1816123.1816170

R. Guha, R. Kumar, P. Raghavan, and A. Tomkins, Propagation of trust and distrust, Proceedings of the 13th conference on World Wide Web , WWW '04, 2004.
DOI : 10.1145/988672.988727

A. Guttman, R-tree: a dynamic index structure for spatial searching, SIGMOD, 1984.

Z. Gyöngi, H. G. Molina, and J. Pedersen, Combating web spam with TrustRank, VLDB, 2004.

F. Heider, Attitudes and cognitive organization, Journal of Psychology, 1946.

P. Heymann, G. Koutrika, and H. Garcia-molina, Can social bookmarking improve web search? In WSDM, 2008.

D. Horowitz and S. D. Kamvar, The anatomy of a large-scale social search engine, Proceedings of the 19th international conference on World wide web, WWW '10, 2010.
DOI : 10.1145/1772690.1772735

A. Hotho, R. Jãd-'schke, C. Schmitz, and G. Stumme, Information Retrieval in Folksonomies: Search and Ranking, ESWC, pp.111-114, 2006.
DOI : 10.1007/11762256_31

V. Hristidis and Y. Papakonstantinou, Algorithms and applications for answering ranked queries using ranked views, VLDBJ, 2004.
DOI : 10.1007/s00778-003-0099-8

I. F. Ilyas, G. Beskales, and M. A. Soliman, A survey of top-k query processing techniques in relational database systems, In ACM Comp. Surv, 2008.

S. Javanmardi, C. Lopes, P. Baldi, G. Jeh, and J. Widom, Modeling user reputation in wikis SimRank: a measure of structural-context similarity, KDD, 2002.

G. Jeh and J. Widom, Scaling personalized web search, Proceedings of the twelfth international conference on World Wide Web , WWW '03, 2003.
DOI : 10.1145/775152.775191

S. D. Kamvar, M. T. Schlosser, and H. G. Molina, The eigentrust algorithm for reputation management in p2p netwokrs, WWW, 2003.

I. Konstas, V. Stathopoulos, and J. Jose, On social networks and collaborative recommendation, Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, SIGIR '09
DOI : 10.1145/1571941.1571977

R. Kumar, K. Punera, T. Suel, and S. Vassilvitskii, Top-k aggregation using intersections of ranked inputs, WSDM, 2009.

J. Kunegis, A. Lommatzsch, and C. Bauckhage, The slashdot zoo, Proceedings of the 18th international conference on World wide web, WWW '09, 2009.
DOI : 10.1145/1526709.1526809

J. Leskovec, D. Huttenlocher, and J. Kleinberg, Predicting positive and negative links in online social networks, Proceedings of the 19th international conference on World wide web, WWW '10, 2010.
DOI : 10.1145/1772690.1772756

J. Leskovec, D. Huttenlocher, and J. Kleinberg, Signed networks in social media, Proceedings of the 28th international conference on Human factors in computing systems, CHI '10, 2010.
DOI : 10.1145/1753326.1753532

D. Liben-nowell and J. Kleinberg, The link-prediction problem for social networks, JASIST, 2007.

H. Liu, E. Lim, H. W. Lauw, M. Le, A. Sun et al., Predicting trusts among users of online communities, Proceedings of the 9th ACM conference on Electronic commerce, EC '08, 2008.
DOI : 10.1145/1386790.1386838

S. Maniu and B. Cautis, Taagle, Proceedings of the 2012 international conference on Management of Data, SIGMOD '12, 2012.
DOI : 10.1145/2213836.2213926
URL : https://hal.archives-ouvertes.fr/hal-00711465

C. D. Manning, P. Raghavan, and H. Schutze, Introduction to Information Retrieval, 2008.
DOI : 10.1017/CBO9780511809071

A. Marian, S. Amer-yahia, N. Koudas, and D. Srivastava, Adaptive Processing of Top-k Queries in XML, 21st International Conference on Data Engineering (ICDE'05), 2005.
DOI : 10.1109/ICDE.2005.18

A. A. Markov, On certain applications of algebraic continued fractions, p.1884

P. Massa and P. Avesani, Controversial users demand local trust metrics: an experimental study on epinions.com, AAAI, 2005.

A. Mishra and A. Bhattacharya, Finding the bias and prestige of nodes in networks based on trust scores, Proceedings of the 20th international conference on World wide web, WWW '11
DOI : 10.1145/1963405.1963485

A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee, Measurement and analysis of online social networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement , IMC '07, 2007.
DOI : 10.1145/1298306.1298311

B. Nikhil, A. Blum, and S. Chawla, Correlation clustering, Machine Learning, 2004.

C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity, 1998.

H. S. Rad, A. Makazhanov, D. Rafiei, and D. Barbosa, Leveraging editor collaboration patterns in Wikipedia, 2012.

C. Ré, N. Dalvi, and D. Suciu, Efficient Top-k Query Evaluation on Probabilistic Data, 2007 IEEE 23rd International Conference on Data Engineering, 2007.
DOI : 10.1109/ICDE.2007.367934

M. Richardson, R. Agrawal, and P. Domingos, Trust Management for the Semantic Web, ISWC, 2003.
DOI : 10.1007/978-3-540-39718-2_23

J. Rocha-junior, A. Vlachou, C. Doulkeridis, and K. Norvag, Efficient processing of top-k spatial preference queries, VLDB, 2010.
DOI : 10.14778/1921071.1921076

L. Roddity and U. Zwick, On dynamic shortest paths problems, Algorithmica, 2010.

R. Schenkel, T. Crecelius, M. Kacimi, S. Michel, T. Neumann et al., Efficient top-k querying over social-tagging networks, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR '08, 2008.
DOI : 10.1145/1390334.1390424

F. Scholer, H. Williams, J. Yiannis, and J. Zobel, Compression of inverted indexes For fast query evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval , SIGIR '02, 2002.
DOI : 10.1145/564376.564416

P. Singla and M. Richardson, Yes, there is a correlation -from social networks to personal behavior on the web, WWW, 2008.

M. A. Soliman, I. F. Ilyas, and S. Ben-david, Supporting ranking queries on uncertain and incomplete data, VLDBJ, 2010.
DOI : 10.1007/s00778-009-0176-8

B. Suh, G. Convertino, E. H. Chi, and P. Pirolli, The singularity is not near, Proceedings of the 5th International Symposium on Wikis and Open Collaboration, WikiSym '09, 2009.
DOI : 10.1145/1641309.1641322

S. Suri and S. Vassilvitskii, Counting triangles and the curse of the last reducer, Proceedings of the 20th international conference on World wide web, WWW '11, 2011.
DOI : 10.1145/1963405.1963491

V. A. Traag, Y. E. Nesterov, and P. V. Dooren, Exponential Ranking: Taking into Account Negative Links, SocInfo, 2010.
DOI : 10.1007/978-3-642-16567-2_14

J. Twitter, M. Wang, J. Clements, A. P. Yang, M. J. De-vries et al., Twitter turns six Personalization of tagging systems, Inf. Process. Manage, 2010.

R. Wetzker, C. Zimmermann, and C. Bauckhage, Analyzing social bookmarking items: A del.icio.us cookbook, ECAI Mining Social Data Workshop, 2008.

E. B. Wilson, Probable Inference, the Law of Succession, and Statistical Inference, Journal of the American Statistical Association, vol.22, issue.158, 1927.
DOI : 10.1080/01621459.1927.10502953

S. Xu, S. Bao, B. Fei, Z. Su, and Y. Yu, Exploring folksonomy for personalized search, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR '08, 2008.
DOI : 10.1145/1390334.1390363

H. Yan, S. Ding, and T. Suel, Inverted index compression and query processing with optimized document ordering, Proceedings of the 18th international conference on World wide web, WWW '09, 2009.
DOI : 10.1145/1526709.1526764

P. Yin, W. Lee, and K. C. Lee, On top-k social web search, Proceedings of the 19th ACM international conference on Information and knowledge management, CIKM '10, 2010.
DOI : 10.1145/1871437.1871609

J. Zhang, X. Long, and T. Suel, Performance of compressed inverted list caching in search engines, Proceeding of the 17th international conference on World Wide Web , WWW '08, 2008.
DOI : 10.1145/1367497.1367550

J. Zobel and A. Moffat, Inverted files for text search engines, ACM Computing Surveys, vol.38, issue.2, 2006.
DOI : 10.1145/1132956.1132959

M. Zukowski, S. Heman, N. Nes, and P. Boncz, Super-Scalar RAM-CPU Cache Compression, 22nd International Conference on Data Engineering (ICDE'06), 2006.
DOI : 10.1109/ICDE.2006.150