Context-sensitive ranking

ABSTRACT

Contextual preferences take the form that item i1 is preferred to item i₂ 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.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Edward L. Wimmers, A framework for expressing and combining preferences, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.297-306, May 15-18, 2000, Dallas, Texas, United States
• 3: S. Agrawal, S. Chaudhuri, G. Das, and A. Gionis. Automated ranking of database query results. In CIDR, 2003.
• 4: A. Balmin, V. Hristidis, and Y. Papakonstantinou. Objectrank: Authority-based keyword search in databases. In VLDB, pages 564--575, 2004.
• 5: Bonnie Berger , Peter W. Shor, Approximation alogorithms for the maximum acyclic subgraph problem, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.236-243, January 22-24, 1990, San Francisco, California, United States
• 6: Arvind Hulgeri , Charuta Nakhe, Keyword Searching and Browsing in Databases using BANKS, Proceedings of the 18th International Conference on Data Engineering, p.431, February 26-March 01, 2002
• 7: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 8: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 9: S. Chaudhuri, G. Das, V. Hristidis, and G. Weikum. Probabilistic ranking of database query results. In VLDB, pages 888--899, 2004.
• 10: Jan Chomicki, Preference formulas in relational queries, ACM Transactions on Database Systems (TODS), v.28 n.4, p.427-466, December 2003 [doi>10.1145/958942.958946]
• 11: M. Chrobak, C. Kenyon, and N. E. Young. The reverse greedy algorithm for the metric k-median problem. In COCOON, 2005.
• 12: William W. Cohen , Robert E. Schapire , Yoram Singer, Learning to order things, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.451-457, July 1998, Denver, Colorado, United States
• 13: P. Diaconis and R. Graham. Spearman's footrule as a measure of disarray. J. of the Royal Statistical Society, 39(2):262--268, 1977.
• 14: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 15: Ronald Fagin , Ravi Kumar , Mohammad Mahdian , D. Sivakumar , Erik Vee, Comparing and aggregating rankings with ties, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055568]
• 16: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 17: Ronald Fagin , Ravi Kumar , D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872795]
• 18: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 19: F. Geerts, H. Mannila, and E. Terzi. Relational link-based ranking. In VLDB, pages 552--563, 2004.
• 20: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 21: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 22: D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, pages 180--184, 1985.
• 23: A. Huang, Q. Xue, and J. Yang. Tuplerank and implicit relationship discovery in relational databases. In WAIM, 2003.
• 24: T. Kamishima and J. Fujiki. Clustering orders. In Discovery Science, pages 194--207, 2003.
• 25: W. KieBling. Foundations of preferences in database systems. In VLDB, pages 311--322, 2002.
• 26: Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276860]
• 27: Georgia Koutrika , Yannis Ioannidis, Constrained optimalities in query personalization, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066167]
• 28: Georgia Koutrika , Yannis Ioannidis, Personalization of Queries in Database Systems, Proceedings of the 20th International Conference on Data Engineering, p.597, March 30-April 02, 2004
• 29: Georgia Koutrika , Yannis Ioannidis, Personalized Queries under a Generalized Preference Model, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.841-852, April 05-08, 2005 [doi>10.1109/ICDE.2005.106]
• 30: Krishna Kummamuru , Raghu Krishnapuram , Rakesh Agrawal, On Learning Asymmetric Dissimilarity Measures, Proceedings of the Fifth IEEE International Conference on Data Mining, p.697-700, November 27-30, 2005 [doi>10.1109/ICDM.2005.107]
• 31: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, An optimal and progressive algorithm for skyline queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872814]
• 32: M. Richardson and P. Domingos. The intelligent surfer: Probabilistic combination of link and content information in pagerank. In NIPS, pages 1441--1448, 2001.
• 33: M. Schultz and T. Joachims. Learning a distance metric from relative comparisons. In NIPS, 2003.
• 34: M. Yannakakis. Edge-deletion problems. SIAM J. Comput., 10(2):297--309, 1981.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms, Experimentation

Keywords:
preferences, ranking