Fast contextual preference scoring of database tuples

ABSTRACT

To provide users with only relevant data from the huge amount of available information, personalization systems utilize preferences to allow users to express their interest on specific pieces of data. Most often, user preferences vary depending on the circumstances. For instance, when with friends, users may like to watch thrillers, whereas, when with their kids, they may prefer to watch cartoons. Contextual preference systems address this challenge by supporting preferences that depend on the values of contextual attributes such as the surrounding environment, time or location. In this paper, we address the problem of finding interesting data items based on contextual preferences that assign interest scores to pieces of data based on context. To this end, we propose a number of pre-processing steps. Instead of pre-computing scores for all data items under all potential context states, we exploit the hierarchical nature of context attributes to identify representative context states. Furthermore, we introduce a method for grouping preferences based on the similarity of the scores that they produce. This method uses a bitmap representation of preferences and scores with various levels of precision that lead to approximate rankings with different degrees of accuracy. We evaluate our approach using both real and synthetic data sets and present experimental results showing the quality of the scores attained using our methods.

REFERENCES

• 1: Internet Movies Database. Available at www.imdb.com.
• 2: MovieLens 2003. Available at www.grouplens.org/data.
• 3: Rakesh Agrawal , Ralf Rantzau , Evimaria Terzi, Context-sensitive ranking, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142517]
• 4: Rakesh Agrawal , Edward L. Wimmers, A framework for expressing and combining preferences, ACM SIGMOD Record, v.29 n.2, p.297-306, June 2000
• 5: S. Amer-Yahia, I. Fundulaki, and L. V. S. Lakshmanan. Personalizing xml search in pimento. In ICDE, pages 906--915, 2007.
• 6: W.-T. Balke, U. Güntzer, and C. Lofi. Eliciting matters - controlling skyline sizes by incremental integration of user preferences. In DASFAA, pages 551--562, 2007.
• 7: W.-T. Balke, U. Güntzer, and C. Lofi. User interaction support for incremental refinement of preference-based queries. In RCIS, pages 209--220, 2007.
• 8: 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]
• 9: Anind K. Dey, Understanding and Using Context, Personal and Ubiquitous Computing, v.5 n.1, p.4-7, February 2001 [doi>10.1007/s007790170019 ]
• 10: Jens-Peter Dittrich , Peter M. Fischer , Donald Kossmann, AGILE: adaptive indexing for context-aware information filters, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066183]
• 11: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 12: 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]
• 13: Ulrich Güntzer , Wolf-Tilo Balke , Werner Kießling, Optimizing Multi-Feature Queries for Image Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.419-428, September 10-14, 2000
• 14: S. Holland and W. Kießling. Situated preferences and preference repositories for personalized database applications. In ER, pages 511--523, 2004.
• 15: Vagelis Hristidis , Nick Koudas , Yannis Papakonstantinou, PREFER: a system for the efficient execution of multi-parametric ranked queries, ACM SIGMOD Record, v.30 n.2, p.259-270, June 2001
• 16: Werner Kießling, Foundations of preferences in database systems, Proceedings of the 28th international conference on Very Large Data Bases, p.311-322, August 20-23, 2002, Hong Kong, China
• 17: 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]
• 18: Georgia Koutrika , Yannis Ioannidis, Personalized Queries under a Generalized Preference Model, Proceedings of the 21st International Conference on Data Engineering, p.841-852, April 05-08, 2005 [doi>10.1109/ICDE.2005.106]
• 19: Y. Li, Z. A. Bandar, and D. McLean. An approach for measuring semantic similarity between words using multiple information sources. IEEE TKDE, 15(4):871--882, 2003.
• 20: George A. Miller, WordNet: a lexical database for English, Communications of the ACM, v.38 n.11, p.39-41, Nov. 1995 [doi>10.1145/219717.219748]
• 21: Query Processing Issues in Image(Multimedia) Databases, Proceedings of the 15th International Conference on Data Engineering, p.22, March 23-26, 1999
• 22: Yannis Stavrakas , Manolis Gergatsoulis, Multidimensional Semistructured Data: Representing Context-Dependent Information on the Web, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.183-199, May 27-31, 2002
• 23: Y. Stavrakas, K. Pristouris, A. Efandis, and T. K. Sellis. Implementing a query language for context-dependent semistructured data. In ADBIS, pages 173--188, 2004.
• 24: K. Stefanidis and E. Pitoura. Approximate contextual preference scoring in digital libraries. In PersDL, pages 60--64, 2007.
• 25: K. Stefanidis, E. Pitoura, and P. Vassiliadis. Modeling and storing context-aware preferences. In ADBIS, pages 124--140, 2006.
• 26: K. Stefanidis, E. Pitoura, and P. Vassiliadis. Adding context to preferences. In ICDE, pages 846--855, 2007.
• 27: A. H. van Bunningen, L. Feng, and P. M. G. Apers. A context-aware preference model for database querying in an ambient intelligent environment. In DEXA, pages 33--43, 2006.