최근에 휴대용 단말기들의 발전으로, 대용량 데이타에 대한 다양한 검색 서비스들이 휴대용 단말기에 제공되고 있다. 정보 검색을 위한 대부분 응용프로그램들은 대용량 데이타를 검색하기 위하여 B-tree나 R-tree와 같은 색인을 사용한다. 그러나 전체 데이타의 매우 적은 부분이 사용자에 의하여 접근된다. 또한, 각 데이타에 대한 접근 빈도수들은 다양하다. 그러나 B-tree나 R-tree와 같은 색인들은 편향적 접근 패턴의 특성을 고려하지 않는다. 그리고 캐쉬는 빠른 접근을 위해서 반복적으로 접근되는 데이타를 메모리에 저장한다. 그러나 캐쉬에서 사용하는 메모리의 크기는 제한적이다. 본 논문에서는 사용자의 검색패턴들을 고려한 디스크 기반의 새로운 색인구조, J-tree를 제안한다. 제안된 색인은 모든 데이터에 대한 일정한 검색속도를 보장하는 균형트리이다. 그리고 자주 접근된 데이타에 대해서는 빠른 검색속도를 제공한다. 성능평가는 다양한 실험환경에서 제안된 색인의 효율성을 보여준다.
최근에 휴대용 단말기들의 발전으로, 대용량 데이타에 대한 다양한 검색 서비스들이 휴대용 단말기에 제공되고 있다. 정보 검색을 위한 대부분 응용프로그램들은 대용량 데이타를 검색하기 위하여 B-tree나 R-tree와 같은 색인을 사용한다. 그러나 전체 데이타의 매우 적은 부분이 사용자에 의하여 접근된다. 또한, 각 데이타에 대한 접근 빈도수들은 다양하다. 그러나 B-tree나 R-tree와 같은 색인들은 편향적 접근 패턴의 특성을 고려하지 않는다. 그리고 캐쉬는 빠른 접근을 위해서 반복적으로 접근되는 데이타를 메모리에 저장한다. 그러나 캐쉬에서 사용하는 메모리의 크기는 제한적이다. 본 논문에서는 사용자의 검색패턴들을 고려한 디스크 기반의 새로운 색인구조, J-tree를 제안한다. 제안된 색인은 모든 데이터에 대한 일정한 검색속도를 보장하는 균형트리이다. 그리고 자주 접근된 데이타에 대해서는 빠른 검색속도를 제공한다. 성능평가는 다양한 실험환경에서 제안된 색인의 효율성을 보여준다.
In recent years, with the development of portable terminals, various searching services on large data have been provided in portable terminals. In order to search large data, most applications for information retrieval use indexes such as B-trees or R-trees. However, only a small portion of the data...
In recent years, with the development of portable terminals, various searching services on large data have been provided in portable terminals. In order to search large data, most applications for information retrieval use indexes such as B-trees or R-trees. However, only a small portion of the data set is accessed by users, and the access frequencies of each data are not uniform. The existing indexes such as B-trees or R-trees do not consider the properties of the skewed access patterns. And a cache stores the frequently accessed data for fast access in memory. But the size of memory used in the cache is restricted. In this paper, we propose a new index based on disk, called J-tree, which considers user's search patterns. The proposed index is a balanced tree which guarantees uniform searching time on all data. It also supports fast searching time on the frequently accessed data. Our experiments show the effectiveness of our proposed index under various settings.
In recent years, with the development of portable terminals, various searching services on large data have been provided in portable terminals. In order to search large data, most applications for information retrieval use indexes such as B-trees or R-trees. However, only a small portion of the data set is accessed by users, and the access frequencies of each data are not uniform. The existing indexes such as B-trees or R-trees do not consider the properties of the skewed access patterns. And a cache stores the frequently accessed data for fast access in memory. But the size of memory used in the cache is restricted. In this paper, we propose a new index based on disk, called J-tree, which considers user's search patterns. The proposed index is a balanced tree which guarantees uniform searching time on all data. It also supports fast searching time on the frequently accessed data. Our experiments show the effectiveness of our proposed index under various settings.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
이처럼 검색의 대상이 전체 데이타의 일부분에 편중되어 있다. 그래서 본 논문에서는 이러한 사용자의 검색패턴을 검색을 위한 색인에 반영하여 보다 빠른 검색서비스를 제공하는 색인구조를 제안한다. 제안하는 색인구조는 사용자의 검색패턴을 분석하고 이를 색인에 반영한 새로운 색인이다.
향후연구방향은 본 논문에서 제안하는 J-Tree 가 검색서비스에 국한되어있지만 데이타의 삽입과 삭제에 대해서도 실시간으로 이를 색인에 반영하는 구조로 변경할 필요가 있다. 또한 실 검색데이타를 적용하여 보다 세밀한 성능평가를 통하여 보다 향상된 색인을 구현하고자 한다.
이때 사용자가 정보검색을 위해 사용하는 질의어의 대부분은 같은 질의어를 반복하여 사용하는 경우가 많다. 본 논문에서는 이러한 사용자의 검색패턴을 색인에 반영하여 보다 빠른 검색속도를 제공하는 J-Tree라는 새로운 색인을 제안한다. 그림 3은 이러한 사용자 검색 패턴을 적용한 J-Tree의 개념도를 보여준다.
본 논문에서는 일반적인 검색에서 전체 데이타의 일부분에 집중되는 검색을 보다 빠르게 제공하기 위하여 사용자의 검색패턴을 이용한 새로운 색인구조 J-Tree를 제안하였다. J-Tree는 일반적으로 사용하는 B*-Tree 나 R-Tree와 같은 색인보다 점프경로를 이용하여 내부의 검색 비교를 생략함으로써 보다 빠른 검색속도를 제공하였다.
그래서 대용량 데이타에 대한 검색서비스에 캐쉬을 적용하는 것은 적합하지 않다. 본 논문은 이러한 문제점을 해결하기 위해서 메모리를 이용하는 방법이 아닌 디스크 기반의 색인을 제안한다.
제안 방법
또한 균형트리는 모든 데이타에대하여 균등한 검색속도를 제공하지만 접근 빈도가 높은 데이타에 대하여 빠른 검색속도를 제공하지 못하는 단점을 갖고 있다. 그래서 본 논문에서 제안하는 색인은 접근 빈도가 높은 데이타에 대한 빠른 검색속도를 제공하면서 접근 빈도가 낮은 데이타에 대해서는 균등한 검색속도를 제공하는 균형트리로 설계한다.
성능평가를 위하여 전체 데이타에 대한 접근 횟수를 미리 설정하기 위하여 십만 번의 검색을 실행하였다. 그리고 점프경로를 생성하기 위하여 AVG_ RCNT(l+k) 을 설정하기 위하여 k의 상수값을 0.3로 설정하여 점프경로를 결정하였다. 표 1은 성능평가를 위한 설정 기호들을 보여준다.
그리고 질의에 대한 편중도는 S=(50, 30)으로 전체검색 횟수의 50%가 전체 데이타 영역의 30%에 편중되는 조건에서 측정하였다. 본 논문에서 제안한 J-Tree가 B*-Tree 보다 레코드의 수가 증가함에 따라 처리속도가 현격히 차이가 나는 것을 보여준다.
각 링크의 접근 빈도수 R*? CNT 링크의 조건에 만족하는 단말노드의 데이타에 대한 빈도수 DRCNT을 합산한 빈도수로 설정된다. 또한 점프경로를 결정하기 위하여 링크들의 평균 접근 빈도수 AVG_RCNT 보다 높은 AVG_RCNT(l+k)의 빈도수를 설정하여 접근 빈도가 높은 링크를 선택한다. 이때 k의 값은 상수값으로 AVG_RCNT(l+k)의 값이 TOTALRCNT 값보다 적도록 설정하여 사용한다.
이러한 사용자의 검색패턴을 반영한 색인은 검색을 위해 하드디스크에 있는 데이타를 메모리에 가져오기 위한 10작업의 일부를 생략함으로써 보다 빠른 검색을 제공한다. 본 논문에서 제안하는 색인은 데이타에 대한 삽입과 삭제가 실시간으로 변경되지 않고 특정기간이 지난 이후에 일괄적으로 반영되는 검색서비스에 초점을 맞춘다.
0GHz, 메인메모리 1G를 갖는 시스템에서 실시하였다. 성능평가를 위하여 전체 데이타에 대한 접근 횟수를 미리 설정하기 위하여 십만 번의 검색을 실행하였다. 그리고 점프경로를 생성하기 위하여 AVG_ RCNT(l+k) 을 설정하기 위하여 k의 상수값을 0.
비교 및 분석한다. 실험은 LINUX 운영체계, 펜티엄IV 2.0GHz, 메인메모리 1G를 갖는 시스템에서 실시하였다. 성능평가를 위하여 전체 데이타에 대한 접근 횟수를 미리 설정하기 위하여 십만 번의 검색을 실행하였다.
그래서 본 논문에서는 이러한 사용자의 검색패턴을 검색을 위한 색인에 반영하여 보다 빠른 검색서비스를 제공하는 색인구조를 제안한다. 제안하는 색인구조는 사용자의 검색패턴을 분석하고 이를 색인에 반영한 새로운 색인이다. 이러한 사용자의 검색패턴을 반영한 색인은 검색을 위해 하드디스크에 있는 데이타를 메모리에 가져오기 위한 10작업의 일부를 생략함으로써 보다 빠른 검색을 제공한다.
J-Tree는 검색과정에서 실시간으로 발생하는 각각의 데이타에 대한 접근 빈도수를 단말노드에 반영하지만 J-Tree의 구조에 바로 반영하지 않는다. 특정 기간이 지난 이후에 데이타에 대한 삽입, 삭제 및 수정으로 일괄적으로 검색데이타를 변경하는 시점과 사용자의 검색패턴을 재 반영하기 위하여 특정한 주기인 M 기간을 설정하여 J-Tree를 재구축한다. 여기서 특정한 주기 Me 검색서비스의 대상이 되는 데이타의 특성에 맞추어 설정한다.
데이터처리
본 논문에서 제안한 J-Tree를 성능평가하기 위하여 균형 트리이면서 데이타 검색에 범용적으로 사용하는 Tree와 비교 및 분석한다. 실험은 LINUX 운영체계, 펜티엄IV 2.
이론/모형
AH-Tree는 멀티채널 환경에서의 브로드 캐스트에 많이 사용되는 색인이다[4]. AH-Tree는 Hu-tucker 알고리즘을 사용하여 생성된다. 이 알고리즘은 먼저 데이타를 접근 빈도에 따라 정렬한 후, 접근 빈도가 낮은 데이타부터 결합하여 트리를 생성하는 상향식 트리 구성 방법을 사용한다.
AH-Tree는 Hu-tucker 알고리즘을 사용하여 생성된다. 이 알고리즘은 먼저 데이타를 접근 빈도에 따라 정렬한 후, 접근 빈도가 낮은 데이타부터 결합하여 트리를 생성하는 상향식 트리 구성 방법을 사용한다. 따라서 AH-Tree에서 트리의 깊이는 각 데이타에 대한 접근 빈도를 나타내게 된다.
성능/효과
2장에서 관련된 연구를 소개하고 3장에서는 본 논문에서 제안하는 J-Tree 기법 및 특성을 기술한다. 마지막으로 4장에서 다양한 실험환경에서 제안하는 기법과 B*-Tree 의 성능평가를 통하여 제안하는 J-Tree 색인의 우수성을 입증한다.
조건에서 측정하였다. 본 논문에서 제안한 J-Tree가 B*-Tree 보다 레코드의 수가 증가함에 따라 처리속도가 현격히 차이가 나는 것을 보여준다. 이와 같은 결과는 중복되는 질의어에 대한 처리에서 J-Tree가 내부노드의 비교과정을 단축함으로써 처리속도가 빨라진 것이다.
후속연구
J-Tree는 일반적으로 사용하는 B*-Tree 나 R-Tree와 같은 색인보다 점프경로를 이용하여 내부의 검색 비교를 생략함으로써 보다 빠른 검색속도를 제공하였다. 향후연구방향은 본 논문에서 제안하는 J-Tree 가 검색서비스에 국한되어있지만 데이타의 삽입과 삭제에 대해서도 실시간으로 이를 색인에 반영하는 구조로 변경할 필요가 있다. 또한 실 검색데이타를 적용하여 보다 세밀한 성능평가를 통하여 보다 향상된 색인을 구현하고자 한다.
참고문헌 (8)
Narayanan Shivakumar, Suresh Venkatasubramanian, 'Energy Efficient indexing for Information Dissemination In Wireless Systems,' in ACM, Journal of Wireless and Nomadic Application, 1996
Ryen W. White, Dan Morris, 'Investigating the querying and browsing behavior of advanced search engine users,' Proc, ACM SIGIR, July, 2007
Yabo Xu, Ke Wang, Benyu Zhang, Zheng Chen,'Privacy-enhancing personalized web search,' Proceedings of the 16th international conference on World Wide Web, May, 2007
S. Lo and A. Chen, 'Optimal Index and Data Allocation in Multiple Broadcast Channels,' In proceedings. 16th international conference on Data Engineering, 2000
L. Fan, P. Cao, J. Almeida, and A. Broder, 'Summary Cache: A Scalable Wide Area Web Cache Sharing Protocol,' Proc. ACM SIGCOMM, pp. 254-265, 1998
K. Wu and P. Yu, 'Latency-Sensitive Hashing for Collaborative Web Caching,' Proc. World Wide Web Conf., pp. 633-644, 2000
Glen Jeh, Jennifer Widom, 'Scaling personalized web search,' Proceedings of the 12th international conference on World Wide Web, 2003
Kathleen R. McKeown, Noemie Elhadad, Vasileios Hatzivassiloglou, 'Leveraging a common representaion for personalized search and summarization in a medical digital library,' Proceedings of the 3rd ACMlIEEE-CS joint conference on Digital libraries, 2003
※ AI-Helper는 부적절한 답변을 할 수 있습니다.