·264· 智能系统学报 第3卷 [4 ]SCHRECK T,CHEN Z Branch grafting method or R-tree 1.0 ◆基于LS-tree mplementation [J]The Joumal of Systems and Sofwware, 。不同级小波系数 2000.53(1):83-93 0.9 0 [5 SH M K,SR IKANT R,AGRAWAL R High-dimensional sm ilarity poins [J ]IEEE Trans on Knowledge and Data 0.8 0 Engineering,2002,14(1):156-171. [6]PARKD J,HEU S,KM H J.The RS-tree:an efficient da- 古 ta structure for distance browsing queries [J]nfomation Processing Letters,2001,80(2):195-203 0.63 [7]HUANG PW,LN PL,LN H Y.Opti izing storage utili- 4 6 小波级数 zation in R-tree dynam ic index structure for spatial databas- (a)基于LS-tree和不同级小波系统检索的检索精度 es [J ]The Joumal of Systems and Softare,2007,55(3) 291-299 1.0 *基于LS-tree [8 WHIE D A,JA N R Sm ilarity indexing with the SS-tree 口不同级小波级数 0.8 [C]//Proceedings of the Twelfth Intemational Conference on Data Engineering New Orleans,USA:Stanley Y.W. 0.6 Su,1996:516-523 0.4 [9]BERCHTOLD S,KEM D A,KR IEGEL H P The X-tree: an index structure for high-dmensional data [C]//Proc In- 0.2 tl Con on Very Large Databases Bombay,India:VADB, 0 米 1996:28-39 5 6 [10]CA IC,MIRA S K,D NG R Smart wavelet mage cod- 小波级数 ing X-tree approach [C]//Signal Processing 82 [S (b)基于LS-ree和不同级小波系数检索的古用时司比率 1],2002:239-249 图6基于LS-tree不同级小波系数检索的占用时间 [11 ]COLOSSIN G,NASC MENTO M A Benchmarking ac- cess structures for the sm ilarity retrieval of high-dmen- 比率 sonal multmedia data [C]//IEEE Intemational Confer Fig 6 Compare with LS-tree and difference level coef ence Multmedia and Expa New York,USA,2000: 1215-1218 ficient to retrieval audo [12]PRAMAN IK S,LI S,RUAN J.Perfomance analysis of 4 结束语 AB-tree [C]//IEEE Intemational Conference Multmedia and Expa New York,USA,2000:1701-1704 正如前所述，目前，可以适用于各种多媒体数据 [13]HENR CH A The LSDh-tree:an access structure for fea- ture vecors C ]//Data Engineering 14th Intemational 的组织、管理和搜索的空间数据结构很多.这些空间 Conference Orlando,USA,1998:362-369 数据结构一般都是以R-tree为基础提出来的.如，对 [14 ]CHAKRABARTIK,MEHROTRA S The hybrid tree:an index structure for high diensional feature paces[C]// 于图像数据的组织和管理常用R`-tree对于文档数 Data Engineering,15 th Intemational Conference Sydney, 据的组织管理采用TV-tree对于视频数据的管理通 1999:440-447. [15 ]SUBRAMANYA S R Indexing and searching schemes or 常采用帧段树或RS-tee等.但对于多媒体音频数据 audio data in audio/multmedia databases(multmedia da- 的组织管理却鲜有文献.针对这种情况，本文提出并 tabase)[D ]USA:George Washington Univ,1999 定义了LS-tree来组织管理多媒体音频数据.同时， [16 ]L I Y,HOU Y.Search audio data with the wavelet Pyram i dal algprithm [J ]Infomation Processing Letter,2004,91 把这种结构用于以小波包最好基小波塔型算法为 (1):49-55 基础的音频数据检索中.实验结果表明了这种方法 [17]ZHANG T,JA Y K CC Audio content analysis for online audiovisual data segentation and classification [J].IEEE 的有效性和实用性.可以认为，这种索引结构如果能 Trans Speech and Audio Processing.2001,9(4):441- 进一步和音频数据的分段和分类技术相结合，将为 457 实现真正的基于例子和基于内容的多媒体音频数据 [18 ]UMAPATHY K,KR ISHNAN S,RAO R K Audio signal feature extraction and classificaton using bcal discrm inant 检索提供有效的方法和思路， bases [J].EEE Trans Audio,Speech and Language Pro- cessing2006,15(4):1236-1246 参考文献： 作者简介： [1]SAMET H The design and analysis of patial data struc- 李应，男，1964年生，副教授，博 tures[D ]MA,USA:AddisonWesley,1989. 士，主要研究方向为多媒体数据检索和 [2]HJAL TASON G,SAMET H.Ranking in patial databases 信息安全，发表学术论文6篇 [C]//Advances in Spatial Databases-4th Symposium. Berlin,Gemany:SpringerVerlag.1995:83-95 [3]L N K L JAGAD ISH H V,FALOUTSOS C The TV-tree: an index structure for high-dmensional data [J].VLDB Joumal,.1994,3(4):517-542 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net图 6 基于 LS2tree不同级小波系数检索的占用时间 比率 Fig. 6 Compare with LS2tree and difference level coef2 ficient to retrieval audio 4 结束语 正如前所述 ,目前 ,可以适用于各种多媒体数据 的组织、管理和搜索的空间数据结构很多. 这些空间 数据结构一般都是以 R2tree为基础提出来的. 如 ,对 于图像数据的组织和管理常用 R 3 2tree、对于文档数 据的组织管理采用 TV2tree、对于视频数据的管理通 常采用帧段树或 RS2tree等. 但对于多媒体音频数据 的组织管理却鲜有文献. 针对这种情况 ,本文提出并 定义了 LS2tree来组织管理多媒体音频数据. 同时 , 把这种结构用于以小波包最好基 2小波塔型算法为 基础的音频数据检索中. 实验结果表明了这种方法 的有效性和实用性. 可以认为 ,这种索引结构如果能 进一步和音频数据的分段和分类技术相结合 ,将为 实现真正的基于例子和基于内容的多媒体音频数据 检索提供有效的方法和思路. 参考文献 : [ 1 ] SAMET H. The design and analysis of spatial data struc2 tures[D ]. MA,USA: Addison2W esley, 1989. [ 2 ]HJALTASON G, SAMET H. Ranking in spatial databases [ C ] / /Advances in Spatial Databases—4 th Symposium. Berlin, Germany: Sp ringer2Verlag, 1995: 83295. [ 3 ]L IN K I, JAGAD ISH H V, FALOUTSOS C. The TV2tree: an index structure for high2dimensional data [ J ]. VLDB Journal, 1994, 3 (4) : 5172542. [ 4 ] SCHRECK T, CHEN Z. Branch grafting method for R2tree imp lementation [J ]. The Journal of Systems and Software, 2000, 53 (1) : 83293. [ 5 ] SH IM K, SR IKANT R, AGRAWAL R. H igh2dimensional sim ilarity joins [ J ]. IEEE Trans on Knowledge and Data Engineering, 2002, 14 (1) : 1562171. [ 6 ] PARK D J, HEU S, KIM H J. The RS2tree: an efficient da2 ta structure for distance browsing queries [ J ]. Information Processing Letters, 2001, 80 (2) : 1952203. [ 7 ]HUANG PW , L IN P L, L IN H Y. Op timizing storage utili2 zation in R2tree dynam ic index structure for spatial databas2 es [J ]. The Journal of Systems and Software, 2007, 55 (3) : 2912299. [ 8 ]WH ITE D A, JA IN R. Sim ilarity indexing with the SS2tree [C ] / /Proceedings of the Twelfth International Conference on Data Engineering. New O rleans, USA: Stanley Y. W. Su, 1996: 516 2523. [ 9 ]BERCHTOLD S, KEIM D A, KR IEGEL H P. The X2tree: an index structure for high2dimensional data [C ] / / Proc In2 tl Con on Very Large Databases. Bombay, India: VADB, 1996: 28239. [ 10 ]CA I C, M ITRA S K, D ING R. Smart wavelet image cod2 ing: X2tree app roach [ C ] / / Signal Processing 82. [ S. l. ], 2002: 2392249. [ 11 ] COLOSSI N G, NASCIMENTO M A. Benchmarking ac2 cess structures for the sim ilarity retrieval of high2dimen2 sional multimedia data [ C ] / / IEEE International Confer2 ence Multimedia and Expo. New York, USA, 2000: 121521218. [ 12 ] PRAMAN IK S, L I S, RUAN J. Performance analysis of AB2tree [ C ] / / IEEE International Conference Multimedia and Expo. New York, USA, 2000: 170121704. [ 13 ]HENR ICH A The LSDh2tree: an access structure for fea2 ture vectors [ C ] / /Data Engineering 14 th International Conference. O rlando, USA, 1998: 3622369. [ 14 ]CHAKRABARTI K, MEHROTRA S. The hybrid tree: an index structure for high dimensional feature spaces[ C ] / / Data Engineering, 15 th International Conference. Sydney, 1999: 440 2447. [ 15 ] SUBRAMANYA S R. Indexing and searching schemes for audio data in audio /multimedia databases(multimedia da2 tabase) [D ]. USA: George W ashington Univ, 1999. [ 16 ]L I Y, HOU Y. Search audio data with the wavelet Pyram i2 dal algorithm [J ]. Information ProcessingLetter, 2004, 91 (1) : 49255. [ 17 ] ZHANG T, JAY K C C. Audio content analysis for online audiovisual data segmentation and classification [J ]. IEEE Trans Speech and Audio Processing, 2001, 9 ( 4 ) : 4412 457. [ 18 ]UMAPATHY K, KR ISHNAN S, RAO R K. Audio signal feature extraction and classification using local discriminant bases [J ]. IEEE Trans Audio, Speech and Language Pro2 cessing, 2006, 15 (4) : 123621246. 作者简介 : 李 应 ,男 , 1964年生 ,副教授 ,博 士 ,主要研究方向为多媒体数据检索和 信息安全 ,发表学术论文 6篇. ·264· 智 能 系 统 学 报 第 3卷