Maintenance of top-k materialized views
Tóm tắt
In this paper we present results on the problem of maintaining materialized top-k views and provide results in two directions. The first problem we tackle concerns the maintenance of top-k views in the presence of high deletion rates. We provide a principled method that complements the inefficiency of the state of the art independently of the statistical properties of the data and the characteristics of the update streams. The second problem we have been concerned with has to do with the efficient maintenance of multiple top-k views in the presence of updates to their base relation. To this end, we provide theoretical guarantees for the nucleation (practically, inclusion) of a view with respect to another view and the reflection of this property to the management of updates. We also provide algorithmic results towards the maintenance of a large number of views, via their appropriate structuring in hierarchies of views.
Tài liệu tham khảo
Baikousi, E., Vassiliadis, P.: Tuning the top-k view update process. In: 3rd Multidisciplinary Workshop on Advances in Preference Handling (M-Pref 2007), held in conjunction with VLDB 2007, Vienna, Austria, 23 September 2007
Das, G., Gunopulos, D., Koudas, N., Tsirogiannis, D.: Answering top-k queries using views. In: Proc. of the 32nd VLDB Conference, pp. 451–462, Seoul, Korea, 2006
DeGroot, M.H., Schervish, M.J.: Probability and Statistics. Addison-Wesley, Reading (2002)
Fagin, R.: Combining fuzzy information from multiple systems. In: Proc. of the 15th ACM Symposium on Principles of Database Systems, pp. 216–226, Montreal, Canada, 1996
Fagin, R.: Fuzzy queries in multimedia database systems. In: Proc. of the 17th ACM Symposium on Principles of Database Systems, pp. 1–10, Seattle, USA, 1998
Fagin, R., Lotem, A., Naor, M.: Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci. 66(4), 614–656 (2003)
Graefe, G.: Dynamic query evalutation plans: Some course corrections. Bull. Tech. Comm. Data Eng. 23(2), 3–6 (2000)
Güntzer, U., Balke, W.-T., Kießling, W.: Optimizing multi-feature queries for image databases. In: Proc. of the 26th VLDB Conference, pp. 419–428, Cairo, Egypt, 2000
Hristidis, V., Papakonstantinou, Y.: Algorithms and applications for answering ranked queries using ranked views. VLDB J. 13(1), 49–70 (2004)
Hristidis, V., Koudas, N., Papakonstantinou, Y.: PREFER a system for the efficient execution of multi-parametric ranked queries. In: Proc. of the ACM Special Interest Group on Management of Data Conference (SIGMOD), pp. 259–270, Santa Barbara, USA, 2001
Kossmann, D.: The state of the art in distributed query processing. ACM Comput. Surv. 32(4), 422–469 (2000)
Marian, A., Bruno, N., Gravano, L.: Evaluating top-k queries over web-accessible databases. ACM Trans. Database Syst. (TODS) 29(2), 319–362 (2004)
Mouratidis, K., Bakiras, S., Papadias, D.: Continuous monitoring of top-k queries over sliding windows. In: Proc. of the ACM Special Interest Group on Management of Data Conference (SIGMOD), pp. 635–646, Chicago, Illinois, USA, 2006
Nepal, S., Ramakrishna, M.V.: Query processing issues in image (multimedia) databases. In: Proc. of the 15th International Conference on Data Engineering (ICDE), pp. 22–29, Sydney, Australia, 1999
Papadias, D., Tao, Y., Fu, G., Seeger, B.: Progressive skyline computation in database systems. ACM Trans. Database Syst. (TODS) 30(1), 41–82 (2005)
Schlossnagle, T.: Dissecting today’s Internet traffic spikes. Posted on 15 January 2009 at http://omniti.com/seeds/dissecting-todays-internet-traffic-spikes
Trivedi, K.S.: Probability and Statistics with Reliability, Queuing and Computer Science Applications. Wiley, New York (2002)
Vlachou, A., Doulkeridis, C., Norvag, K., Vazirgiannis, M.: On efficient top-k query processing in highly distributed environments. In: Proc. of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 2008
Yi, K., Yu, H., Yang, J., Xia, G., Chen, Y.: Efficient maintenance of materialized top-k views. In: Proceedings of the 19th International Conference on Data Engineering (ICDE), pp. 189–200, Bangalore, India, 2003
Zhao, K., Tao, Y., Zhou, S.: Efficient top-k processing in large-scaled distributed environments. Data Knowl. Eng. 63, 315–335 (2007)