Derived　from　the　thought　of　data　warehouse　and　data　cube,　this　paper　presents　a　new　database　structure　model　which　organizes　the　multimedia　data　in　a　multi-dimensional　data　cube.　Clustered　data　are　stored　in　instance　table　in　the　data　cube.　A　corresponding　leading　data　are　stored　in　dimension　table.　When　querying,　a　leading　data　is　gained　from　dimension　table　firstly,　followed　by　a　k-nearest　neighbor　query　from　the　corresponding　category,　the　retrieval　results　are　returned.　Because　of　not　in　need　of　searching　all　the　records　in　database,　the　time　cost　is　low.　©　2008　IEEE.