ABSTRACT
Contextual preferences take the form that item i1 is preferred to item i2 in the context of X. For example, a preference might state the choice for Nicole Kidman over Penelope Cruz in drama movies, whereas another preference might choose Penelope Cruz over Nicole Kidman in the context of Spanish dramas. Various sources provide preferences independently and thus preferences may contain cycles and contradictions. We reconcile democratically the preferences accumulated from various sources and use them to create a priori orderings of tuples in an off-line preprocessing step. Only a few representative orders are saved, each corre-sponding to a set of contexts. These orders and associated contexts are used at query time to expeditiously provide ranked answers. We formally define contextual preferences, provide algorithms for creating orders and processing queries, and present experimental results that show their efficacy and practical utility.
- R. Agrawal, T. Imielinski, and A. N. Swami. Mining association rules between sets of items in large databases. In SIGMOD, pages 207--216, 1993. Google ScholarDigital Library
- R. Agrawal and E. L. Wimmers. A framework for expressing and combining preferences. In SIGMOD, pages 297--306, 2000. Google ScholarDigital Library
- S. Agrawal, S. Chaudhuri, G. Das, and A. Gionis. Automated ranking of database query results. In CIDR, 2003.Google Scholar
- A. Balmin, V. Hristidis, and Y. Papakonstantinou. Objectrank: Authority-based keyword search in databases. In VLDB, pages 564--575, 2004. Google ScholarDigital Library
- B. Berger and P. W. Shor. Approximation algorithms for the maximum acyclic subgraph problem. In SODA, pages 236--243, 1990. Google ScholarDigital Library
- G. Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti, and S. Sudarshan. Keyword searching and browsing in databases using BANKS. In ICDE, pages 431--440, 2002. Google ScholarDigital Library
- S. Borzsonyi, D. Kossmann, and K. Stocker. The skyline operator. In ICDE, pages 421--430, 2001. Google ScholarDigital Library
- S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks, 30(1-7):107--117, 1998. Google ScholarDigital Library
- S. Chaudhuri, G. Das, V. Hristidis, and G. Weikum. Probabilistic ranking of database query results. In VLDB, pages 888--899, 2004. Google ScholarDigital Library
- J. Chomicki. Preference formulas in relational queries. ACM Trans. Database Syst., 28(4):427--466, 2003. Google ScholarDigital Library
- M. Chrobak, C. Kenyon, and N. E. Young. The reverse greedy algorithm for the metric k-median problem. In COCOON, 2005.Google Scholar
- W. W. Cohen, R. E. Schapire, and Y. Singer. Learning to order things. In NIPS, 1997. Google ScholarDigital Library
- P. Diaconis and R. Graham. Spearman's footrule as a measure of disarray. J. of the Royal Statistical Society, 39(2):262--268, 1977.Google Scholar
- C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation methods for the web. In WWW, pages 613--622, 2001. Google ScholarDigital Library
- R. Fagin, R. Kumar, M. Mahdian, D. Sivakumar, and E. Vee. Comparing and aggregating rankings with ties. In PODS, pages 47--58, 2004. Google ScholarDigital Library
- R. Fagin, R. Kumar, and D. Sivakumar. Comparing top k lists. In SODA, pages 28--36, 2003. Google ScholarDigital Library
- R. Fagin, R. Kumar, and D. Sivakumar. Efficient similarity search and classification via rank aggregation. In SIGMOD, pages 301--312, 2003. Google ScholarDigital Library
- R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In PODS, pages 102--113, 2001. Google ScholarDigital Library
- F. Geerts, H. Mannila, and E. Terzi. Relational link-based ranking. In VLDB, pages 552--563, 2004. Google ScholarDigital Library
- L. Guo, F. Shao, C. Botev, and J. Shanmugasundaram. XRANK: Ranked keyword search over XML documents. In SIGMOD, pages 16--27, 2003. Google ScholarDigital Library
- T. H. Haveliwala. Topic-sensitive pagerank. In WWW, pages 517--526, 2002. Google ScholarDigital Library
- D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, pages 180--184, 1985.Google Scholar
- A. Huang, Q. Xue, and J. Yang. Tuplerank and implicit relationship discovery in relational databases. In WAIM, 2003.Google ScholarCross Ref
- T. Kamishima and J. Fujiki. Clustering orders. In Discovery Science, pages 194--207, 2003.Google ScholarCross Ref
- W. KieBling. Foundations of preferences in database systems. In VLDB, pages 311--322, 2002. Google ScholarDigital Library
- J. Kleinberg, C. Papadimitriou, and P. Raghavan. Segmentation problems. In STOC, pages 473--482, 1998. Google ScholarDigital Library
- G. Koutrika and Y. Ioannidis. Constrained optimalities in query personalization. In SIGMOD, pages 73--84, 2005. Google ScholarDigital Library
- G. Koutrika and Y. E. Ioannidis. Personalization of queries in database systems. In ICDE, pages 597--608, 2004. Google ScholarDigital Library
- G. Koutrika and Y. E. Ioannidis. Personalized queries under a generalized preference model. In ICDE, pages 841--852, 2005. Google ScholarDigital Library
- K. Kummamuru, R. Krishnapuram, and R. Agrawal. On learning assymetric dissimilarity measures. In ICDM, 2005. Google ScholarDigital Library
- D. Papadias, Y. Tao, G. Fu, and B. Seeger. An optimal and progressive algorithm for skyline queries. In SIGMOD, pages 467--478, 2003. Google ScholarDigital Library
- M. Richardson and P. Domingos. The intelligent surfer: Probabilistic combination of link and content information in pagerank. In NIPS, pages 1441--1448, 2001.Google ScholarDigital Library
- M. Schultz and T. Joachims. Learning a distance metric from relative comparisons. In NIPS, 2003.Google ScholarDigital Library
- M. Yannakakis. Edge-deletion problems. SIAM J. Comput., 10(2):297--309, 1981.Google ScholarDigital Library
Index Terms
- Context-sensitive ranking
Recommendations
Context-sensitive ranking for document retrieval
SIGMOD '11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of dataWe study the problem of context-sensitive ranking for document retrieval, where a context is defined as a sub-collection of documents, and is specified by queries provided by domain-interested users. The motivation of context-sensitive search is that ...
A new ranking procedure by incomplete pairwise comparisons using preference subsets
A method for ranking of alternatives or objects and its extensions by incomplete pairwise comparisons using random set theory are proposed in the paper. The main feature of the method is that it allows us to deal with comparisons of arbitrary groups of ...
Partial Ranking by Incomplete Pairwise Comparisons Using Preference Subsets
BELIEF 2014: Proceedings of the Third International Conference on Belief Functions: Theory and Applications - Volume 8764In multi-criteria decision making the decision maker need to assign weights to criteria for evaluation of alternatives, but decision makers usually find it difficult to assign precise weights to several criteria. On the other hand, decision makers may ...
Comments