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

논문 상세정보

고차원 데이터의 효율적인 최근접 객체 검색 기법
Efficient Searching Technique for Nearest Neighbor Object in High-Dimensional Data

김진호   (명지대학교 대학원 컴퓨터공학과UU0000539  ); 박영배   (명지대학교 컴퓨터공학과UU0000539  );
  • 초록

    피라미드 기법은 n-차원 공간 데이터를 1차원 데이터로 변환하여 B+-트리로 표현하며, n-차원 데이터 공간에서 하이퍼큐브 영역질의 처리로 발생하는 “차원의 저주현상”에 영향을 받지 않게 검색 시간 문제를 해결하고 있다. 또 구형 피라미드 기법(SPY-TEC)은 피라미드 기법의 공간 분할 전략을 응용하여 유사도 검색에 적합한 구 영역질의 방법을 사용하고 검색 성능을 개선하고 있다. 하지만 유사도 검색의 응용에서 영역질의는 범위를 지정하는데 어려움이 있어 최근접 질의가 더 효율적이며, 기존의 제안된 인덱스 기법들은 특정 분포의 데이터에 대해서만 우수한 성능을 보이는 단점이 있다. 따라서 이 논문에서는 멀티미디어 데이터와 같은 고차원 데이터의 검색 성능을 향상시키기 위해 제안되었던 PdR-트리를 이용하여 최근접 객체 검색 기법을 제안한다. 다양한 분포의 모의 데이터와 실제 데이터를 이용하여 실험한 결과, PdR-트리가 피라미드 기법과 구형 피라미드 기법보다 검색 성능이 향상되었음을 보이고 있다.


    The Pyramid-Technique is based on mapping n-dimensional space data into one-dimensional data and expresses it as a B+-tree. By solving the problem of search time complexity the pyramid technique also prevents the effect of "phenomenon of dimensional curse" which is caused by treatment of hypercube range query in n-dimensional data space. The SPY-TEC applies the space division strategy in pyramid method and uses spherical range query suitable for similarity search so that Improves the search performance. However, nearest neighbor query is more efficient than range query because it is difficult to specify range in similarity search. Previously proposed index methods perform well only in the specific distribution of data. In this paper, we propose an efficient searching technique for nearest neighbor object using PdR-Tree suggested to improve the search performance for high dimensional data such as multimedia data. Test results, which uses simulation data with various distribution as well as real data, demonstrate that PdR-Tree surpasses both the Pyramid-Technique and SPY-TEC in views of search performance.rformance.


  • 주제어

    PdR-트리 .   피라미드 기법 .   구형 피라미드 기법 .   최근접 질의.  

  • 참고문헌 (23)

    1. 이혜명, 임채명, 박영배, '시계열 패턴을 위한 dR-트리', 한국정보과학회 가을 학술발표논문집(A), 1996 
    2. 이동호, 정진완, 김형주, '고차원 데이터의 유사성 검색을 위한 효율적인 색인기법', 정보과학회논문지(B), 제26권 제11호, 1999 
    3. 이동호, 송용준, 김형주. 'SCARLET: 웨이브릿 변환을 이용한 내용기반 이미지검색시스템의 설계 및 구현', 정보과학회 논문지(C), 제3권 제4호, 1997 
    4. 박영배, 조범석, 'PdR-트리 : 고차원 데이터의 검색 성능 향상을 위한 효율적인 인덱스 기법', 정보처리학회논문지D, 제8-D권 제2호,2001     
    5. C. C. Chang, S. Y. Lee, 'Retrieval of Similar Pictures on Pictorial Databases,' Pattern Recognition, pp.24, 675-680, 1991 
    6. N. Beckermann, H. P. Kriegel, R. Schneider, B. Seeger, 'The R*-tree : An Efficient and Robust Access Method for Points and Rectangles,' ACM, 1990 
    7. A. Gutmann, 'A Dynamic Index Structure for Spatial Searching,' ACM, USA, 1984 
    8. N. Roussopoulos, S. Kelley, F. Vincent, 'Nearest Neighbor Querys', Proc. ACM SIGMOD Int. Conf., pp.71-79, 1995 
    9. K. Aizawa, H. Harashima, 'Model based image coding,' SPIE/IS, Electronic Imaging, Vol.4-1, pp.1-2, 1994 
    10. I. Kamel, C. Faloutsos, 'Hilbert R-tree : An Improved R-tree using Fractals,' VLDB, 1994 
    11. D. A. White, R. Jain, 'Similarity Indexing with the SS-tree,' IEEE, 1995 
    12. L. I. Lin, H. V. Jagadish, C. Faloutsos, 'The TV-tree-an index structure for high-dimensional data,' VLDB, 1995 
    13. A. D. Bimbo, P. Pala, S. Santini, 'Image Retrieval by Elastic Matching of Shapes and Image Patterns,' Proceeding of the itn'l conf. on multimedia computing and systems, Japan, 1996 
    14. N. Katayama, S. Satoh, 'The SR-tree : An Index Structure for High-Dimensional Nearest Neighbor Queries,' ACM SIGMOD, 1997 
    15. S. Berchtold, D. A. Keim, H. P. Kriegel, 'The X-tree : An Index Structure for High-Dimension Data,' 22nd VLDB Conference, 1996 
    16. J. M. Hellerstein, E. Koutsoupias, C. H. Papadimitriou, 'On the Analysis of Schemes,' ACM PODS, pp 249-256, 1997 
    17. R. Weber, S. Blott, 'An Approximation-Based Data Structure for Similarity Search,' Esprit Project Hermes, technical report, Oct., 1997 
    18. P. Ciaccia, M. Patella, P. Zezula, 'M-tree : An Efficient Access Method for Similarity Search in Metric Spaces,' 23rd VLDB Conference, 1997 
    19. S. Berchtold, C. Bohm, H-P. Kriegel. 'The Pyramid- Technique : Towards Breaking the Curse of Dimensionality,' Proc. ACM SIGMOD Int. Conf. on Management of Data, 1998 
    20. A. Henrich, 'The LSDh-tree : An Access Structure for Feature Vectors,' ICDE, 1998 
    21. R. Weber, H. J. Schek, S. Blott, 'A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, 24th VLDB Conference,' NY, USA, 1998 
    22. A. Hinneburg, D. A. Keim, 'Optimal Grid_Clustering : Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering,' proceedings of the 25th VLDB Conference, Edinburgh, Scotland, 1999 
    23. G. R. Hjaltason, H. Samet, 'Distance Browsing in Spatial Databases,' ACM Transaction on Database Systems, 24(2), pp.265-318, 1999 

 저자의 다른 논문

  • 박영배 (21)

    1. 1982 "Software Manufacturing의 표준화에 관한 연구" 공업경영논총 5 (7): 49~58    
    2. 1998 "인트라넷에서 가상데이터베이스를이용한 데이터베이스 검색 시스템의 설계" 정보처리논문지 = The transactions of the Korea Information Processing Society 5 (6): 1404~1417    
    3. 2001 "PdR-트리 : 고차원 데이터의 검색 성능 향상을 위한 효율적인 인덱스 기법" 정보처리학회논문지. The KIPS transactions. Part D. Part D d8 (2): 145~153    
    4. 2001 "점진적 프로젝션을 이용한 고차원 글러스터링 기법" 정보과학회논문지. Journal of KIISE. 데이타베이스 28 (4): 568~576    
    5. 2002 "Gabor 필터를 이용한 효율적인 지문분류" 정보처리학회논문지. The KIPS transactions. Part B. Part B b9 (1): 29~34    
    6. 2002 "Gabor 필터를 이용한 지문 인식" 정보처리학회논문지. The KIPS transactions. Part B. Part B b9 (5): 653~662    
    7. 2004 "효율적인 이미지 분할을 위한 RGB 채널 선택 기법" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 31 (10): 1332~1344    
    8. 2005 "모바일 데이터베이스 환경의 신뢰성 보장 질의처리 시스템 설계" 정보처리학회논문지. The KIPS transactions. Part D. Part D d12 (4): 521~530    
    9. 2005 "이기종 CBIR 시스템을 위한 FEMAL" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 32 (9): 853~867    
    10. 2006 "연속적인 스카이라인 질의의 정적 유효 영역을 이용한 효율적인 처리" 정보과학회논문지. Journal of KIISE. 데이타베이스 33 (6): 631~643    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

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