Video query processing in the VDBMS testbed for video database research

ABSTRACT

The increased use of video data sets for multimedia-based applications has created a demand for strong video database support, including efficient methods for handling the content-based query and retrieval of video data. Video query processing presents significant research challenges, mainly associated with the size, complexity and unstructured nature of video data. A video query processor must support video operations for search by content and streaming, new query types, and the incorporation of video methods and operators in generating, optimizing and executing query plans. In this paper, we address these query processing issues in two contexts, first as applied to the video data type and then as applied to the stream data type. We first present the query processing functionality of the VDBMS video database management system as a framework designed to support the full range of functionality for video as an abstract data type. We describe two query operators for the video data type which implement the rank-join and stop-after algorithms. As videos may be considered streams of consecutive image frames, video query processing can be expressed as continuous queries over video data streams. The stream data type was therefore introduced into the VDBMS system, and system functionality was extended to support general data streams. From this viewpoint, we present an approach for defining and processing streams, including video, through the query execution engine. We describe the implementation of several algorithms for video query processing expressed as continuous queries over video streams, such as fast forward, region-based blurring and left outer join. We include a description of the window-join algorithm as a core operator for continuous query systems, and discuss shared execution as an optimization approach for stream query processing.

References

1. Aref, W., Catlin, A.C., Elmagarmid, A., Fan, J., Hammad, M., Ilyas, I., Marzouk, M., and Zhu, X. A video database management system for advancing video database research. In Proc. of the Int Workshop on Management Information Systems. Nov 2002. Tempe, Arizona.]]
2. Aref, W., Catlin, A.C., Elmagarmid, A., Fan, J., Guo, J., Hammad, M., Ilyas, I., Marzouk, M., Prabhakar, S., Rezgui, A., Teoh, S., Terzi, E., Tu, Y., Vakali, A. and Zhu, X. A distributed server for continuous media. In Proc. of the 18th Int Conf on Data Engineering. Feb 26-Mar 1 2002. San Jose, California.]]
3. Beckmann, N., Kriegel, H., Schneider, R. and Seeger, B. The R* -tree: an efficient robust access method for points and rectangles. SIGMOD Record, ACM Special Interest Group on Management of Data, 19(2): pp. 322---331. 1990.]]
4. Berchtold, S., Böhm, C., Jagadish, H., Kriegel, H-P. and Sander, J. Independent quantization: An index compression technique for high-dimensional data spaces. In Proc. of the 16th Int Conf on Data Engineering. San Diego, CA. pp. 577--588. February 2000.]]
5. Bertino, E., Elmagarmid, A. and Hacid, M-S. Quality of service in multimedia digital libraries. SIGMOD Record. 30(1), pp. 35--40, March 2003.]]
6. Bertino, E., Hammad, M., Aref, W. and Elmagarmid, A. An access control model for video database systems. In Proc. of the 9th Int Conf on Information and Knowledge Management. pp. 336---343. Nov 2000.]]
7. Bertino, E., Samarati. P. and S. Jajodia. An extended authorization model. IEEE Trans. on Knowledge and Data Engineering. 9(1). pp. 85--101. 1997.]]
8. P. Bonnet , J. E. Gehrke and P. Seshadri. Towards Sensor Database Systems. In Proc. of the 2nd Inter Conf on Mobile Data Management. Jan 2001.]]
9. Michael J. Carey and Donald Kossmann, On saying "Enough already!" in SQL, In Proc. CK SIGMOD. Tucson, Arizona. May 1997.]]
10. Michael J. Carey and Donald Kossmann, Reducing the Braking Distance of an SQL Query Engine, In Proc. CK'98 VLDB. New York, August, 1998.]]
11. Fagin, R., Lotem, A. and Naor, M. Optimal aggregation algorithms for middleware. In Proc. PODS'01 Santa Barbara, CA. May 2001.]]
12. Fan, J., Aref, W., Elmagarmid, A., Hacid, M., Marzouk, M. and Zhu, X. Multiview: Multi-level video content representation and retrieval. Journal of Electrical Imaging, Vol. 10, No. 4, pp. 895--908, October 2001.]]
13. Guntzer, U., Balke, W-T. and Kiessling, W. Optimizing multi-feature queries for image databases. In Proc. Of 26th Int Conf On Very Large Databases. Cairo, Egypt. pp. 419-428. September 10---14 2000.]]
14. Hammad, M., Aref, W., and Elmagarmid, A. Search-based buffer management policies for streaming in continuous media. In Proc. of the IEEE Int Conf on Multimedia and Expo. Lausanne, Switzerland. August 26---29, 2002.]]
15. Hammad, M., Franklin, M., Aref, W. and Elmagarmid. A. Scheduling for shared window joins over data streams. In Proc. of the 29th Int Conf on Very Large Data Bases. 2003.]]
16. Hammad, M., Aref, W. and Elmagarmid. A. Stream Window Join: Tracking Moving Objects in Sensor-Network Databases. In Proc. of the 15th SSDBM Conf. Jul 2003.]]
17. Hellerstein, J., Naughton, J. and Pfeffer, A. Generalized search trees for database systems. In Proc. of 21st Int Conf on Very Large Data Bases. Zurich, Switzerland. September 11--15, 1995.]]
18. Ilyas, I. and Aref, W. SP-GiST: An extensible database index for supporting space partitioning trees. Journal of Intelligent System. 17(2-3). pp. 215--235. 2001.]]
19. Ilyas, I, Aref, W, and Elmagarmid, A. Joining ranked inputs in practice. In Proc. of the 28th Int Conf on Very Large Data Bases. Hong Kong, China. 2002.]]
20. Ilyas, I. and Aref, W. An extensible index for spatial databases. In Proc of the 13th Int Conf on Statistical and Scientific Databases. Virginia. July 2001.]]
21. Katayama, N. and Satoh, S. The SR-tree: An index structure for high dimensional nearest neighbor queries. SIGMOD Record, ACM Special Interest Group on Management of Data, 26(2). 1997.]]
22. S. Madden, M. J. Franklin, J. M. Hellerstein and W. Hong. The design of an acquisitional query processor for sensor networks. In Proc. of the SIGMOD Conf. 2003.]]
23. Nepal, S., Ramakrishna, M. Query processing issues in image (multimedia) databases. In Proc. of the 15th Int Conf on Data Engineering. Sydney, Australia. pp. 22-29. March 23--26, 1999.]]
24. Natsev, A., Chang, Y-C., Smith, J., Li, C-S. and Vitter, J. Supporting incremental join queries on ranked inputs. In Proc. of 27th Int Conf on Very Large Data Bases. Rome, Italy. 2001.]]
25. Seshadri, P. Predator: A resource for database research. SIGMOD Record. 27(1). pp. 16--20. 1998.]]
26. R. T. Snodgrass. Developing Time-Oriented Database Applications in SQL. Morgan Kaufmann, 2000.]]
27. Thomas, M., Carson, C., and Hellerstein, J. Creating a Customized Access Method for Blobworld, In Proc of the 16th Int Conf on Data Engineering. San Diego, CA, March 2000.]]

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

  • Information systems applications

    • Multimedia information systems

      • Multimedia databases

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)