[논문]부분매칭 경로질의를 위한 포스트픽스 공유에 기반한 스트리밍 XML 데이타 필터링 기법

박석; 김영수

부분매칭 경로질의를 위한 포스트픽스 공유에 기반한 스트리밍 XML 데이타 필터링 기법
A Filtering Technique of Streaming XML Data based Postfix Sharing for Partial matching Path Queries 원문보기

정보과학회논문지. Journal of KIISE. 데이타베이스, v.33 no.1, 2006년, pp.138 - 149

초록
AI-Helper

센서 네트워크나 유비쿼터스 환경이 보급되면서 최근에는 저장되어 있는 데이타가 아닌 계속적으로 빠르게 지나가는 스트리밍 데이타에 대한 연구가 활발하게 이루어지고 있다. 기존의 Publish-Subscribe 시스템도 인터넷의 발달로 데이타가 실시간으로 빠르게 들어오는 스트리밍 데이터의 형태를 가지게 되면서 스트리밍 데이타 연구에 관심을 가지게 되었고 이 중에서도 웹 환경의 표준으로 많이 사용되는 XML에 관심을 가지게 되었다. Publish-Subscribe 시스템에서 서버에 들어오는 스트리밍 XML 데이타에 대해서 질의에 빠르게 매치(match)되는 것을 찾기 위한 스트리밍 XML 데이타 필터링 기법이 오토마타를 이용해서 연구되었으며, 이중에서 비결정적 오토마타를 사용한 방법이 YFilter이다. 비결 정적 오토마타를 사용하는 YFilter의 경우 질의 앞부분의 공통된 오퍼레이터를 한번에 계산하기 위해서 XPath 질의의 공통된 앞부분을 공유하고 질의의 루트부터 처리하는 하향식 방식을 사용하고 있다. 하지만, 부분매칭 경로질의의 경우에는 질의의 앞부분 공유를 방해하고 질의를 루트에서부터 처리할 필요가 없기 때문에 YFilter에서 부분매칭 경로질의가 증가하면 처리량이 떨어지는 문제가 발생한다. 본 논문에서는 이 문제 대해 XPath 질의의 공통된 뒷부분 공유에 기반한 상향식 방식을 사용하는 PoSFilter를 한가지 해결책으로 제시한다. 그리고 YFilter와 PoSFilter의 처리량을 비교를 통해서 PoSFilter의 경우 부분매칭 경로질의가 증가할 때 YFilter보다 좋은 처리량을 나타내는 것을 검증한다.

Abstract ▼ AI-Helper

As the environment with sensor network and ubiquitous computing is emerged, there are many demands of handling continuous, fast data such as streaming data. As work about streaming data has begun, work about management of streaming data in Publish-Subscribe system is started. The recent emergence of XML as a standard for information exchange on Internet has led to more interest in Publish - Subscribe system. A filtering technique of streaming XML data in the existing Publish- Subscribe system is using some schemes based on automata and YFilter, which is one of filtering techniques, is very popular. YFilter exploits commonality among path queries by sharing the common prefixes of the paths so that they are processed at most one and that is using the top-down approach. However, because partial matching path queries interrupt the common prefix sharing and don't calculate from root, throughput of YFilter decreases. So we use sharing of commonality among path queries with the common postfixes of the paths and use the bottom-up approach instead of the top-down approach. This filtering technique is called as PoSFilter. And we verify this technique through comparing with YFilter about throughput.

주제어

AI 본문요약
AI-Helper

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

문제 정의

그다음에 가 들어오면 스택에 다시 상태1을 푸쉬하고 이 들어오면 스택의 탑의 상태1에서 email 엘리먼트로 어디로 이동할 수 있는지 살펴본다.
나) 다음에 질의가 들어오면 우선 기존에 들어온 XPath 질의 오토마타의 마지막 상태들을 저장한 리스트를 보고 이 안에서 들어온 질의가 기존의 질의들과 칠의의 앞부분이 공유될 수 있는지 살펴본다. 질의의 앞부분이 공유될 수 있다면 공유하여 최대 공유될 수 있는 오토마타 상태를 저장해둔다.
하지만, YFilter의 경우 부분 매칭 경로 질의가 증가하면 처리량이 떨어지는 문제점이 존재했다. 본 논문에서는 이런 문제점을 해결하기 위해서. 새로운 스트리밍 XML 필터링 기법으로 PoS- Fiiter를 제안하고 있다.
Publish-Subscribe 시스템[1, 2]은 데이타가 서버에 들어올 때 그 데이타들 중에서 원하는 데이타를 얻기 위해서 사용자가 질의를 등록하면 이 질의들은 서버에 저장되고 사용자들이 등록한 질의에 대해서 들어오는데 이 타에 매치하는 질의가 있다면 해당 질의를 등록한 사용자에게 매치된 데이타를 보내주는 시스템이다. 본 연구에서는 이 시스템에서 발생하는 데이타가 스트리밍 XML 데이타인 경우인 XML-based Publish- Subscribe 시스템에 대해 연구하고 있으며, 이 경우에 스트리밍 XML 데이타의 형태로 들어온 XML 문서가 사용자가 등록한 XPath 질의에 매치되면 해당 XML 문서를 질의를 보낸 사용자에게 보내준다. Publish- Subscribe 시스템에서 스트리밍 XML 데이타 필터링 기법은 스트리밍 XML 데이타 형태로 들어온 XML 문서가 어떤 질의에 매치되는지 빠르게 알려주기 위한 기법이다, 그림 1은 Publish-Subscribe 시스템의 한 예를 보여주고 있다.
이 실험에서는 사용자가 등록한 모든 질의가 부분 매칭 경로 질의이고 질의의 수가 증가할 때 YFilter와 PoSFilter의 처리량의 변화를 알아보려고 한다. 그림 9는 질의가 모두 부분 매칭 경로 질의이며 질의의 개수가 100, 500, 1000일 때의 결과를 나타내고 있다.
이 실험에서는 정해진 질의 수에 대해서 부분 매칭 경 로질의 비율이 변할 때 그에 따른 두 개의 필터링 기법의 처리량을 비교하기 위한 실험이다. 질의의 수는 100이고 부분 매칭 경로 질의의, 비율이 0%, 20%, 40%, 60%, 80%, 100%로 변경된다.
스트리밍 XML 필터링 기법에서는 XPath의 질의 종류 중에서 어떤 질의가 들어올지 모르기 때문에 질의 종류에 따라 처리량이 떨어지는 것은 문제가 된다. 하지만 YFilter의 경우에는 질의의 공통적인 앞부분 공유 (prefix sharing)에 기반한 하향식(top- down) 비결정적 오토마타를 사용하기 때문에 부분 매칭 경로 질의가 증가하면 처리량이 떨어지는 문제점이 존재한다 본 논문은 부분 매칭 경로 질의에서 처리량이 떨어지는 문제에 대한 새로운 필터링 기법으로 질의 뒷부분 공유(postfix sharing)에 기반한 상향식(bottom-up) 비결정적 오토마타를 사용하는 해결책을 제시한다. 제시한 해결책은 부분 매칭 경로 질의의 비율이 증가하면 기존의 YFilter보다 좋은 처리량을 나타낸다.

가설 설정

. XPath의 위치 경로 탐색을 우선적으로 고려하기 위해서 XPath 질의에서 predicate를 제외한 질의로 가정한다.
. 스트리밍 XML 데이타 필터링 기법에서 가정하는 질의는 지금 들어오고 있는 스트리밍 XML 문서에 대한 질의만을 가정한다. 즉, 지나간 문서는 저장되지 않기 때문에 질의 처리를 하지 않는다.
가) 우선 맨 처음 질의가 들어온 경우에는 공유할 오토마타 상태가 없기 때문에 새로운 오토마타 상태를 생성하며 새로운 오토마타 상태를 생성할 경우 이 상태들을 나타내기 위해 생성하는 상태의 순서에 따라 번호를 매긴다.
실험을 위한 스트리밍 XML 데이타로 XMark[8]에서 제공하는 온라인 옥션을 위한 DTD를 사용하였다. 여기에서 가정하는 온라인 옥션은 옥션의 사용자가 자신이 원하는 물건의 정보를 얻기 위해서 XPath 질의를 서버에 등록하고 이 옥션에서는 물건을 팔거나 산다는 정보를 스트리밍 XML 데이타 형태로 실시간으로 받아들인다. 여기에서는 옥션의 사용자가 등록한 XPath 질의를 크게 루트에서 시작하는 질의와 부분 매칭 경로 질의의 두 가지로 나눈다.

제안 방법

그러므로 질의의 뒷부분인 상태1에서 시작해서 공유될 부분을 찾는데 이때 name과 person이 공유될 수 있으므로 질의의 뒷부분에서 name과 person0] 공유된다. YFilter와 PoSFilter에서 비결정적 오토마타로 구성된 여러 개의 XPa比를 하나의 비결정적 오토마타로 구성하는데 드는 비용을 비교해본다. 여기에서 총 XPath 질의의 수를 N이라고 하고 각 XPath를 구성하는 노드의 개수를 n이라고 하며 XPath 질의들에 대해서 마지막 상태를 저장한 리스트 안의 마지막 상태 개수를 k라고 중}자.
여기에서 가정하는 온라인 옥션은 옥션의 사용자가 자신이 원하는 물건의 정보를 얻기 위해서 XPath 질의를 서버에 등록하고 이 옥션에서는 물건을 팔거나 산다는 정보를 스트리밍 XML 데이타 형태로 실시간으로 받아들인다. 여기에서는 옥션의 사용자가 등록한 XPath 질의를 크게 루트에서 시작하는 질의와 부분 매칭 경로 질의의 두 가지로 나눈다. 처리량은 초당 처리할 수 있는 엘리먼트를 나타내며 처리량이 높은 필터링 기법이 좋은 성능을 나타낸다.
본 논문은 다음과 같이 구성한다. 우선 기존의 스트리밍 XML 데이타 필터링 기법을 살펴보고, 다음에는 연구동 기와 제안하는 질의 뒷부분 공유에 기반한 상향식 비결정적 오토마타를 사용하는 PoSFilter에 대해서 살펴보며 마지막으로 제안하는 기법을 이용한 실험을 통해서 기존의 YFilter 와 비교 평가하고 결론을 맺는다.
위의 구성 방법에 대해서 예를 들어 다음의 4개의 질의가 있을 때 이 질의들에 대해서 PoSFilter를 구성하는 방법을 살펴보자.
Publish-Subscribe 시스템의 한 부분으로 스트리밍 XML 데이타 필터링 기법은 사용자가 보낸 질의에 대해서 빠르게 매치하는 데이타를 찾는 것을 목적으로 하기 때문에 어떤 질의가 들어오더라도 빠르게 처리할 수 있기를 원한다. 이때 기존의 필터링 기법으로 XFilter, YFilter, XMLTK를 간략히 소개하고 그중에 메모리를 적게 사용하면서도 좋은 처리량을 나타내고 있는 YFilter를 검토한다.
그다음에 처음으로 XML 문서의 끝 엘리먼트가 들어오게 되고 우선 스택의 탑에 있는 오토마타의 상태를 찾아본다. 이때 스택의 탑에는 오토마타의 상태1이 들어 있으며 오토마타의 상태1에 서 시작하여 name 엘리먼트로 오토마타에서 이동할 수 있는 상태를 PoSFilter에서 있는지 살펴본다. 그림 9(b)의 오토마타에서 상태 1에서 name이 들어오면 상태 2로 이동하는 것을 알 수 있다.
본 논문에서 제시한 PoSFilter는 부분매칭 경로 질의에 대해서 효과적으로 스트리밍 XML 데이타를 처리하기 위한 방법이다. 이번 장에서는 YFiltei■와 제시한 PoSFilter의 처리량에 대해서 비교해 본다.
기존의 필터링 기법 중에서 YFilter와 같은 비결정적 오토마타를 사용할 경우 부분 매칭 경로 질의가 증가할 때 처리량이 감소하는 문제가 생긴다. 이에 대한 제안으로 부분 매칭 경로 질의에 적합한 필터링 기법으로 질의 뒷부분 공유(postfix sharing에 기반한 상향식(bottom- up) 비결정적 오토마타를 사용하는 새로운 방법, 즉 PoSFilt或를 제안한다.

대상 데이터

위에서 여러 개의 XPath 질의를 질의 뒷부분 공유에 기반한 상향식 비결정적 오토마타인 PoSFiltei■로 구성하였다. PoSFilter를 실행하기 위해서 스트리밍 XML 데이타의 각 엘리먼트가 들어올 때마다 오토마타의 상태를 어떻게 이동해야 하는지 알아야 한다.

이론/모형

실험을 위한 스트리밍 XML 데이타로 XMark[8]에서 제공하는 온라인 옥션을 위한 DTD를 사용하였다. 여기에서 가정하는 온라인 옥션은 옥션의 사용자가 자신이 원하는 물건의 정보를 얻기 위해서 XPath 질의를 서버에 등록하고 이 옥션에서는 물건을 팔거나 산다는 정보를 스트리밍 XML 데이타 형태로 실시간으로 받아들인다.

성능/효과

기존의 YFilter는 질의의 앞부분을 공유하는 질의 앞부분 공유와 하향식 방식을 사용하므로 부분 매칭 경로 질의와 반대의 성격을 가지기 때문에 부분 매칭 경로 질의에 대해서 처리량이 떨어질 수밖에 없었다. 본 논문에서 제시한 PoSFilter는 이런 부 분매칭 경로 질의의 특성을 반영함으로 해서 부분 매칭 경로 질의가 증가할 경우에 YFilter는 처리량이 많이 감소하는 반면에 PoSFiltei■는 일정한 처리량을 갖고 부분 매칭 경로 질의가 20% 이상만 되어도 더 좋은 처리량을 보였다. 다만 이 방법을 사용할 경우에 전체 질의 중에 서 부분 매칭 경로 질의의 비중이 작을 경우에는 YFilter 보다 처리량이 떨어지는 결과를 나타낼 수 있기 때문에 부분 매칭 경로 질의 뿐만 아니라 루트에서 시작하는 질의가 있을 경우에도 좋은 처리량을 나타낼 수 있도록 두 가지 필터링 기법을 결합하는 연구가 필요하다.
하지만 YFilter의 경우에는 질의의 공통적인 앞부분 공유 (prefix sharing)에 기반한 하향식(top- down) 비결정적 오토마타를 사용하기 때문에 부분 매칭 경로 질의가 증가하면 처리량이 떨어지는 문제점이 존재한다 본 논문은 부분 매칭 경로 질의에서 처리량이 떨어지는 문제에 대한 새로운 필터링 기법으로 질의 뒷부분 공유(postfix sharing)에 기반한 상향식(bottom-up) 비결정적 오토마타를 사용하는 해결책을 제시한다. 제시한 해결책은 부분 매칭 경로 질의의 비율이 증가하면 기존의 YFilter보다 좋은 처리량을 나타낸다. 본 논문은 다음과 같이 구성한다.

후속연구

첫 번째 가정에서 Publish-Subscribe 시스템에서는 이미 지나간 데이타는 저장해 두지 않기 때문에 더 이상 둥록된 질의에 대해서 데이타가 매치되는지 살펴보지 않는다. 그리고 두 번째 가정에 있어서 제안하는 필터링 기법의 경우에는 우선 XPath의 위치경로의 탐색을 줄이는 방법을 연구하고 있기 때문에 predicate의 처리에 대한 연구는 추후 연구로 남겨놓는다. 세 번째 가정에서 Publish-Subscribe 시스템에서 사용자는 XML의 내용(content)을 중요시하는데 내용 중에서도 사용자가 원하는 정보는 대부분 XML의 PCDATA에 있다.
본 논문에서 제시한 PoSFilter는 이런 부 분매칭 경로 질의의 특성을 반영함으로 해서 부분 매칭 경로 질의가 증가할 경우에 YFilter는 처리량이 많이 감소하는 반면에 PoSFiltei■는 일정한 처리량을 갖고 부분 매칭 경로 질의가 20% 이상만 되어도 더 좋은 처리량을 보였다. 다만 이 방법을 사용할 경우에 전체 질의 중에 서 부분 매칭 경로 질의의 비중이 작을 경우에는 YFilter 보다 처리량이 떨어지는 결과를 나타낼 수 있기 때문에 부분 매칭 경로 질의 뿐만 아니라 루트에서 시작하는 질의가 있을 경우에도 좋은 처리량을 나타낼 수 있도록 두 가지 필터링 기법을 결합하는 연구가 필요하다. 또한 본 연구에서는 XPath의 위치경로의 탐색을 줄이는 부분만을 우선적으로 연구하고 있기 때문에 가정에서 predicate를 고려하지 않았다.

참고문헌 (13)

B. Babcock, S. Babu, M. Datar, R. MotWani, J. Widom, 'Models and Issues In Data Stream Systems,' In Proceeding of the PODS, 2002, pp.1-16
Mehmet Altinel, Michael J. Franklin, 'Efficient Filtering of XML Documents for selective Dissemination of Information,' In Proceeding of the VLDB, 2000, pp.53-64
Yanlei Diao, Michael J. Franklin, 'High-Performance XML Filtering: an overview of YFilter,' Bulletin of the IEEE, 2003, pp.1-8
Yanlei Diao, Peter Fischer, Michael J. Franklin, Raymond To, 'YFilter: Efficient and scalable Filtering of XML Documents,' In Proceeding of the ICDE, 2002
Yanlei Diao, Mehmet Altinel, Michael J. Franklin, Hao Zhang, Peter Fischer, 'Path Sharing and Predicate Evaluation for High-Performance XML Filtering,' ACM Transcations on Database Systems, 2003, pp. 467-516

상세보기
Todd J. Green, Gerome Miklau, Makoto Onizuka, and Dan Suciu, 'Processing XML Streams with Deterministic Automata,' In Proceeding of the LNCS, 2003, pp. 173-189
Todd J. Green, Gerome Miklau, Makoto Onizuka, and Dan Suciu, 'Processing XML Streams with Deterministic Automata and Stream Indexes,' In Proceeding of the TODS, 2004
Albrecht Schmidt, Florian Waas, Martin Kersten, Michael J. Carey, Ioana Manolescu, Ralph Busse, 'XMark: A Benchmark for XMl Data Management,' In Proceeding of the VLDB, 2002, pp.974-985
Tim Furche, 'Optimizing multiple queries against XML streams,' http://www.pms.ifi.lmu. de/publikationen/diplomarbeiten/Tim.Furche/mqspex.pdf
Chin-Wan Chung, Jun-Ki Min, Kyuseok Shim, 'APEX: An Adaptive Path Index for XML data,' In Proceeding of the SIGMOD, 2002, pp.121-132
S. Babu and J. Widom, 'Continuous Queries over data Streams,' In Proceeding of the SIGMOD, 2001, pp.109-120
Jianjun Chen, David J. DeWitt, Feng Tian, Yuan Wang, 'NiagaraCQ: A Scalable Continuous Query System for Internet databases,' In Proceeding of the SIGMOD, 2000, pp.379-390
P.Th. Eugster, P.Felber, R. Guerraoui, A. M. Kermarrec, 'The Many Faces of Publish/ Subscribe,' ACM Computing Serveys, 2003, pp.114-131

상세보기

저자의 다른 논문 :

표제어: 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

연합인증