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. Bruno, N., Chaudhuri, S., Gravano, L. Top- k Selection Queries over Relational Databases: Mapping Strategies and Performance Evaluation. ACM TODS, 27(2), 153--187, 2002.
2. Chaudhuri, S., Gravano, L. Evaluating Top-k Selection Queries. Proc. of the 25th Int'l Conf. On VLDB, 1999.
3. Ganguly, S., Hasan, W., Krishnamurthy, R. Query Optimization for Parallel Execution. Proc. Of the ACM Int'l Conf. On Management of Data, SIGMOD, 1992.
4. Glover F. Tabu Search - Part I. ORSA Journal on Computing, Vol. 1, pp. 190--206, 1989.
5. Goldberg D. Genetic Algorithms in Search and Machine Learning. Reading, Addison Wesley, 1989.
6. Ilyas, I., Aref, W. G., Elmagarmid, A. Supporting top-k join queries in relational databases. VLDB J. 13(3): 2004.
7. Internet Movies Database. Available at www.imdb.com.
8. Karypis, G. Evaluation of Item-Based Top-N Recommendation Algorithms. Proc. of CIKM, 247--254, 2001.
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. Kossmann, D., Stocker, K. Iterative Dynamic Programming: A New Class of Query Optimization Algorithms. ACM TODS, 25(1), 2000, 43--82.
12. Koutrika, G. Ioannidis, Y. Personalization of Queries in Database systems. Proc. of ICDE, 2004.
13. Liu F., Yu C., Meng W. Personalized Web Search by Mapping User Queries to Categories. Proc. of CIKM, 2002.
14. Pitkow, J., Schutze, H., et al. Personalized Search. Comm. of the ACM, 45(9), 2002.
15. Selinger, P. G., Astrahan, M. M., Lorie, R. A., Price, T. G. Access Path Selection in a Relational Database Management System. Proc. of SIGMOD, 1979.

• Information systems

  • Data management systems

    • Database management system engines

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory