Fast Index Filtering in Vector Approximation File

• Autorzy: Skarbek W. , Sikora T. , Galinski G.
• Języki publikacji: EN

Abstrakty

EN

Several fast filtering attributes are analysed for vector interval (cell) pruning while querying the vector approximation file. Beside distance range, sum and median features their deviation forms are introduced. Range and K-NN queries are considered and appropriate acceptance intervals are designed. The impact of feature space dimensionality on index design is discussed, too.

Słowa kluczowe

EN

multidimensional indexing; index filtering; vector interval; vector approximation file

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 61, nr 3,4
• Strony: 335--349
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Skarbek W.

• Faculty of Electronics and Information Technology, Warsaw University of Technology, Poland

autor

Sikora T.

• Communications Systems Department, Technical University of Berlin, Germany

autor

Galinski G.

• Faculty of Electronics and Information Technology, Warsaw University of Technology, Poland

Bibliografia

• [1] Berchtold S., Boehm C, Kriegel H.,-P., The Pyramid Technique: Towards Breaking the Curse of Dimensionality, Proc. ACM SIGMOD, Int. Conf. on Management of Data, 1998.
• [2] Berchtold S., Keim D.A., Kriegel H.,-P., The X-Tree: An Index structure for High-Dimnsional Data, Proc. on the 22nd VLDB Conference, Bombay, India, 1996.
• [3] Blott, S., Weber, R., A Simple Vector Approximation File for Similarity Search in High-dimensional Vector Spaces, Technical Report 19, ESPRIT project HERMES (no. 9141), 1997.
• [4] Ciacia P., Patella M., Zezula P., M-tree: An efficient access method for similarity search in metric spaces, Proc. on the 23rd VLDB Conference, 1997.
• [5] Ferhatosmanoglu, H., Tuncel, E., Agrawal, D., El Abbadi, A., Vector approximation based indexing for nonuniform high dimensional data sets, Proc. 9th ACM Int. Conf. on Information and Knowledge Management, 2000
• [6] Galinski, G., Skarbek, W., Motion trajectory representations for efficient storage and search, Proc. SPIE vol. 5242, Internet Multimedia Management Systems IV - ITCom'2003, Orlando FL, USA, 2003.
• [7] Guttman, A., R-trees: A dynamic index structure for spatial searching, Proc. ACM SIGMOD Int. Conf. on Management of Data, 1984.
• [8] Heisterkamp, D., Peng, J., Kernel VA-Files for Nearest Neighbor Search in Large Image Databases, Proc. 13th Int. Conf. on Artificial Neural Networks/10th Int. Conf. on Neural Information Processing, Istanbul, Turkey, 2003.
• [9] ISO/IEC 15938-x, JTC1/SC29AVG11, Multimedia content description interface, the MPEG-7 standard, ISO/IEC, 2002.
• [10] Knuth D., The Art of Computer Programming: Fundamental Algorithms, vol. 2, Addison Wesley, 1973.
• [11] Kozen D., The Design and Analysis of Algorithms, Springer Verlag, 1992.
• [12] Manjunath B.S., Salambier B., Sikora T, Introduction to MPEG-7: Multimedia Content Description Language, John Wiley & Sons, 2002.
• [13] Skarbek W., Multimedia - Algorithms and Standards for Compression, Akademicka Oficyna Wydawnicza PLJ, Warszawa, 1998 (in Polish).
• [14] Weber R., Blott S., An Approximation-Based Data Structure for Similarity Search, Technical Report 24, ESPRIT Project HERMES (no. 9141), 1997.