본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

고차원 멀티미디어 데이터 검색을 위한 벡터 근사 비트맵 색인 방법
Vector Approximation Bitmap Indexing Method for High Dimensional Multimedia Database

박주현   (서강대학교 대학원 컴퓨터학과UU0000674  ); 손대온   (LG전자 MC연구소CC0145603  ); 낭종호   (서강대학교 컴퓨터학과UU0000674  ); 주복규   (홍익대학교 컴퓨터정보통신공학과UU0001569  );
  • 초록

    고차원 데이터 공간에서의 효과적인 검색을 위해 최근 VA-file[1], LPC-file[2] 등과 같이 벡터 근사에 기반을 둔 필터링 색인 방법들이 연구되었다. 필터링 색인 방법은 벡터를 근사한 작은 크기의 색인 정보를 사용하여 근사 거리를 계산하고, 이를 사용하여 질의 벡터와 유사하지 않은 대부분의 벡터들을 빠른 시간 안에 검색 대상에서 제외한다. 즉, 실제 벡터 대신 근사 벡터를 읽어 디스크 I/O 시간을 줄여 전체 검색 속도를 향상시키는 것이다. 하지만 VA-file 이나 LPC-file은 근사 거리를 구하는 방법이 순차 검색과 같거나 복잡하기 때문에 검색 속도 향상 효과가 그리 크지 않다는 문제점을 가지고 있다. 본 논문은 이러한 근사 거리 계산 시간을 줄이기 위하여 새로운 비트맵 색인 구조를 제안한다. 근사 거리 계산속도의 향상을 위하여, 각 객체의 값을 특성 벡터 공간상의 위치를 나타내는 비트 패턴으로 저장하고, 객체 사이의 거리를 구하는 연산은 실제 벡터 값의 연산보다 속도가 훨씬 빠른 XOR 비트 연산으로 대체한다. 실험에 의하면 본 논문이 제안하는 방법은 기존 벡터 근사 접근 방법들과 비교하여 데이터 읽기시간은 더 크지만, 계산 시간을 크게 줄임으로써 전체 검색 속도는 순차 검색의 약 4배, 기존의 방법들보다는 최대 2배의 성능이 향상되었다. 결과적으로, 데이터베이스의 속도가 충분히 빠른 경우 기존의 벡터 근사 접근법의 필터링을 위한 계산 시간을 줄임으로써 더욱 검색 성능을 향상 시킬 수 있음을 확인할 수 있다.


    Recently, the filtering approach using vector approximation such as VA-file[1] or LPC-file[2] have been proposed to support similarity search in high dimensional data space. This approach filters out many irrelevant vectors by calculating the approximate distance from a query vector using the compact approximations of vectors in database. Accordingly, the total elapsed time for similarity search is reduced because the disk I/O time is eliminated by reading the compact approximations instead of original vectors. However, the search time of the VA-file or LPC-file is not much lessened compared to the brute-force search because it requires a lot of computations for calculating the approximate distance. This paper proposes a new bitmap index structure in order to minimize the calculating time. To improve the calculating speed, a specific value of an object is saved in a bit pattern that shows a spatial position of the feature vector on a data space, and the calculation for a distance between objects is performed by the XOR bit calculation that is much faster than the real vector calculation. According to the experiment, the method that this paper suggests has shortened the total searching time to the extent of about one fourth of the sequential searching time, and to the utmost two times of the existing methods by shortening the great deal of calculating time, although this method has a longer data reading time compared to the existing vector approximation based approach. Consequently, it can be confirmed that we can improve even more the searching performance by shortening the calculating time for filtering of the existing vector approximation methods when the database speed is fast enough.


  • 주제어

    멀티미디어 검색 .   고차원 색인.  

  • 참고문헌 (13)

    1. R. Weber, H. Schek, and S. Blott, 'A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces,' Proc. of the Int'l Conf. on VLDB, pp.194-205, 1998 
    2. G. Cha, X. Zhu, D. Petkovic, and C. Chung, 'An Efficient Indexing Method for Nearest Neighbor Searches in High-Dimensional Image Databases,' IEEE Trans. on Multimedia, Vol. 4, No.1, pp.76-87, 2002 
    3. N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger, 'The R*-tree: An efficient and robust access method for points and rectangles,' Proc. of ACM SIGMOD Int'l Conf. on Meanagement of Data, PP.322-331, 1990 
    4. S. Berchtold, D. Keim, and H. Kriegel, 'The X-tree: An Index Structure for High-Dimensional Data,' Proc. of the Int'l Conf. on Very Large Data Bases, pp.28-39, 1996 
    5. G. Cha, and C. Chung, 'The GC-Tree: A High-Dimensional Index Structure for Similarity Search in Image Databases,' IEEE Trans. on Multimedia, Vol.4, No.2, pp.235-247, 2002 
    6. N. Katayama, and S. Satoh, 'The SR-Tree: An Index Structure for High-Dimensional Nearest Neighbor Queries,' Proc. of the ACM SIGMOD Int'l Conf. on Management of Data, pp.369-380, 1997 
    7. P. Indyk, and R. Motwani, 'Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,' Proc. of the ACM Symp. on the Theory of Computing, pp.604-613, 1998 
    8. ISO/IEC JTC1/SC29/WG11 Information Technology Multimedia Content Description Interface-Part3: Visual, 2001 
    9. ISO/IEC JTC1/SC29/WG11 MPEG-7 Visual part of eXperience Model Version 11.0, 2001 
    10. B. Manjunath, P. Salembier, and T. Sikora, Introduction to MPEG-7 Multimedia Content Description Interface, JOOHN WILEY & SONS, 2002 
    11. K. Chakrabarti, and S. Mehrotra, 'Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces,' Proc. of the Int'l Conf. on VLDB, pp.89-100, 2000 
    12. K. Kanth, D. Agrawal, and A. Singh, 'Dimensionality Reduction for Similarity Searching in Dynamic Databases,' Proc. of the ACM SIGMOD Int'l Conf. on Management of Data, pp.l66-176. 1998 
    13. E. Kushilevitz, R. Ostrovsky, and Y. Ravani, 'Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces,' Proc, of the ACM Symposium on the Theory of Computing, pp.614-623, 1998 

 저자의 다른 논문

  • 박주현 (3)

    1. 2002 "동영상 요약 및 검색 시스템" 방송공학회논문지 = Journal of broadcast engineering 7 (2): 114~125    
    2. 2003 "문맥을 고려한 예제 기반 동영상 검색 알고리즘" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (12): 756~771    
    3. 2006 "MAF(Multimedia Application File Format) 기반 멀티미디어 검색 시스템의 설계 및 구현" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 33 (9): 574~584    
  • 낭종호 (45)

  • 주복규 (17)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기