병렬 해쉬함수를 이용한 최소 해쉬 충돌 알고리즘
Collision Free Indexing Algorithm by using Parallel Hash Function
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
최근 소셜 네트워크 서비스가 폭발적으로 증가하면서 빅데이터 분석 연구가 많이 진행되고 있다. 이 중, 해쉬함수를 이용해서 빅데이터를 분석하는데 주로 이용되는 최소 완전 해쉬함수(MPHF)방법은 이론적으로는 해쉬충돌이 일어나지 않지만 실제로 사용하면 잦은 충돌 문제가 발생한다. 이로인해서 빅데이터 분석시간이 길어진다. MPHF의 단점이며 데이터의 양에 관계없이 해쉬 충돌이 일어나지 않도록 하기위해서 본 논문에서는 해쉬함수를 병렬화에 있어서 Heuristic 알고리즘을 적용하여해쉬 인덱스를 최적화하는 방안을 제안한다. 실험 부분에서는 본 제안방법의 착안점에 따른 우수성을기존의 방법과 비교하여 보여준다.
Abstract
According to explosive increase of social network service (SNS), big data analysis methodshave been developed by many researchers. Out of the methods, Minimal Perfect Hash Functionhas been used in big data analysis. The method sometimes cause a hash collision in realapplications and results in more analysis time. In order to solve the problem, we propose a CollisionFree Indexing algorithm using parallel hash function. For developing our method, we optimizehash index by applying a heuristic concept. In the experimental section, we show anoutperformance of out method comparing with an existing method
참고문헌 (11)
- 유지연, "세계경제포럼 (WEF) 을 통해 본 빅데이터 논의동향과 함의", 보통신정책연구원 방송통신정책, ~ (2012)
- Seokwoo Hong, "Advancement for smart fusion era dominated IT industry", Ministry of Knowledge Economy, 2, pp.24~ (2012)
- Cichelli, Richard J, "Minimal perfect hash functions made simple", Communications of the ACM, 23(1), pp.17~19 (1980)
- Fox, Edward A., "A faster algorithm for constructing minimal perfect hash functions", Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval (1992), ACM
- Fox, Edward A, "Practical minimal perfect hash functions for large databases", Communications of the ACM, 35(1), pp.105~121 (1992)
- Havas, George, "Optimal algorithms for minimal perfect hashing", Key Centre for Software Technology, Department of Computer Science, University of Queensland, ~ (1992)
- Havas, George, "Graph-Theoretic Concepts in Computer Science" (1994), Springer Berlin Heidelberg
- Sager, Thomas J, "A polynomial time generator for minimal perfect hash functions", Communications of the ACM, 28(5), pp.523~532 (1985)
- 조나연, "Hadoop과 HBase 기반의 빅 데이터 처리 응용을 위한 가상 컴퓨팅 자원 이용률 분석", 정보기술아키텍처 연구, 11(4), pp.449~462 (2014), 한국엔터프라이즈아키텍처학회
- Karp, Richard M., "An optimal algorithm for on-line bipartite matching", Proceedings of the twentysecond annual ACM symposium on Theory of computing (1990), ACM
- 함원경, "분산 시뮬레이션 시스템에서 합성 환경 표현 및 교환 표준(SEDRIS)기반의 전장 환경 구축", 정보기술아키텍처 연구, 9(3), pp.253~263 (2012), 한국엔터프라이즈아키텍처학회