[논문]범위 질의 인덱싱을 이용한 스트림 데이터의 다중 질의처리 기법

이동언; 이윤석

doi:10.9708/jksci.2009.14.2.069

범위 질의 인덱싱을 이용한 스트림 데이터의 다중 질의처리 기법
A Multi-dimensional Query Processing Scheme for Stream Data using Range Query Indexing 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.14 no.2, 2009년, pp.69 - 77

이동언 (한국외국어대학교 전자정보공학부) , 이윤석 (한국외국어대학교 전자정보공학부)

초록
AI-Helper

스트림 서비스 환경에서는 지속적으로 입력되는 막대한 양의 데이터에 대해 원하는 조건을 탐색하는 실시간 질의처리가 요구된다. 기존의 R-tee기반 질의처리 기술은 각 이벤트에 대해 트리 전체에 대해 동일한 탐색과정을 반복해야 하므로 이를 효율적으로 감당할 수 없었다. 한편 센서 측정값을 비롯한 대부분의 스트림 데이터는 매우 높은 지역성을 가지며 이를 활용하여 탐색 공간을 크게 줄일 수 있다. 따라서 본 연구에서는 스트림 데이터의 지역성을 활용하여 스트림 환경에 적합한 질의처리 기법을 제안하였다. 또한 이 프레임웍을 활용하여 스트림 환경에서 어플리케이션이 요구하는 다양한 질의처리 서비스를 개발할 수 있을 것으로 기대된다. 본 연구에서 구현한 프로토타입 시스템을 스트림 환경에 적용해 얻은 실험 결과를 통해, 스트림 환경에서 기존질의처리 기법보다 더 적합하고 효율이 크게 개선됨을 확인할 수 있었다.

Abstract ▼ AI-Helper

Stream service environment demands real-time query processing for voluminous data which are ceaselessly delivered from tremendous sources. Typical R-tree based query processing technologies cannot efficiently handle such situations, which require repetitive and inefficient exploration from the tree root on every data event. However, many stream data including sensor readings show high locality, which we exploit to reduce the search space of queries to explore. In this paper, we propose a query processing scheme exploiting the locality of stream data. From the simulation, we conclude that the proposed scheme performs much better than the traditional ones in terms of scalability and exploration efficiency.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

할 수 있다. 따라서, 본 연구에서는 스트림 데이터의 높은 지역성 (locality)를 활용하여 사용자의 다양한 질의 표현을 효과적으로 지원하는 다중질의처리 기법을 제안하고자 한다.
본 논문에서는 기존의 질의 처리 방법에서 문제가 되었던 스트림 환경 기반의 입력 데이터에 대한 질의 탐색성능과 다차원 질의 표현에 대한 성능 개선을 연구하고 제안하였다. 그리고 범위 질의 인덱스를 설계하여 스트림 서비스 환경에 효율적인 질의처리 시스템을 구성하였고, 이를 바탕으로 모의실험을 통해 기존 질의 처리 방법과 성능을 비교한 결과, 스트림 환경에서는 범위 질의 인덱스 방법이 다양한 질의 표현이 가능하고, 효과적으로 질의를 탐색함을 알 수 있었다.
이처럼 다양하게 스트림 서비스가 활용되고 있으며, 이 서비스는 연속적인 스트림 데이터의 특성에 적합한 질의 처리 시스템 설계를 통해 수많은 사용자들이 다양하게 질의를 등록함은 물론 빠르게 정보를 제공받는 것이 매우 중요한 목적이라고 할 수 있다. 따라서, 본 연구에서는 스트림 데이터의 높은 지역성 (locality)를 활용하여 사용자의 다양한 질의 표현을 효과적으로 지원하는 다중질의처리 기법을 제안하고자 한다.

제안 방법

실제로 지역성을 가지는 스트림 데이터의 특징을 나타내기 위해 Fluctuation Level을 설정하여 스트림 데이터를 생성하였다. Fluctuation Levele 현채입력된 데이터 다음에 입력될 데이터가 나타나게 되는 범위로써 실제 스트림 데이터의 특징을 표현하기 위해 설정하였다. [그림 1이과 같이 Fluctuation Level의 변화를 두어 지 역성을 가지는 경우와 아닌 경우 제안한 질의 처리 시스템이 스트림 환경에 얼마나 적합한지를 측정하기 위해 Fluctuation Level (0.
Fluctuation Levele 현채입력된 데이터 다음에 입력될 데이터가 나타나게 되는 범위로써 실제 스트림 데이터의 특징을 표현하기 위해 설정하였다. [그림 1이과 같이 Fluctuation Level의 변화를 두어 지 역성을 가지는 경우와 아닌 경우 제안한 질의 처리 시스템이 스트림 환경에 얼마나 적합한지를 측정하기 위해 Fluctuation Level (0.1 ~ 1.0%)를 두어 Uniform Random Generation 하였다. 그리고 Stream Data 는 10, 000개로 동일하게 실험 하였다.
하지만 본 연구에서 제안하는 범위 질의 인덱스 기법은 [그림 7〕과 같이 1차원 범위 질의인덱스를 각 차원별로 각각 구성하여 다차원 질의 처리를 구성하였다. 그리고 질의정보를 알려주는 Query Table 또한 각 차원별로 제공하고, 각 차원에 대한 표현 방법을 알려주는 Operator를 두어서 Query 표현(온도&& 습도, 온도, 습도, 온도, 습도 등)을 다양하게 등록할 수 있도록 하였다. 이와 같이 각 차원마다 독립적으로 질의 정보를 구성하기 때문에 질의의 확장을 편리하게 할 수 있는 장점이 있다.
이를 통해[그림 2(b)〕처럼 수집된 센서 정보를 분석하여 교량의 상태를 쉽게 모니터링함으로 더욱 정밀하고 안전한 유지, 보수가 가능하게 되었다.또한 각 센서에 대해 다수의 사용자(또는 시스템) 가다양한 종류의 질의를 통해 교량의 상태 정보를.제공받을 수 있게 되었다.
범위 질의 인덱스에 대한 질의 처리 성능 평가를 위해 질의의 수, 질의 범위, 스트림 데이터의 변화 범위를 각각 변화시키면서 실험을 진행하였다.
것을 알 수 있다. 본 실험에서는 앞서의 모의실험 환경 하에, 기존의 R-트리를 사용한 방법과 본 연구에서 제안한 방법의 성능을 비교하였다.
사용자 질의는[그림 11〕에 보이는 바와 같이 2차원 질의를 기반으로 World Space 0 ~ 10, 000범위 안에서 Uniform Random Generation (Generation Tool : Spatial Data Generator (c), University of Pireaus) 프로그램을 사용하여 무작위로 생성하였다. 질의를 1,000 ~ 10, 000개까지 생성하면서 실제 스트림 환경에서 질의의 수가 질의 처리에 미치는 영향에 대해 실험하였다.
특징은 다음과 같다. 실제로 지역성을 가지는 스트림 데이터의 특징을 나타내기 위해 Fluctuation Level을 설정하여 스트림 데이터를 생성하였다. Fluctuation Levele 현채입력된 데이터 다음에 입력될 데이터가 나타나게 되는 범위로써 실제 스트림 데이터의 특징을 표현하기 위해 설정하였다.
사용하여 무작위로 생성하였다. 질의를 1,000 ~ 10, 000개까지 생성하면서 실제 스트림 환경에서 질의의 수가 질의 처리에 미치는 영향에 대해 실험하였다.
매우 높은 복잡도를 갖는다. 하지만 본 연구에서 제안하는 범위 질의 인덱스 기법은 [그림 7〕과 같이 1차원 범위 질의인덱스를 각 차원별로 각각 구성하여 다차원 질의 처리를 구성하였다. 그리고 질의정보를 알려주는 Query Table 또한 각 차원별로 제공하고, 각 차원에 대한 표현 방법을 알려주는 Operator를 두어서 Query 표현(온도&& 습도, 온도, 습도, 온도, 습도 등)을 다양하게 등록할 수 있도록 하였다.

성능/효과

그리고 범위 질의 인덱스를 설계하여 스트림 서비스 환경에 효율적인 질의처리 시스템을 구성하였고, 이를 바탕으로 모의실험을 통해 기존 질의 처리 방법과 성능을 비교한 결과, 스트림 환경에서는 범위 질의 인덱스 방법이 다양한 질의 표현이 가능하고, 효과적으로 질의를 탐색함을 알 수 있었다.
그리고 1차원과 동일하게 Query Table이 인덱스를 단계적으로 이동하면서 변화되기 때문에 [그림 9〕 에 보이 는 바와 같이 첫 번째 데이터가 입력되고 두 번째 데이터가 입력되었을 때 첫 번째 데이터가 만족하는 Query 1 과 두 번째 데이터가 만족하는 Query 3만 알려주는 것이 아니라 Query 2가지나왔던 사실 또한 알려줄 수 있다. 다차원범위 질의 인덱스도 역시 기존 질의 처리 방법에서 해결되지 못한 입력 데이터 변화에 대한 질의 변화를 알 수 있어 스트림 서비스 환경에 보다 적합하다는 것을 알 수 있다.
실험 결과에서 보듯이 지역성이 적은 스트림 데이터가 입력되는 스트림 환경에서는 제안한 범위 질의 인덱스가 기존질의처리 방법보다 더욱 더 빠르고 안정적인 질의 처리 결과를 얻는다는 것을 알 수 있다. 본 실험에서는 앞서의 모의실험 환경 하에, 기존의 R-트리를 사용한 방법과 본 연구에서 제안한 방법의 성능을 비교하였다.
그리고 A 노드가 가리키는 영역으로 이동한다. 이동한 영역에 있는 D, E, F, G 노드를 확인하고 만족하는 G 노드를 찾은 다음 더 이상 가리키고 있는 경로가 없다는 사실을 판단한 뒤 모든 탐색을 종료한다. 결국 입력한 데이터가 질의 G를 만족하고 있다는 사실을 알려주게 된다.
그래프에서 보듯이 R-트리의 경우 질의의 개수가 많아질수록 탐색하는 영역이 많아지게 되고 중복되는 영역도 늘어나기 때문에 질의 탐색 횟수는 계속 늘어나게 된다. 하지만 제안한 범위 질의 인덱스 방법은 질의의 개수에 따른 영향보다는 스트림 데이터의 변동률 즉 지역성에 따라 인덱스를 탐색하는 횟수가 결정되기 때문에 지역성을 가진 스트림 데이터가 입력되면 거의 변동 없이 질의를 찾게 된다.

후속연구

향후 연구방향으로 본 논문에서 제안한 범위 질의 인덱스를 실제 스트림 서버 아키텍처를 구현하여 실제 사용자가 다중 질의를 등록하는 환경에서 성능 평가를 하는 것이다. 또한 실제 스트림 데이터를 이용하여 질의 처리에 대한 성능 평가를추가적으로 수행해야 한다.

참고문헌 (12)

Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching," Proc. ACM SIGMOD, pp. 47-57, June 1984.
Mladen Bestvina, "R-Trees in topology, geometry, and group theory," Handbook of geometric topology R. J. Daverman and R. B. Sher(editors), January 18, 1999.
Timos Sellis, Nick Roussopoulos and Christos Faloutsos, "The R+ Tree: A dynamic index for multi-dimensional objects," Department of Computer Science University of Maryland College Park, 1987.
Stefan Berchtold, Daniel A. Keim. Hans-Peter Kriegel, "The X-tree: An Index Structure for High-Dimensional Data," Institute for Computer Science, University of Munich, The 22ndLVDB Conference Mumbai (Bombay), India, 1996.
J. Lee, Y. Lee, S. Kang, S. Lee, H. Jin, B. Kim, J. Song, "BMQ-Index: Shared and Incremental Processing of Border Monitoring Queries over Data Streams," Korea Advanced Institute of Science and Technology. MDM'06, 2006.
The Medusa Distributed Stream-Processing System, Magdalena Balazinska, Hari Balakrishnan, Jon Salz and Mike Stonrbraker, MIT Computer Science and Artificial Intelligence Lab, http://nms.lcs.mit.edu/projects/medusa/.
Kim, W., "Completeness Criteria for Object-Relational Database Systems," UniSQL inc., 1996.
Ron Avnur, "Eddies : Continuously Adaptive Query processing," Univ of Berkeley, IEEE Network. January/February 2004.
서 석호, "고속 스트림 데이터에 대한 연속 질의 처리 아키텍처의 설계," 한국 외국어 대학교 전자정보공학과 석사학위논문, 2005년.
이 석호, "파일 구조," 정익사, 2007년.
한국철도기술연구원 2005. 11. 10 기술 소개, "교량에 설치된 센서의 종류 및 위치," 2005년.
건설기술정보, "계측 센서 별 측정값 비교," 2001년.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증