Earticle

초록

영어

The binary and interpolation search algorithms are the most famous among search area algorithms, the former running in O(log2 n) on average, and the latter in O(log2 log2 n)on average and O(n) at worst. Also, the interpolation search use only the probability of key value location without priori information. This paper proposes another search algorithm, which I term a ‘hybrid block and interpolation search’. This algorithm employs the block search, a method by which MSB index of a data is determined as a block, and the interpolation search to find the exact location of the key. The proposed algorithm reduces the search range with priori information and search the reduced range with uninformed situation. Experimental results show that the algorithm has a time complexity of O(log2 log2 ni), ni ≃ 0.1n both on average and at worst through utilization of previously acquired information on the block search. The proposed algorithm has proved to be approximately 10 times faster than the interpolation search on average.

한국어

데이터 탐색법 중 가장 널리 알려진 이진법은 평균과 최악의 경우 O(log2 n), 보간법은 평균 O(log2 log2 n), 최악의 경우 O(n)의 수행 복잡도를 갖고 있다. 또한 기존의 보간탐색법은 사전정보없이 킷값이 확률적으로 위치한 정 보에 근거하여 탐색을 한다. 본 논문에서는 데이터의 MSB 인덱스를 블록으로 하는 블록탐색법으로 해당 블록범위를 결정하고, 블록 내에서는 보간법을 적용하여 탐색하는 하이브리드 블록과 보간탐색 알고리즘을 제안한다. 제안된 알고 리즘은 블록탐색법의 사전 정보를 활용하여 탐색범위를 축소시키고 축소된 탐색범위내에서 무정보 방법으로 탐색하는 방법으로 평균과 최악의 경우 모두 수행복잡도는 O(log2 log2 ni), ni ≃ 0.1n으로 보간탐색법의 평균 수행복잡도에 비해 10배 정도 시간을 단축시킬 수 있다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. 탐색법의 문제점
 Ⅲ. 블록 보간 탐색법
 Ⅳ. 적용 결과 및 분석
 Ⅴ. 결론
 References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380