본문 바로가기 주메뉴 바로가기
22대 대한민국 국회 국회정보길라잡이 국회의원검색
회원가입 로그인
HOME

정보검색

소장정보 검색

국회도서관 홈으로 정보검색 소장정보 검색

결과 내 검색

동의어 포함

고급검색

인명/단체명

저자정보 상세정보
인명/단체명을 입력하세요.

키워드

  • 대표어

  • 외국어

-

초록보기

데이터 응답 속도는 사용자 경험과 직결되기 때문에 클라우드 서비스의 중요한 이슈이다. 그렇기 때문에 사용자의 요청에 빠르게 응답하기 위하여 인-메모리 데이터베이스는 클라우드 기반 응용 프로그램에 널리 사용되고 있다. 하지만, 현재 인-메모리 데이터베이스는 대부분 연결 리스트 기반의 해시 테이블로 구현되어 있어 상수 시간의 응답을 보장하지 못한다. 쿠쿠 해싱(cuckoo hashing)이 대안으로 제시되었지만, 할당된 메모리의 반만 사용할 수 있다는 단점이 있었다. 이후 버킷화 쿠쿠 해싱(bucketized cuckoo hashing)이 메모리 효율을 개선하였으나 삽입 연산시의 오버헤드를 여전히 극복하지 못하였다. 본 논문에서는 BCH의 삽입 성능과 탐색 성능을 동시에 향상시키는 데이터 관리 방법인 월 쿠쿠(wall cuckoo)를 제안한다. 월 쿠쿠의 핵심 아이디어는 버킷 내부의 데이터를 사용된 해시 함수에 따라 분리하는 것이다. 이를 통하여 버킷의 탐색 범위가 줄어들어 접근해야 하는 슬롯의 수를 줄일 수 있는데, 이렇게 탐색 연산의 성능이 향상되기 때문에 탐색 과정이 포함되어 있는 삽입 연산 또한 개선된다. 분석에 따르면, 월 쿠쿠에서의 슬롯 접근 횟수 기댓값은 BCH의 기댓값보다 작다. 우리는 월 쿠쿠와 BCH, 정렬 쿠쿠를 비교하는 실험을 진행하였으며, 각 메모리 사용률(10%-95%)에서 월 쿠쿠의 탐색 및 삽입 연산이 다른 기법보다 더 적은 슬롯 접근 횟수를 가지는 것을 보였다.

The data response speed is a critical issue of cloud services because it directly related to the user experience. As such, the in-memory database is widely adopted in many cloud-based applications for achieving fast data response. However, the current implementation of the in-memory database is mostly based on the linked list-based hash table which cannot guarantee the constant data response time. Thus, cuckoo hashing was introduced as an alternative solution, however, there is a disadvantage that only half of the allocated memory can be used for storing data. Subsequently, bucketized cuckoo hashing (BCH) improved the performance of cuckoo hashing in terms of memory efficiency but still cannot overcome the limitation that the insert overhead. In this paper, we propose a data management solution called Wall Cuckoo which aims to improve not only the insert performance but also lookup performance of BCH. The key idea of Wall Cuckoo is that separates the data among a bucket according to the different hash function be used. By doing so, the searching range among the bucket is narrowed down, thereby the amount of slot accesses required for the data lookup can be reduced. At the same time, the insert performance will be improved because the insert is following up the operation of the lookup. According to analysis, the expected value of slot access required for our Wall Cuckoo is less than that of BCH. We conducted experiments to show that Wall Cuckoo outperforms the BCH and Sorting Cuckoo in terms of the amount of slot access in lookup and insert operations and in different load factor (i.e., 10%-95%).

권호기사

권호기사 목록 테이블로 기사명, 저자명, 페이지, 원문, 기사목차 순으로 되어있습니다.
기사명 저자명 페이지 원문 목차
블록체인 기반의 토큰을 이용한 IoT 다단계 인증 시스템 = IoT multi-phase authentication system using token based blockchain 박환, 김미선, 서재현 p.139-150

월 쿠쿠 = Wall cuckoo : a method for reducing memory access using hash function categorization : 해시 함수 분류를 이용한 메모리 접근 감소 방법 문성광, 민대홍, 장룡호, 정창훈, 양대헌, 이경희 p.127-138

Performance Counter Monitor를 이용한 FLUSH+RELOAD 공격 실시간 탐지 기법 = Real-time detection on FLUSH+RELOAD attack using performance counter monitor 조종현, 김태현, 신영주 p.151-158

참고문헌 (17건) : 자료제공( 네이버학술정보 )

참고문헌 목록에 대한 테이블로 번호, 참고문헌, 국회도서관 소장유무로 구성되어 있습니다.
번호 참고문헌 국회도서관 소장유무
1 DB-Engines, DB-Engines Ranking [Internet], http://db- engines. com/en/ranking/. 미소장
2 Amazon Web Services, Definition of Key-value Database [Internet], https://aws.amazon.com/ko/nosql/key-value/. 미소장
3 Redis, OBJECT Subcommand [Internet], https://redis.io/commands/object. 미소장
4 Memcached [Internet], https://memcached.org/. 미소장
5 Memcached GitHub, Memcached/memcached.h [Internet], https://goo.gl/BK7nkQ, Line 462. 미소장
6 R. Pagh and F. F. Rodler, “Cuckoo Hashing,” Eur. Symp. Algorithms, Springer Berlin Heidelberg, pp.121-133, Aug. 2001. 미소장
7 An Improved Version of Cuckoo Hashing: Average Case Analysis of Construction Cost and Search Operations 네이버 미소장
8 D. H. Min, R. H. Jang, D. H. Nyang, and K. H. Lee, “Sorting Cuckoo - Enhancing Lookup Performance of Cuckoo Hashing Using Insertion Sort -,” The Journal of Korean Institute of Communications and Information Sciences, Vol.42, No.3, pp.566-576, Mar. 2017. 미소장
9 U. Erlingsson, M. Manasse, and F. McSherry, “A Cool and Practical Alternative to Traditional Hash Tables,” in Proc. WDAS’06, Jan. 2006. 미소장
10 Y. Sun, Y. Hua, S. Jiang, Q. Li, S. Cao, and P. Zuo, “SmartCuckoo: A Fast and Cost-Efficient Hashing Index Scheme for Cloud Storage Systems,” USENIX Annual Technical Conference, pp.553-565, Santa Clara, CA, USA, July 2017. 미소장
11 A Collision-Mitigation Cuckoo Hashing Scheme for Large-Scale Storage Systems 네이버 미소장
12 E. Lehman and R. Panigrahy, “3.5-way Cuckoo Hashing for the Price of 2-and-a-bit,” in Eur. Symp. Algorithms, pp. 671-681, Springer Berlin Heidelberg, Sept. 2009. 미소장
13 E. Porat and B. Shalem, “A Cuckoo Hashing Variant with Improved Memory Utilization and Insertion Time,” in IEEE 2012 Data Compression Conf., pp.347-356, Apr. 2012. 미소장
14 A. D. Breslow, D. P. Zhang, J. L. Greathouse, N. Jayasena, and D. M. Tullsen, “Horton Tables: Fast Hash Tables for In-memory Data-intensive Computing,” USENIX ATC 16, pp.281-294, Jun. 2016. 미소장
15 J. Bob, A Hash Function for Hash Table Lookup [Internet], http://www.burtleburtle.net/bob/hash/doobs.html. 미소장
16 Mersenne twister 네이버 미소장
17 Enhanced chained and Cuckoo hashing methods for multi-core CPUs 네이버 미소장

추천서가 (다양한 추천 자료를 만나보세요)

권호기사보기

권호기사 목록 테이블로 기사명, 저자명, 페이지, 원문, 기사목차 순으로 되어있습니다.
기사명 저자명 페이지 원문 기사목차

권호

기사명 원문보기 기사목차
닫기