Journal of KIISE:Databases (한국정보과학회논문지:데이타베이스)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

A Distributed High Dimensional Indexing Structure for Content-based Retrieval of Large Scale Data

대용량 데이터의 내용 기반 검색을 위한 분산 고차원 색인 구조

  • 최현화 (한국전자통신연구원 데이터베이스연구팀) ;
  • 이미영 (한국전자통신연구원 데이터베이스연구팀) ;
  • 김영창 (한국전자통신연구원 데이터베이스연구팀) ;
  • 장재우 (전북대학교 컴퓨터시스템공학과) ;
  • 이규철 (충남대학교 컴퓨터공학과)
  • Received : 2010.08.23
  • Accepted : 2010.08.26
  • Published : 2010.10.15
Download PDF
⟨ Previous Next ⟩

Abstract

Although conventional index structures provide various nearest-neighbor search algorithms for high-dimensional data, there are additional requirements to increase search performances as well as to support index scalability for large scale data. To support these requirements, we propose a distributed high-dimensional indexing structure based on cluster systems, called a Distributed Vector Approximation-tree (DVA-tree), which is a two-level structure consisting of a hybrid spill-tree and VA-files. We also describe the algorithms used for constructing the DVA-tree over multiple machines and performing distributed k-nearest neighbors (NN) searches. To evaluate the performance of the DVA-tree, we conduct an experimental study using both real and synthetic datasets. The results show that our proposed method contributes to significant performance advantages over existing index structures on difference kinds of datasets.

고차원 데이터에 대한 다양한 색인 구조가 제안되어 왔음에도 불구하고, 인터넷 서비스로서 이미지 및 동영상의 내용 기반 검색을 지원하기 위해서는 고확장성 지원 및 k-최근접점 검색 성능 향상을 지원하는 새로운 고차원 데이터의 색인 구조가 절실히 요구된다. 이에 우리는 다중 컴퓨팅 노드를 바탕으로 구축되는 분산 색인 구조로 분산 벡터 근사 트리(Distributed Vector Approximation-tree)를 제안한다. 분산 벡터 근사 트리는 대용량의 고차원 데이터로부터 추출한 샘플 데이터를 바탕으로 hybrid spill-tree를 구축하고, hybrid spill-tree외 말단 노드 각각에 분산 컴퓨팅 노드를 매핑하여 VA-file용 구축하는 두 레벨의 분산 색인 구조이다. 우리는 다중 컴퓨팅 노드들 상에 구축된 분산 벡터 근사 트리를 바탕으로 병렬 k-최근접점 검색을 수행함으로써 검씩 성능을 향상시킨다. 본 논문에서는 서로 다른 분포의 데이터 집합을 바탕으로 한 성능 시험 결과를 통하여, 분산 벡터 근사 트리가 기존의 고확장성을 지원하는 색인 구조와 비교하여 검색 정확도에 대한 손실 없이 더 빠른 k-최근접점 검색을 수행함을 보인다.

Keywords

References

  1. C. Zhang, A. Krishnamurthy, and R.Y. Wang, "SkipIndex: Towards a Scalable Peer-to-Peer Index Service for High Dimensional Data," Technical Report TR-703-04, Princeton University, 2004.
  2. B. Nam and A. Sussman, "DiST: Fully Decentralized Indexing for Querying Distributed Multidimensional Datasets," Technical Report CS-TR-4720 and UMIACS-TR-2005-28, Maryland University, 2005.
  3. H.V. Jagadish, B.C. Ooi, Q. H. Vu, et al., "VBITree: A Peer-to-Peer Framework for Supporting Multi-Dimensional Indexing Schemes," Proc. ICDE, 2006.
  4. M. Bawa, T. Condie, and P. Ganesan, "LSH Forest: Self-Tuning Indexes for Similarity Search," Proc. WWW, 2005.
  5. P. Haghani, S. Michel, P. Cudre-Mauroux, et al., "LSH At Large-Distributed KNN Search in High Dimensions," Proc. WebDB, 2008.
  6. R. Weber, H.J. Schek and S. Blott, "A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces," Proc. VLDB, pp.194-205, 1998.
  7. J.T. Robinson, "The K-D-B Tree: A Search Structure for Large Multidimensional Dynamic Indexes," Proc. SIGMOD, 1981.
  8. D.B. Lomet and B. Salzberg, "A Robust Multi- Attribute Search Structure," Proc. IEEE Data Engineering, pp.296-304, 1989.
  9. N. Beckmann, H.P. Kriegel, R. Schneider, et al., "The R*-tree: An Efficient and Robust Access Method for Point and Rectangles," Proc. ACM SIGMOD, pp.322-331, 1990.
  10. S. Berchtold, D.A. Keim, and H.-P. Kriegel, "The X-tree: An Index Structure for High-Dimensional Data," Proc. VLDB, pp.28-39, 1996.
  11. P. Ciaccia, M. Patella, and P. Zezula, "M-tree: An Efficient Access Method for Similarity Search in Metric Spaces," Proc. VLDB, pp.426-435, 1997.
  12. T. Liu, A.W. Moore, and A. Gray, "An Investigation of Practical Approximate Nearest Neighbor Algorithms," Proc. ANIPS, 2004.
  13. C. Bohm and H.P. Kriegel, "Dynamically Optimizing High-Dimensional Index Structures," Proc. EBDT, 2000.
  14. G.H. Cha, X. Zhu, D. Petkovic, et al., "An Efficient Indexing Method for Nearest Neighbor Searches in High-Dimensional Image Databases," IEEE Transaction on Multimedia, vol.4, no.1, pp.76-87, 2002. https://doi.org/10.1109/6046.985556
  15. S.G. Han and J.W. Chang, "A New High- Dimensional Index Structure Using a Cell-Based Filtering Technique," Proc. DASFAA, LNCS, vol.1884, pp.79-92, 2000.
  16. A. Gionis, P. Indyk, and R. Motwani, "Similarity Search in High Dimensions via hashing," Proc. VLDB, 1999.
  17. E. Cohen, M. Datar, S. Fujiwara, et al., "Finding Interesting Associations without Support Pruning," Proc. ICDE, 2000.
  18. T. Liu, C. Rosenberg, and H.A. Rowley, "Clustering Billions of Images with Large Scale Nearest Neighbor Search," Proc. IEEE WACV, 2007.
  19. T. Yamane, Statistics, An Introductory Analysis, 2nd Ed., 1976.
  20. http://www-deis.unibo.it/research/Mtree
  21. http://www.autonlab.org/autonweb/15960.html