The continuous advance of digital mobile communication technology coupled with the recent proliferation of portable computers has led development efforts for future mobile information systems toward mobile computing - a new paradigm of future communication and computing networks. This thesis addresses clustering and caching of wireless data for partial match queries.
First, we propose a wireless broadcast data clustering method for partial match queries. A partial match query retrieves data records by specifying some non-key attributes. Because it uses a content-based retrieval, it has been widely used in various applications in wireless and (or) wireline systems. The method utilizes the clustering properties of Gray codes. We analyze clustering effects of the proposed method using the `Query Distance` measure, and evaluate the performance with comparison of other methods.
Second, we propose a cache management scheme for mobile clients that use continuous partial match queries. A continuous partial match query is a partial match query whose result remains in a consistent manner in the client`s memory. The conventional cache management methods for mobile environments are based on record ID`s, thus they cannot properly manage the cache of mobile clients using partial match queries. In the thesis, we propose a predicate-based cache management scheme, where the cache state of a mobile client and cache invalidation reports (CIR) are represented by partial match predicates. We also propose a set of methods for CIR construction and identification of invalidated parts of client`s cache. We show the effectiveness of the proposed caching scheme with a brief evaluation, and analyze the complexity of proposed algorithms.
The proposed clustering and caching methods can be effectively used for mobile clients using partial match queries. The server broadcasts data by using the proposed clustering method and mobile clients cache data records by using the proposed caching scheme. With the proposed methods, we can improve the access time performance of wireless information systems.
근래에 들어 무선 통신과 휴대용 컴퓨터의 비약적인 확산으로 인하여 사용자가 이동하면서
정보를 검색, 처리할 수 있도록 하는 이동 컴퓨팅(mobile computing)이라는 환경이 새롭게 부각되고 있다. 본 논문에서는 이러한 무선 통신 환경에서 중요하게 다루어지는 방송 데이터 클러스터링과 클라언트의 캐시 방법을 제안하고자 한다.
먼저 본 논문에서는 사용자가 부분 부합 질의(Partial Match Query)를 사용하는 환경에서,
보다 빠른 시간에 방송 데이터를 접근할 수 있도록 그레이 코드(Gray code) 기법을 이용하여 방송 데이터를 클러스터링하는 방법을 제안한다. 제안한 그레이 코드 기법으로 방송 데이터를 클러스터링 시, 부분 부합 질의에 대해 어떤 클러스터링 효과를 갖는지를 `질의 거리(Query Distance)`라는 측정 기준을 사용하여 알아본다. 그리고, 이진 코드(binary code) 클러스터링 기법으로 클러스터링하는 경우와 비교 분석하고, 제안한 그레이 코드 클러스터링 기법의 성능 향상을 보인다.두 번째로, 본 논문에서는 이동 컴퓨팅 환경에서 연속 부분 부합 질의를 위한 캐시 관리 방안을 제안한다. 연속 부분 부합 질의란 질의의 결과가 클라이언트의 메모리에 일관성을 유지하면서 지속되는 부분 부합 질의을 말한다. 기존의 이동 환경을 위한 캐시 관리 기법은 레코드 식별자를 기반으로 하는 방법들이다. 그러나, 부분 부합 질의는 데이터의 내용을 기반으로 탐색하는 질의이기 때문에 이러한 레코드 식별자를
기반으로하는 방법들을 사용할 경우 캐시 관리를 효과적으로 할 수 없다. 제안하는 캐시 관리 방안에서는, 이동 클라이언트의 캐시 상태를 부분 부합 프레디킷으로 기술하고, 서버가 캐시 관리를 위해 클라이언트에게 방송하는 캐시 무효화 정보를 부분 부합 프레디킷으로 구성한다. 이러한 부분 부합 프레디킷 표현을 사용하여, 일련의 캐시 관리 기법-억지 방법, 빼기 연산 방법, 교차 연산 방법-등을 제안한다. 그리고, 제안하는제안한 그레이 코드 클러스터링 방법과 캐시 관리 방법은 무선 데이터 방송 시, 사용자가 부분 부합 질의를 통하여 데이터를 검색, 처리하는 환경에 유용하게 이용될 수 있다. 서버 측에서는 그레이 코드 클러스터링 방법으로 방송 데이터의 순서를 결정하여 보냄으로써 전체 사용자의 평균 접근 시간(access time)을 줄일 수 있고, 클라이언트 측에서는 제안한 캐시 관리 방법을 사용하여 원하는 데이터들에 대한 접근 시간을 줄일 수 있다. 실험과 분석을 통하여 무선 데이터 방송 시스템에서 성능이 향상됨을 보인다.
방법들의 계산 복잡도를 분석한다.
