Here is a paper assignment I had to do for the "Query and Retrieval" course in 2011. The topic is "Index Structures for Multimedia Databases" which I found very interesting. I initially thought that there wouldn't be so much research going on in the field, but I was proved wrong.
Index Structures for Multimedia Databases
ABSTRACT
In this document we address the issue of index structures for multimedia objects. Video, audio and other inhomogeneous formats contain such amount of varying information that cannot be efficiently organized using conventional database techniques. However, fast accessing, response times and efficient sharing are keys issues when it comes to multimedia, due to their rapidly growing commercial and practical applications. An overview of the current drawbacks and limitations of typical index structures will be initially discussed. We will also investigate in which ways the multimedia storage issue can be transformed to the high-dimensional indexing problem. Most of the paper though is focused in presenting a series of generalized 1D and 2D structures while also algorithms specially designed for complicated data.
After I handed in the assignment I stumbled upon other methods such as VA-index; overall the paper contains lots of information and is well written.
1. Kosch H. and Doller M. (2003) Multimedia Database Systems: Where are we now?, CRC Press. ISBN: 0-849-31854-8.
2. Saake G. (2010) Multimedia Retrieval in Databases: Foundation and Index Structures
3. Jagadish H. V. (1991) A Retrieval technique for similar shapes, SIGMOD, New York.
4. Huang Z. (2003) Individual Study Option: Scalable Database Indexing, ISO report.
5. Assent I. and Seidl T. (2006) Efficient multi-step query processing for EMD-based similarity, Dagstuhl Seminar Proceedings 06171
6. Ciaccia P. Indexing Multimedia Databases, Lecture slides
7. Weber R. et al (1998) A Quantitative Analysis and Performance study for similarity search methods in High dimensional Spaces, Proceedings of the 24th VLDB conference, New York.
8. Berchtold S. et al. (1996) The X-tree: An index structure for High-dimensional data, Proceedings of the 22nd VLDB conference, Mumbai.
9. White D. and Jain R. (1996) Similarity Indexing with SS-tree, Proceedings of the 12th ICDE conference.
10. Katayama N. (1997) The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries, Proceedings of ACM SIGMOD.
11. Ciaccia P. et al. (1997) M-tree: An efficient Access method for similarity search in metric spaces, Proceedings of the 23rd VLDB, Athens.
12. Yunshuang H. et al. (2002) An investigation of using k-d tree to improve image retrieval accuracy, DICTA, Melbourne.
13. Henrich A. et al. (1989) The LSD tree: spatial access to multidimensional point and non point objects, Proceedings of the 15th VLDB, Amsterdam.
14. Chakrabarti K. and Mehrotra, S. (1999) The Hybrid Tree: an index structure for high dimensional feature spaces, Proceedings of 15th ICDE, Sydney.
15. Multimedia Analysis and Retrieval System (MARS) www-db.ics.uci.edu/pages/research/mars
16. Chen W.K. (2005) The electrical engineering handbook. Academic Press.
17. Faloutsos C. and Lin K. (1995) FastMap: A fast algorithm for indexing, data mining and visualization of traditional and multimedia databases, Proceedings of SIGMOD, San Jose.
18. Wu L. and Faloutsos C. (2002) Making every bit count: fast nonlinear axis scaling. Proceedings of the 8th ACM SIGKDD, New York.
19. Seidl T. and Kriegel H.P (1997), Efficient user-adaptable similarity search in large multimedia databases, Proceedings of the 23rd VLDB, Athens.
20. Ouksel M. and Scheuermann P. (1983) Storage of multidimensional linear dynamic hashing, Proceedings of the 2nd ACM SIGACT-SIGMOD, New York.
21. Kriegel H. and Seeger B. (1986) Multidimensional order preserving linear hashing with partial expansions, Proceedings of ICDT, Rome.
22. Kriegel H. and Seeger B. (1989) Multidimensional quantile hashing is very efficient for non uniform distributions, Information Sciences, Volume 48, Issue 2, Pages 99-117
23. BerchTold et al. (1998) The pyramid technique: towards breaking the curse of dimensionality, Proceedings of the ACM SIGMOD, New York.
24. Mokbel M.F. et al (2002) Performance of Multi-dimensional space-filling curves. Proceedings of GIS, Virginia.
25. MPEG-7 Multimedia Database, www.dimis.fim.uni-passau.de/iris/index.php?view=mpeg7
26. GiST: Generalised Search Tree gist.cs.berkeley.edu/gist1.html
27. Arjen P. de Vries (1998) Mirror: Multimedia Query Processing in Extensible Databases, in 14th Twente Workshop on Language Technology. Language Technology in Multimedia Information Retrieval, Enschede, The Netherlands.
28. Kernsten M. (1998) A feature database for Multimedia Objects.
29. Chalhoub G. et al. (2004) Towards fully functional multimedia DBMS, Journal of Digital Information Management Volume 2, 3, Pages 116-121
30. Oria V. et al. (2004) Foundation of the DISIMA image query languages, Multimedia Tools and Applications, Volume 23 Issue 3, USA
31. Lin S. et al. (2001) An extensible hash for multi-precision similarity querying of image databases, Proceedings of the 27th VLDB, San Francisco.
32. Niu Y. et al. (1997) 2D-h Trees: An Index Scheme for Content-Based Retrieval of Images in Multimedia Systems, ICIPS 97, Beijing.
33. Niu Y. et al () 2-d-s : an index structure for content based retrieval of images, Proceedings of the
34. Doller M. (2006) MPEG-7 meets multimedia database systems, JUKM, Volume 1, Number 1, Pages 18-25.
35. Scheer O. et al (2008) User requirements for Multimedia indexing and retrieval of unedited Audio-Visual Footage – RUSHES, IEEE
36. Alexander A. and Piotr I. (2006) Near-Optimal Hashing Algortithms for Approximate Nearest Neighbor in High Dimensions, Proceedings of FOCS
37. Zhang S. et al. (2010), Building Contextual Visual Vocabulary for large-scale image applications, Proceedings of the international conference on Multimedia..
38. Zhou W et al. (2010) Spatial coding for large scale partial-duplicate web image search, Proceedings of the international conference on Multimedia.
39. Shang L. et al. (2010)Real-time Large Scale Near-duplicate Web Video Retrieval, Proceedings of the international conference on Multimedia
