IndexStructuresforMultimediaData多媒体数据的索引结构.ppt

1、Jaruloj Chongstitvatana,2301474 Advanced Data Structures,1,Index Structures for Multimedia Data,Feature-based Approach,2301474 Advanced Data Structures,2,Jaruloj Chongstitvatana,Multimedia Data,Feature-based approach Image/Voice data Sequence data Geometric data Text descriptor,Examples Movies, musi

2、c Gene sequence Shape (CAD) Documents,2301474 Advanced Data Structures,3,Jaruloj Chongstitvatana,Queries for Multimedia Data,Point queries Given a data, find the exact match Range queries Given a data, find similar data within a range Nearest-neighbor queries Given a data, find the most similar data

3、,2301474 Advanced Data Structures,4,Jaruloj Chongstitvatana,Feature Transformation,Mapping from an object to a d-dimensional vector, called a feature vector. What is this mapping function? For image data: color histogram, etc. For sequence data: number of each element For geometric data: slope of se

4、gments of perimeter For text descriptor: number of each keyword,2301474 Advanced Data Structures,5,Jaruloj Chongstitvatana,Similarity Measure: distance function,Given 2 data objects x and y. Let (x,y) be the distance function. (x,y) indicates the similarity between data x and y. Usually (x,y) is bas

5、ed on a distance between the feature vectors of x and y.,2301474 Advanced Data Structures,6,Jaruloj Chongstitvatana,Similarity Queries,Point queries Given an object x, find any object y such that (x,y)=0. Range queries Given an object x and a threshold , find any object y such that (x,y) . Nearest-n

6、eighbor queries Given an object x, find an object y such that (x,y) (x,z) for any object z in the database.,2301474 Advanced Data Structures,7,Jaruloj Chongstitvatana,Distance Measure,Euclidean distance Manhattan distance Maximum distance Weighted Euclidean distance Ellipsoid distance,(x,y) = (i=1,d

7、 (xi-yi)2 )1/2 (x,y) = i=1,d |xi-yi| (x,y) = max i=1,d |xi-yi| (x,y) = (i=1,d wi (xi-yi)2 )1/2 (x,y) = (x-y)T W (x-y),2301474 Advanced Data Structures,8,Jaruloj Chongstitvatana,Other Similarity Queries,k-Nearest-neighbor queries Given an object x and an integer k, find k objects y1, y2, yk, such tha

8、t, for i=1, 2, , k, (x,yi) (x,z) for any other object z in the database. Approximate nearest-neighbor queries Approximate k-nearest-neighbor queries,2301474 Advanced Data Structures,9,Jaruloj Chongstitvatana,Range Queries,On k-d-B trees Grid files Quad trees R-trees Already discussed.,2301474 Advanced D