http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
RAH-tree: 편향 접근 패턴을 갖는 공간 데이터에 대한 새로운 색인 구조
최근하(Keunha Choi),이승중(Seung Joong Lee),정성원(Sungwon Jung) 한국정보과학회 데이터베이스 소사이어티 2006 데이타베이스 연구 Vol.22 No.1
GPS및 PDA의 발달로 인해서 위치 기반 서비스(LBS), 차량항법장치(CNS), 지리정보시스템(GIS)등 공간데이터를 다루는 응용프로그램들이 급속하게 보급되었다. 이러한 응용프로그램들은 높이 균등 색인 기법을 통해 사용자가 원하는 데이터에 대한 색인을 제공하였다. 그러나 모든 공간 객체는 서로 상이한 접근 빈도를 가지고 있음에도 불구하고 기존의 공간색인 기법은 이를 고려하지 못하는 단점을 가지고 있었다. 또한 빈도수만을 고려한 공간 객체의 색인 방법은 접근 빈도에 따른 편향성(skewed)은 제공하지만 공간 객체에 대한 지역성을 반영하지 못한다. 이는 공간 객체가 2개 이상의 차원에 대한 정보를 요구하고 하나의 차원에 대해서만 정렬을 할 수 없기 때문이다. 본 논문에서는 밀집되어 있는 공간 객체의 접근 빈도를 반영해서 편향된 색인 트리를 생성하는 기법을 제안한다. 이형 클러스터링으로 분포되어 있는 전체 영역에 대해서 Zahn의 클러스터링 알고리즘을 변형시켜서 다단계 세부 영역을 구분한다. 이렇게 구분된 세부 영역에 대해서 거리적 인접성과 접근 빈도수의 합을 이용해서 색인 트리를 생성한다. 또한 다단계로 구성된 전체 영역에 대해서 하향식 방식으로 편향된 색인 트리를 생성함으로써, 접근 빈도가 높은 공간 객체에 대해서 빠른 탐색이 가능하게 한다. Because of the advancement of GPS and PDA, applications using spatial data like Location Based Service(LBS), Car Navigation System(CNS) and Geographic Information System(GIS) has been widely used. Most of these applications provide indexes for data using height-balanced indexing techniques. However, those techniques doesn't consider the access frequency of each spatial object. Though some indexing techniques which consider frequency can provide the skewedness effected by the frequency, it's not suitable when spatial objects are massed. Because, to work efficiently, they also have to consider the distance between spatial objects when it's more than 2 dimensions. In this paper, we propose a new indexing technique which can make an skewed index tree considering the distance and access frequency. It divides the area into multistaged subareas using a revised version of Zahn's clustering algorithm. It considers the sum of distance and access frequency between the subareas when it builds the index tree. Also the index tree is built with a top-down approach using density as a criterion. As the search starts from the root with the highest density, it enables fast search.
무선 브로드캐스트 환경에서 편향된 엑세스 패턴을 가진 모바일 트랜잭션을 위한 효과적인 동시성 제어 기법
정성원(Sungwon Jung),박성근(Sunggeun Park),최근하(Keunha Choi) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.1
브로드캐스트는 하나 또는 여러 개의 채널을 이용해서 다수의 모바일 클라이언트들이 빈번하게 필요로 하는 데이타를 효과적으로 전송하기 위한 방법 중의 하나이다. 무선 브로드캐스트 환경에서는 채널의 상향 대역폭의 한계로 인해 기존의 동시성 제어 기법은 적합하지 않다. 무선 브로드캐스트 환경에서 서버는 종종 모바일 클라이언트의 접근 패턴을 고려하여 편향된 접근 빈도를 갖는 서로 다른 데이타 아이템을 브로드캐스트 하기도 한다. 무선 브로드캐스트 환경에서 모바일 트랜잭션을 위한 기존의 제안된 동시성 제어 기법들은 일정한 데이타 접근 패턴에 중점을 두고 있다. 하지만, 기존의 기법들은 데이타의 접근 패턴이 일정하지 않고 편향된 경우에는 오히려 심각한 성능 저하를 발생시킨다. 편향된 데이타 접근 패턴을 갖는 갱신 모바일 트랜잭션들은 높은 접근 빈도를 같은 데이타를 동시에 접근하고자 하는 다른 모바일 트랜잭션들 간의 충돌로 인해 실행이 취소되고 재실행될 것이다. 본 논문에서는 일정한 데이타 접근 패턴뿐만 아니라 편향된 데이타 접근 패턴을 갖는 모바일 트랜잭션을 위한 에너지 효율적인 동시성 제어 기법을 제안한다. 본 논문에서는 임의 백오프 기법을 통해 갱신 모바일 트랜잭션의 빈번한 실행 취소와 재실행을 방지한다. 우리는 기존의 동시성 제어 기법과의 비교를 통해 본 논문에서 제안하는 기법을 심층적으로 분석한다. 또한 실험을 통해 기존의 기법들에 비해 평균 접근 시간, 상향 및 하향 통신 대역폭의 사용량이 현저히 줄어드는 것을 보임으로써 제안하는 기법의 성능을 검증한다. Broadcast has been often used to disseminate the frequently requested data efficiently to a large volume of mobile clients over a single or multiple channels. Conventional concurrency control protocols for mobile transactions are not suitable for the wireless broadcast environments due to the limited bandwidth of the up-link communication channel. In wireless broadcast environments, the server often broadcast different data items with different frequency to incorporate the data access patterns of mobile transactions. The previously proposed concurrency control protocols for mobile transactions in wireless broadcast environments are focused on the mobile transactions with uniform data access patterns. However, these protocols perform poorly when the data access pattern of update mobile transaction are not uniform but skewed. The update mobile transactions with skewed data access patterns will be frequently aborted and restarted due to the update conflict of the same data items with a high access frequency. In this paper, we propose an energy-efficient concurrency control protocol for mobile transactions with skewed data access as well as uniform data access patterns. Our protocol use a random back-off technique to avoid the frequent abort and restart of update mobile transactions. We present in-depth experimental analysis of our method by comparing it with existing concurrency control protocols. Our performance analysis show that it significantly decrease the average response time, the amount of upstream and downstream bandwidth usage over existing protocols.