$\require{mediawiki-texvc}$
  • 검색어에 아래의 연산자를 사용하시면 더 정확한 검색결과를 얻을 수 있습니다.
  • 검색연산자
검색연산자 기능 검색시 예
() 우선순위가 가장 높은 연산자 예1) (나노 (기계 | machine))
공백 두 개의 검색어(식)을 모두 포함하고 있는 문서 검색 예1) (나노 기계)
예2) 나노 장영실
| 두 개의 검색어(식) 중 하나 이상 포함하고 있는 문서 검색 예1) (줄기세포 | 면역)
예2) 줄기세포 | 장영실
! NOT 이후에 있는 검색어가 포함된 문서는 제외 예1) (황금 !백금)
예2) !image
* 검색어의 *란에 0개 이상의 임의의 문자가 포함된 문서 검색 예) semi*
"" 따옴표 내의 구문과 완전히 일치하는 문서만 검색 예) "Transform and Quantization"
쳇봇 이모티콘
안녕하세요!
ScienceON 챗봇입니다.
궁금한 것은 저에게 물어봐주세요.

논문 상세정보

고차원 멀티미디어 데이터 검색을 위한 벡터 근사 비트맵 색인 방법

Vector Approximation Bitmap Indexing Method for High Dimensional Multimedia Database

초록

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

Abstract

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 

이 논문을 인용한 문헌 (0)

  1. 이 논문을 인용한 문헌 없음

원문보기

원문 PDF 다운로드

  • ScienceON :

원문 URL 링크

원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다. (원문복사서비스 안내 바로 가기)

상세조회 0건 원문조회 0건

DOI 인용 스타일