Georgia Koutrika
Yannis Ioannidis
Skip Abstract Section
Abstract
People's preferences are expressed at varying levels of granularity and detail as a result of partial or imperfect knowledge. One may have some preference for a general class of entities, for example, liking comedies, and another one for a fine-grained, specific class, such as disliking recent thrillers with Al Pacino. In this article, we are interested in capturing such complex, multi-granular preferences for personalizing database queries and in studying their impact on query results. We organize the collection of one's preferences in a preference network (a directed acyclic graph), where each node refers to a subclass of the entities that its parent refers to, and whenever they both apply, more specific preferences override more generic ones. We study query personalization based on networks of preferences and provide efficient algorithms for identifying relevant preferences, modifying queries accordingly, and processing personalized queries. Finally, we present results of both synthetic and real-user experiments, which: (a) demonstrate the efficiency of our algorithms, (b) provide insight as to the appropriateness of the proposed preference model, and (c) show the benefits of query personalization based on composite preferences compared to simpler preference representations.
- Agrawal, R., Rantzau, R., and Terzi, E. 2006. Context-Sensitive ranking. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 383--394. Google Scholar
Digital Library
- Agrawal, R. and Wimmers, E. 2000. A framework for expressing and combining preferences. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Google ScholarDigital Library
- Aho, A., Sagiv, Y., and Ullman, J. D. 1979. Equivalence of relational expressions. SIAM J. Comput. 8, 2, 218--246.Google ScholarCross Ref
- Avnur, R. and Hellerstein, J. M. 2000. Eddies: Continuously adaptive query processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Google ScholarDigital Library
- Balabanovic, M. and Shoham, Y. 1997. Fab: Content-Based, collaborative recommendation. Comm. ACM 40, 3, 66--72. Google ScholarDigital Library
- Balke, W.-T., Guntzer, U., and Lofi, C. 2007. User interaction support for incremental refinement of preference-based queries. In Proceedings of the IEEE International Conference on Research Challenges in Information Science (RCIS). 511--523.Google Scholar
- Borzsonyi, S., Kossmann, D., and Stocker, K. 2001. The skyline operator. In Proceedings of the International Conference on Data Engineering (ICDE'01). 421--430. Google ScholarDigital Library
- Bruno, N., Chaudhuri, S., and Gravano, L. 2002. Top-k selection queries over relational databases: Mapping strategies and performance evaluation. ACM Trans. Datab. Syst. 27, 2, 153--187. Google ScholarDigital Library
- Chang, K. and Hwang, S. 2002. Minimal probing: Supporting expensive predicates for top-k queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Google ScholarDigital Library
- Chekuri, C. and Rajaraman, A. 1997. Conjunctive query containment revisited. In Proceedings of the International Conference on Database Theory (ICDT'97). Google ScholarDigital Library
- Chomicki, J. 2003. Preference formulas in relational queries. ACM Trans. Datab. Syst. 28, 4, 427--466. Google ScholarDigital Library
- Chomicki, J. 2004. Semantic optimization of preference queries. In Proceedings of the International Symposium on Applications of Constraint Databases. 133--148.Google ScholarCross Ref
- Cohen, W. W., Schapire, R. E., and Singer, Y. 1998. Efficiently mining frequent trees in a forest. Adv. Neural Inform. Process. Syst. 10.Google Scholar
- Collins, A. and Quillian, M. 1969. Retrieval time from semantic memory. J. Verbal Learn. Verbal Behav. 8, 240--247.Google ScholarCross Ref
- Cuppens, D. and De Molombe, R. 1989. How to recognize interesting topics to provide cooperative answers. Inform. Syst. 14, 2, 163--173. Google ScholarDigital Library
- Das, A., Datar, M., Garg, A., and Rajaram, S. 2007. Google news personalization: Scalable online collaborative filtering. In Proceedings of the International World Wide Web Conference (WWW'07). 271--280. Google ScholarDigital Library
- Fagin, R., Kumar, R., and Sivakumar, D. 2003. Comparing top k lists. SIAM J. Discrete Math. 17, 1, 134--140. Google ScholarDigital Library
- Fishburn, P. 1999. Preference structures and their numerical representations. Theor. Comput. Sci. 217, 359--383. Google ScholarDigital Library
- Gaasterland, T., Godfrey, P., and Minker, J. 1992. An overview of cooperative query answering. J. Intell. Inf. Syst. 1, 2, 123--157.Google ScholarCross Ref
- Hansson, S. O. 2001. Preference logic. In Handbook of Philosophical Logic 8, D. Gabbay, Ed.Google Scholar
- Holland, S., Ester, M., and Kiessling, W. 2003. Preference mining: A novel approach on mining user preferences for personalized applications. In Proceedings of the European Conference on Principles of Data Mining and Knowledge Discovery (PKDD'03). 204--216.Google Scholar
- Holland, S. and Kiessling, W. 2004. Situated preferences and preference repositories for personalized database applications. In Proceedings of the ER Workshops. 511--523.Google Scholar
- Hristidis, V., Koudas, N., and Papakonstantinou, Y. 2001. PREFER: A system for the efficient execution of multiparametric ranked queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Google ScholarDigital Library
- Ilyas, I., Shah, R., Aref, W., Vitter, J., and El Magarmid, A. 2004. Rank-Aware query optimization. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Google ScholarDigital Library
- Jiang, B., Pei, J., Lin, X., Cheung, D. W., and Han, J. 2008. Mining preferences from superior and inferior examples. In Proceedings of the International SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'08). 390--398. Google ScholarDigital Library
- Joachims, T. 2002. Optimizing search engines using clickthrough data. In Proceedings of the International SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'02). Google ScholarDigital Library
- Joachims, T., Freitag, D., and Mitchell, T. 1997. Webwatcher: A tour guide for the World Wide Web. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI'97).Google Scholar
- Kendall, M. and Gibbons, J. D. 1990. Rank Correlation Methods. Edward Arnold, London.Google Scholar
- Kiessling, W. 2002. Foundations of preferences in database systems. In Proceedings of the International Conference on Very Large Databases (VLDB'02). 311--322. Google ScholarDigital Library
- Kiessling, W. and Kostler, W. 2002. Preference SQL-Design, implementation, experiences. In Proceedings of the International Conference on Very Large Databases (VLDB'02). Google ScholarDigital Library
- Kossmann, D., Ramsak, F., and Rost, S. 2002. Shooting stars in the sky: An online algorithm for skyline queries. In Proceedings of the International Conference on Very Large Databases (VLDB'02). 275--286. Google ScholarDigital Library
- Koutrika, G. 2006. Personalization of structured queries with personal and collaborative preferences. In Proceedings of the ECAI Workshop about Advances on Preference Handling.Google Scholar
- Koutrika, G., Bercovitz, B., and Garcia-Molina, H. 2009. FlexRecs: Expressing and combining flexible recommendations. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Google ScholarDigital Library
- Koutrika, G. and Ioannidis, Y. 2004. Personalization of queries in database systems. In Proceedings of the International Conference on Data Engineering (ICDE'04). 597--608. Google ScholarDigital Library
- Koutrika, G. and Ioannidis, Y. 2005a. Constrained optimalities in query personalization. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 73--84. Google ScholarDigital Library
- Koutrika, G. and Ioannidis, Y. 2005b. Personalized queries under a generalized preference model. In Proceedings of the International Conference on Data Engineering (ICDE'05). Google ScholarDigital Library
- LaCroix, M. and Lavency, P. 1987. Preferences: Putting more knowledge into queries. In Proceedings of the International Conference on Very Large Databases (VLDB'87). 217--225. Google ScholarDigital Library
- Lee, J., Wonyou, G., Wonhuang, S., Selk, J., and Balke, W.-T. 2008. Optimal preference elicitation for skyline queries over categorical domains. In Proceedings of the International Conference on Database and Expert Systems Applications (DEXA'08). 610--624. Google ScholarDigital Library
- Linden, G., Smith, B., and York, J. 2003. Amazon.com recommendations: Item-to-Item collaborative filtering. IEEE Internet Computing. Google ScholarDigital Library
- Liu, F., Yu, C., and Meng, W. 2004. Personalized Web search for improving retrieval effectiveness. IEEE Trans. Knowl. Data Engin. 16, 1. Google ScholarDigital Library
- Miah, M., Das, G., Hristidis, V., and Mannila, H. 2008. Standing out in a crowd: Selecting attributes for maximum visibility. In Proceedings of the International Conference on Data Engineering (ICDE'08). 356--365. Google ScholarDigital Library
- Papadias, D., Tao, Y., Fu, G., and Seeger, B. 2003. An optimal and progressive algorithm for skyline queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 467--478. Google ScholarDigital Library
- Pei, J., Jiang, B., Lin, X., and Yuan, Y. 2007. Probabilistic skylines on uncertain data. In Proceedings of the International Conference on Very Large Databases (VLDB'07). 15--26. Google ScholarDigital Library
- Pei, J., Jin, W., Ester, M., and Tao, Y. 2005. Catching the best views of skyline: A semantic approach based on decisive subspaces. In Proceedings of the Internaional Conference on Very Large Databases (VLDB'05). 253--264. Google ScholarDigital Library
- Pitkow, J. E., Schutze, H., Cass, T. A., Cooley, R., Turnbull, D., Edmonds, A., Adar, E., and Breuel, T. M. 2002. Personalized search. Comm. ACM 45, 9, 50--55. Google ScholarDigital Library
- Sarkas, N., Das, G., Koudas, N., and Tung, A. K. H. 2008. Categorical skylines for streaming data. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 239--250. Google ScholarDigital Library
- Satzger, B., Endres, M., and Kiessling, W. 2006. A preference-based recommendation system. In Proceedings of the International Conference on Electronic Commerce and Web Technologies (ECWeb'06). Google ScholarDigital Library
- Stefanidis, K. and Pitoura, E. 2008. Fast contextual preference scoring of database tuples. In Proceedings of the International Conference on Extending Database Technology (EDBT'08). 344--355. Google ScholarDigital Library
- Stefanidis, K., Pitoura, E., and Vassiliadis, P. 2007. Adding context to preferences. In Proceedings of the International Conference on Data Engineering (ICDE'07).Google Scholar
- Tao, Y., Hristidis, V., Papadias, D., and Papakonstantinou, Y. 2007. Branch-and-Bound processing of ranked queries. Inform. Syst. 32, 3, 424--445. Google ScholarDigital Library
- van Bunningen, A., Feng, L., and Apers, P. M. G. 2006. A context-aware preference model for database querying in an ambient intelligent environment. In Proceedings of the International Conference on Database and Expert Systems Applications (DEXA'06). 33--43. Google ScholarDigital Library
- Vlachou, A., Doulkeridis, C., Kotidis, Y., and Vazirgiannis, M. 2007. SKYPEER: Efficient subspace skyline computation over distributed data. In Proceedings of the International Conference on Data Engineering (ICDE'07). 416--425.Google Scholar
- Wellman, M. and Doyle, J. 1991. Preferential semantics for goals. In Proceedings of the National Conference on Artificial Intelligence. 698--703.Google Scholar
- Wong, R. C -W., Pei, J., Fu, A. W.-C., and Wang, K. 2007. Mining favorable facets. In Proceedings of the International SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'07). 804--813. Google ScholarDigital Library
- Xin, D. and Han, J. 2008. P-Cube: Answering preference queries in multi-dimensional space. In Proceedings of the International Conference on Data Engineering (ICDE'08). 1092--1100. Google ScholarDigital Library
- Yiu, M. L., Dai, X., Mamoulis, N., and Vaitis, M. 2007. Top-k spatial preference queries. In Proceedings of the International Conference on Data Engineering (ICDE'07). 1076--1085.Google Scholar
- Zaki, M. J. 2005. Efficiently mining frequent trees in a forest. Inform. Syst. 17, 8, 1021--1035. Google ScholarDigital Library
Index Terms
- Personalizing queries based on networks of composite preferences
Recommendations
On Utilizing Qualitative Preferences in Web Service Composition: A CP-net Based Approach
SERVICES '08: Proceedings of the 2008 IEEE Congress on Services - Part ITraditional approaches to Web service composition have focused on either generating compositions that match the structural and functional requirements of the user, or using quantitative optimization techniques over non-functional attributes. However, ...
A Clustering Approach for Personalizing Diversity in Collaborative Recommender Systems
UMAP '17: Proceedings of the 25th Conference on User Modeling, Adaptation and PersonalizationMuch of the focus of recommender systems research has been on the accurate prediction of users' ratings for unseen items. Recent work has suggested that objectives such as diversity and novelty in recommendations are also important factors in the ...
Personalizing the settings for Cf-based recommender systems
RecSys '10: Proceedings of the fourth ACM conference on Recommender systemsIn this paper, we propose a new method for collaborative filtering (CF)-based recommender systems. Traditional CF-based recommendation algorithms have applied constant settings such as a reference group (neighborhood) size and a significance level to ...
Comments