이동 컴퓨팅 환경에서 방송 데이타를 위한 색인 방법

정연돈(Yon Dohn Chung),김명호(Myoung Ho Kim) 한국정보과학회 1998 정보과학회논문지(B) Vol.25 No.4

데이타 방송 기법은 주파수 효율성과 에너지 효율성이라는 두가지 좋은 성질을 지니고 있기 때문에 이동 컴퓨팅 분야에서 중요한 역할을 하고 있다. 본 논문에서는 방송 데이타를 위해 제안된 기존색인 방법의 문제점을 해결하는 효율적인 색인 기법들을 제안한다. 먼저 무선 데이타 방송에 적합한 색인기법의 조건들을 제시하고 이를 만족하는 3가지의 기법(FL,NL,SL)을 제안한다. 분석적인 방법과 실험을 통해 제안한 방법들과 기존 방법을 비교, 평가하고 그 결과를 바탕으로 제안한 방법이 기존의 방법에 비하여 우수한 성능을 가지고 있음을 보인다. Data broadcasting is important in mobile computing because it is bandwidth-efficient and energy-efficient. In this paper we propose new efficient index mechanisms for broadcast data in mobile computing that overcomes the problem in the previous indexing method. We first describe the criteria for an appropriate indexing for wireless broadcast data and then develop three methods, FL, NL and SL that satisfy the given criteria. We evaluate the proposed three methods and compare them with the previous one in analytic and experimental ways. We show through the performance comparisons that the proposed methods perform better than the one proposed earlier.

이동 컴퓨팅을 위한 방송 데이타 구성 기법

정연돈(Yon-Dohn Chung),이윤준(Yoon-Joon Lee),김명호(Myoung-Ho Kim) 한국정보과학회 1996 정보과학회논문지(B) Vol.23 No.12

이동 컴퓨팅 환경에서는 여러가지 목적으로 데이타 방송 기법을 사용한다. 그 이유는 데이타 방송 기법이 지니는 에너지 효율성과 주파수 효율성이라는 특성 때문이다. 본 연구에서는 이동 컴퓨팅을 위한 ICC 방송 기법을 제안한다. ICC 방송 기법은 방송 데이타의 색인부에 캐시 제어 정보를 포함하는 방식이다. 캐시 제어 정보를 사용함으로써 이동 클라이언트들은 보다 적은 튜닝 시간으로 방송 데이타를 수신 할 수 있다. 또한 방송 데이타의 구성에 있어 에너지 효율성을 좀 더 높일 수 있는 방안을 함께 제시한다. 실험을 통하여 제안한 방법이 기존 방법보다 우수한 성능을 나타냄을 보인다. Data broadcasting in mobile computing environment has many applications because it has an excellent energy-efficiency and bandwidth-efficiency characteristics. In this work, we propose an ICC data broadcasting scheme for mobile computing. In this scheme we incorporate cache control information into the index broadcasted with data. By utilizing cache control information, data tuning costs are considerably reduced when mobile clients listening broadcast data. In addition, we recommend a method for data stream construction for further improvement of energy-efficiency. We perform simulation experiments for our proposed scheme and show that the proposed scheme works better than those proposed earlier.

동적 분산 색인 기법

정연돈(Yon-Dohn Chung),김명호(Myoung-Ho Kim),이윤준(Yoon-Joon Lee) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.2A

이동 컴퓨팅 환경에서는 에너지 용량의 제한과 주파수 대역의 제약이 중요한 문제점으로 인식되고 있다. 이들 문제점을 극복하기 위하여 방송이라는 통신 방법을 많이 사용하고 있다. 본 논문은 무선 데이타 방송에 사용되는 색인 기법인 분산 색인 방법의 문제점을 지적하고 이를 개선한 동적 분산 색인 기법을 제안한다. 그리고 분석을 통해 제안한 색인 방법이 기존보다 우수한 성능을 지님을 보인다.

무선 XML 스트림을 위한 색인 기법

정연돈(Yon Dohn Chung),이지연(Ji Yeon Lee) 한국정보과학회 2005 정보과학회논문지 : 데이타베이스 Vol.32 No.4

본 논문은 무선 정보 시스템 환경에서, 서버가 다수의 클라이언트들에게 무선 방송 기법을 통해 XML 데이타를 스트리밍 서비스할 때 필요한 색인 기법을 제안한다. 제안 하는 색인 방법은 XML 데이타의 스트리밍시 클라이언트들의 접근 시간 및 튜닝 시간을 효과적으로 제어하기 위하여, XML 데이타 및 색인 정보를 부분적으로 반복, 배치하여 스트림을 구성한다. 이를 위하여 트리형태로 표현되는 XML 데이타와 색인 정보를 2-레벨로 구분하여, 색인 및 데이타의 중복 배치 영역을 설정한다. 제안하는 색인기법의 성능을 접근 시간 및 튜닝 시간 측면에서 분석하여, 분석의 결과로 최적의 레벨 깊이를 결정한다. In the paper, we propose an index method for XML streaming services, where a server broadcasts XML data to a lot of clients in wireless information systems. In order to control the access and tuning time of mobile clients, the proposed method constructs the XML stream through replicating partial index intermixed with parts of data. For this purpose, we propose a two-level tree structure for separating index and XML data into two parts: replicated vs. non-replicated. We analyze the performance of the proposed method with respect to access time and tuning time. With the analysis result, we derive the optimal level value.

B2V - Tree : 무선 데이타 스트림에서 부분 부합 질의를 위한 색인 기법

정연돈(Yon Dohn Chung),이지연(Ji Yeon Lee) 한국정보과학회 2005 정보과학회논문지 : 데이타베이스 Vol.32 No.3

이동 분산 환경에서는 무선 데이타 방송 기법을 통하여 서버의 데이타 레코드들을 이동 사용자들에게 전달하는 방식이 많이 사용된다. 그리고, 무선 방송 스트림에서 데이타를 에너지 효율적으로 접근하기 위해서는 색인 기법이 필요하다. 하지만, 기존의 색인 기법들은 데이타 레코드의 키 값을 이용한 트리 형태의 색인 구조를 사용하고 있다. 따라서 부분 부합 질의 등과 같은 내용 기반 검색 질의를 지원할 수 없었다. 본 논문에서는 무선 방송으로 이동 사용자들에게 전달되는 데이타 스트림에서 내용 기반 검색인 부분 부합 질의를 지원하기 위해 B2V-Tree라고 불리는 색인 기법을 제안한다. 본 논문에서 제안하는 B2V-Tree는 데이타 레코드들의 애트리뷰트 값을 다중 애트리뷰트 해싱을 통해 비트 벡터로 생성한 다음, 이들을 색인 트리로 구성하는 색인 기법이다. In mobile distributed systems the data on the air can be accessed by a lot of mobile clients. And, we need an indexing scheme in order to energy-efficiently access the data on the wireless broadcast stream. In conventional indexing schemes, they use the values of primary key attributes and construct tree-structured index. Therefore, the conventional indexing schemes do not support content-based retrieval queries such as partial-match queries. In this paper we propose an indexing scheme, called B2V-Tree, which supports partial match queries on wireless broadcast data stream. For this purpose, we construct a tree-structured index which is composed of bit-vectors, where the bit-vectors are generated from data records through multi-attribute hashing.

XML 질의의 효율적인 전처리를 위한 시그너처 방법

정연돈(Yon Dohn Chung),김종욱(Jong Wook Kim),김명호(Myoung Ho Kim) 한국정보과학회 2003 정보과학회논문지 : 데이타베이스 Vol.30 No.5

본 논문은 대량의 XML 문서들이 존재하는 정보 검색 시스템에서, XML 질의의 효과적인 처리를 위한 선 처리 방법을 제안한다. 선 처리를 위해 시그너처 기반의 접근 방식을 사용한다. 기존의 (평면적인 문서를 사용하는) 정보 검색 시스템에서는, 대부분 사용자 질의들이 키워드와 부울 연산자로 구성되고, 따라서 시그너처 역시 평면적인 형태로 구성하고 있다. 하지만, XML 기반의 정보 검색 시스템에서는 사용자 질의가 경로 질의의 형태를 띄게 된다. 따라서, 평면적인 시그너처는 XML 문서에 대하여 효과적이지 못하다. 본 논문에서는 XML 문서를 위한 구조화된 시그너처 방법을 제안한다. 실험을 통해 제안하는 방법의 성능을 평가한다. The paper proposes a pre-processing method for efficient processing of XML queries in information retrieval systems with a large amount of XML documents. For the pre-processing, we use a signature-based approach. In the conventional (flat document-based) information retrieval systems, user queries consist of keywords and boolean operators, and thus signatures are structured in a flat manner. However, in XML-based information retrieval systems, the user queries have the form of path query. Therefore, the flat signature cannot be effective for XML documents. In the paper, we propose a structured signature for XML documents. Through experiments, we evaluate the performance of the proposed method.

다중 서버 환경에서의 퍼지 개념을 이용한 작업 할당 기법

정연돈(Yon Dohn Chung),김종수(Jong Soo Kim),이지연(Ji Yeon Lee),오석균(Seok Kyun Oh),이광형(Kwang Hyung Lee),이윤준(Yoon Joon Lee),김명호(Myoung Ho Kim) 한국지능시스템학회 1997 한국지능시스템학회논문지 Vol.7 No.5

균등 무선 방송에서 사용자 접근 시간 최소화를 위한 데이타 스케쥴링 기법

정연돈(Yon Dohn Chung),김명호(Myoung Ho Kim) 한국정보과학회 1999 정보과학회논문지(B) Vol.26 No.9

이동 분산 환경에서는 무선 데이타 전송 기법을 통하여 사용자들에게 다양한 정보들을 전달하게 된다. 본 논문은 균등 무선 데이타 방송 환경에서, 빠른 시간에 방송데이터를 접근할 수 있는 방법에 대하여 기술한다. 이를 위하여 무선 방송 데이타의 스케쥴링 문제를 정의하고, 어떤 질의가 접근하는 데이타들의 응집 정도를 나타내는 '질의 거리(Query Distance: QD)'라는 측정 기준을 제시한다. 제안한 질의 거리를 사용하여 각 질의의 우선 순위에 따라 해당 질의가 접근하는 데이타 집합을 방송 스케쥴에 추가하면서 스케쥴을 구성하는 데이타 스케쥴링 기법을 제시한다. 데이타 집합의 스케쥴 구성 과정에서 우선 순위가 높은 질의의 질의 거리를 최소화하면서 낮은 우선 순위 질의들의 질의 거리를 줄이는 스케쥴 확장 규칙들을 사용한다. 예를 이용하여 제안하는 방법에 대하여 설명한 후, 실험을 통해 제안한 방법의 성능을 평가한다. In mobile distributed systems the data on the air can be accessed by a lot of clients. This paper describes the way clients access the broadcast data in short latency in uniform wireless broadcasting environment. We define the problem of wireless data scheduling and propose a measure, named Query Distance(QD), which represents the coherence degree of data set accessed by a query By using the measure, we give a data scheduling method that constructs the broadcast schedule by appending each query's data set in greedy way. When constructing the schedule, we use schedule expansion rules that reduce the QD's of lower-frequency queries while minimizing the QD's of the higher-frequency ones With the use of examples we illustrate the mechanism of the proposed method and we test the performance of our method.

무선 정보 시스템에서의 다이버젼스 캐슁을 위한 인덱싱 기법

정연돈(Yon-dohn Chung),이윤준(Yoon Joon Lee),김명호(Myoung Ho KIM) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.2A

급속한 전파기술의 발달과 증가하는 사용자의 정보요구는 이동 컴퓨팅(Mobile Computing)이라는 새로운 분야를 만들어 내고 있다. 이러한 분야중에서 전파를 통해 사용자들에게 여러 가지 정보 서비스들을 제공하는 무선 정보 시스템(Wireless Information System)이라는 환경이 있다. 본 논문에서는 무선 정보 시스템에서 방송(Broadcating)의 형태로 제공하는 정보 데이타에 대해서 인덱스를 사용함에 있어 동적 위치 정보와 다이버젼스 제어 정보를 이용하는 방법을 제안한다. 두가지의 캐쉬 제어정보를 인덱스에 포함시킴으로써 데이타의 수신에 있어 이동 사용자로 하여금 최소의 에너지 사용으로 원하는 정보를 얻을 수 있도록 한다. 제안한 방법에 대해 실험을 통해 기존의 방법과의 성능 비교를 보인다.

이동 컴퓨팅 환경에서 연속 부분 부합 질의의 효과적인 처리를 위한 캐시 관리 방안

정연돈(Yon Dohn Chung),이지연(Ji Yeon Lee),이윤준(Yoon Joon Lee),김명호(Myoung Ho Kim) 한국정보과학회 2001 정보과학회논문지 : 데이타베이스 Vol.28 No.2

본 논문은 이동 컴퓨팅 환경에서 연속 부분 부합 질의의 효과적인 처리를 위한 캐시 관리 방안을 제안한다. 연속 부분 부합 질의란 질의의 결과가 클라이언트의 메모리에 일관성을 유지하면서 지속되는 부분 부합 질의이다. 기존의 이동 환경을 위한 캐시 관리 기법은 레코드 식별자를 기반으로 하는 방법들이다. 하지만, 부분 부합 질의는 데이타의 내용을 기반으로 탐색하는 질의이기 때문에 이러한 레코드 식별자를 기반으로 하는 방법들은 캐시 관리를 효율적으로 할 수 없다. 제안하는 캐시 관리 방안에서는, 이동 클라이언트의 캐시 상태를 프레디킷(predicate)으로 기술하고, 서버가 캐시 관리를 위해 클라이언트에게 방송하는 캐시 무효화 정보, 즉 Cache Invalidation Reports (CIR)을 프레디킷으로 구성한다. 이러한 프레디킷 표현을 사용하여, 일련의 캐시 관리 기법-억지 방법 (the brute-force method), 빼기 방법 (the subtraction method), 교차 방법 (the intersection method)-들을 제안한다. 그리고, 제안하는 방법의 계산 복잡도를 계산한다. This paper proposes a cache management scheme for effective processing of continuous partial match queries in mobile computing environments. The continuous partial match query is a partial match query whose result continues to exist consistently in the client's memory. Conventional cache management methods for mobile environments are record ID-based ones. However, since the partial match query is a content-based retrieval, the record ID-based approach does not manage the cache efficiently. In our proposed scheme, we represent the cache state of a mobile client as a predicate, and construct the cache invalidation reports (which the server broadcasts to clients for cache management) with predicates. Using the predicate representation, we also propose a set of cache management methods: the brute-force method, the subtraction method, and the intersection method. And, we analyze the computational complexity of the proposed methods.