Constrained optimalities in query personalization

ABSTRACT

Personalization is a powerful mechanism that helps users to cope with the abundance of information on the Web. Database query personalization achieves this by dynamically constructing queries that return results of high interest to the user. This, however, may conflict with other constraints on the query execution time and/or result size that may be imposed by the search context, such as the device used, the network connection, etc. For example, if the user is accessing information using a mobile phone, then it is desirable to construct a personalized query that executes quickly and returns a handful of answers. Constrained Query Personalization (CQP) is an integrated approach to database query answering that dynamically takes into account the queries issued, the user's interest in the results, response time, and result size in order to build personalized queries. In this paper, we introduce CQP as a family of constrained optimization problems, where each time one of the parameters of concern is optimized while the others remain within the bounds of range constraints. Taking into account some key (exact or approximate) properties of these parameters, we map CQP to a state search problem and provide several algorithms for the discovery of optimal solutions. Experimental results demonstrate the effectiveness of the proposed techniques and the appropriateness of the overall approach.

REFERENCES

• 1: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, Top-k selection queries over relational databases: Mapping strategies and performance evaluation, ACM Transactions on Database Systems (TODS), v.27 n.2, p.153-187, June 2002 [doi>10.1145/568518.568519]
• 2: Surajit Chaudhuri , Luis Gravano, Evaluating Top-k Selection Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.397-410, September 07-10, 1999
• 3: Sumit Ganguly , Waqar Hasan , Ravi Krishnamurthy, Query optimization for parallel execution, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.9-18, June 02-05, 1992, San Diego, California, United States
• 4: Glover F. Tabu Search - Part I. ORSA Journal on Computing, Vol. 1, pp. 190--206, 1989.
• 5: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 6: F. Ilyas , G. Aref , K. Elmagarmid, Supporting top-k join queries in relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.207-221, September 2004 [doi>10.1007/s00778-004-0128-2]
• 7: Internet Movies Database. Available at www.imdb.com.
• 8: George Karypis, Evaluation of Item-Based Top-N Recommendation Algorithms, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502627]
• 9: Kellerer, H., Pferschy, U., Pisinger, D. Knapsack Problems. Springer-Verlag, 2003.
• 10: Kirkpatrick, Gelatt, C. D., Vecchi, M. P. Optimization by Simulated Annealing, Science 220, 4598, 671--680, 1983.
• 11: Donald Kossmann , Konrad Stocker, Iterative dynamic programming: a new class of query optimization algorithms, ACM Transactions on Database Systems (TODS), v.25 n.1, p.43-82, March 2000 [doi>10.1145/352958.352982]
• 12: 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
• 13: Fang Liu , Clement Yu , Weiyi Meng, Personalized web search by mapping user queries to categories, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584884]
• 14: James Pitkow , Hinrich Schütze , Todd Cass , Rob Cooley , Don Turnbull , Andy Edmonds , Eytan Adar , Thomas Breuel, Personalized search, Communications of the ACM, v.45 n.9, September 2002 [doi>10.1145/567498.567526]
• 15: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]