최근 XML 문서필터링에 기반한 출판 -구독 (publish-subscribe) 시스템이 많은 관심을 받고 있다. 전형적인 출판 구독 시스템에서, 구독자들은 XPath 언어로 명세된 프로파일로 자신들의 관심을 표현하고, 새로운 내용들은 사용자 프로파일에 대하여 매칭 여부를 판단하여 관심을 가지고 있는 사용자들에게만 배달된다. 구독자의 수와 그들의 프로파일이 증가할수록, 시스템의 확장성이 출판 구독 시스템의 중요한 성공 요소가 된다. 이 논문에서는 XPath 로 명세된 가지형 패턴과 입력 XML 문서들을 Prufer의 방법을 사용하여 시퀀스로 변환하는 FiST라 불라는 새로운 필터링 시스템을 제안한다. FiST 시스템은 가지형 패턴을 구성하는 선형 경로들에 대하여 각각 매칭을 수행하고 후처리 과정에서 그 결과들을 병합하는 방법을 이용하는 대신에 가지형 패턴 전체를 사용하여 입력 문서에 대하여 매칭을 수행한다. 또한 효율적인 필터링을 위하여 시퀀스들을 해시 기반의 동적 인덱스로 구성한다. 실험 결과를 통해 전체 매칭 접근 방법이 다양한 환경에서 낮은 필터링 비용과 좋은 확장성을 가짐을 알 수 있다.
최근 XML 문서 필터링에 기반한 출판 -구독 (publish-subscribe) 시스템이 많은 관심을 받고 있다. 전형적인 출판 구독 시스템에서, 구독자들은 XPath 언어로 명세된 프로파일로 자신들의 관심을 표현하고, 새로운 내용들은 사용자 프로파일에 대하여 매칭 여부를 판단하여 관심을 가지고 있는 사용자들에게만 배달된다. 구독자의 수와 그들의 프로파일이 증가할수록, 시스템의 확장성이 출판 구독 시스템의 중요한 성공 요소가 된다. 이 논문에서는 XPath 로 명세된 가지형 패턴과 입력 XML 문서들을 Prufer의 방법을 사용하여 시퀀스로 변환하는 FiST라 불라는 새로운 필터링 시스템을 제안한다. FiST 시스템은 가지형 패턴을 구성하는 선형 경로들에 대하여 각각 매칭을 수행하고 후처리 과정에서 그 결과들을 병합하는 방법을 이용하는 대신에 가지형 패턴 전체를 사용하여 입력 문서에 대하여 매칭을 수행한다. 또한 효율적인 필터링을 위하여 시퀀스들을 해시 기반의 동적 인덱스로 구성한다. 실험 결과를 통해 전체 매칭 접근 방법이 다양한 환경에서 낮은 필터링 비용과 좋은 확장성을 가짐을 알 수 있다.
In recent years, publish-subscribe (pub-sub) systems based on XML document filtering have received much attention. In a typical pub-sub system, subscribing users specify their interest in profiles expressed in the XPath language, and each new content is matched against the user profiles so that the ...
In recent years, publish-subscribe (pub-sub) systems based on XML document filtering have received much attention. In a typical pub-sub system, subscribing users specify their interest in profiles expressed in the XPath language, and each new content is matched against the user profiles so that the content is delivered only to the interested subscribers. As the number of subscribed users and their profiles can grow very large, the scalability of the system is critical to the success of pub-sub services. In this paper, we propose a novel scalable filtering system called FiST(Filtering by Sequencing Twigs) that transforms twig patterns expressed in XPath and XML documents into sequences using Prufer's method. As a consequence, instead of matching linear paths of twig patterns individually and merging the matches during post-processing, FiST performs holistic matching of twig patterns with incoming documents. FiST organizes the sequences into a dynamic hash based index for efficient filtering. We demonstrate that our holistic matching approach yields lower filtering cost and good scalability under various situations.
In recent years, publish-subscribe (pub-sub) systems based on XML document filtering have received much attention. In a typical pub-sub system, subscribing users specify their interest in profiles expressed in the XPath language, and each new content is matched against the user profiles so that the content is delivered only to the interested subscribers. As the number of subscribed users and their profiles can grow very large, the scalability of the system is critical to the success of pub-sub services. In this paper, we propose a novel scalable filtering system called FiST(Filtering by Sequencing Twigs) that transforms twig patterns expressed in XPath and XML documents into sequences using Prufer's method. As a consequence, instead of matching linear paths of twig patterns individually and merging the matches during post-processing, FiST performs holistic matching of twig patterns with incoming documents. FiST organizes the sequences into a dynamic hash based index for efficient filtering. We demonstrate that our holistic matching approach yields lower filtering cost and good scalability under various situations.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
이를 위해서 FiST는 XML 가지형 패턴 (사용자 프로파일)과 XML 문서들을 Priifer 시퀀스로 변환한다. 이 논문에서는 Priifer 시퀀스를 사용하여 점 진 적 서브 시퀀스 매칭을 수행하는 단계와 브랜치 검증을 통하여 잘못된 결과들을 버리는 정제 단계로 구성된 필터링 알고리즘을 제안하였다. 또한 다양한 환경에서 FiST 시스템이 최신의 연구인 YFilter 시스템보다 좋은 결과를 나타냄을 실험으로서 보였다.
이 논문에서는 XML 문서 필터링 시스템 FiST를 제 안 하였다. 이전의 연구들은 가지형 패턴을 여러 개의 선 형 경로들로 분해하여 각각의 선형 경로에 대하여 매칭을 수행하고 그 결과를 합쳐는 반면에, FiST 시스템은 입력 XML 문서에 대하여 전체 가지형 패턴 매칭을 수행할 수 있다.
일반적으로 XML 필터링 시스템에서는 사용자들이 XPath 언에U를 사용하여 사용자 프로파일을 명세한다. 이 논문에서는 가지 형 패턴 (twig pattern)으로 표현되는 사용자 프로파일을 다룬다. 가지형 패턴은 자식 (child) 과 후손 (descendant) XPath 축(axis)을 포함하는 2개 이상의 선형 경로(linear path)로 구성된다.
이 논문에서는 가지형 패턴에서의 노드들의 순서가 문서에서의 노드들의 순서와 일치하는 순서 매칭만을 다룬다.
제안 방법
YFilter와 FiST를 다양한 확장성 측면에서 필터 링 비용의 경향을 관찰하여 비교하였다. 왜냐하면 YFilter는 Java로 구현되었고 FiST는 C++로 구현되었기 때문이다.
YFilter의 XPath Generator를 사용하여 균등 분포 프로파일들을 생성하였다. 균등 분포는 엘리먼트 이름들이 균등 분포(uniform distributionX 가지는 데이타셋 을 의미한다.
다음으로 가지형 패턴에서 브랜치의 수를 '다양하게 변화 시켜 가면서 FiST와 YFilter의 확장성을 비교하였다. 그림 9는 이 실험에 대한 결과를 보여준다.
Priifer 시퀀스 레이블 E가 생성될 때, 스택에는 오직 하나의 C와 B만 존재한다. 따라서 필터링 알고리즘은 오직 하나의 서브 시퀀스 인스턴스 “E C B”에 대해서 검사를 수행한다. 그 결과 스택은 실제 매치를 표현하지 않는 서브 시퀀스에 대한 계산을 가지치기(pruning)하는 능력을 제공한다.
각각의 데이타셋에서 가지형 패턴이 가질 수 있는 브랜치의 개수를 3에서 7까지 변화시켰다. 또한 데이타 셋이 가질 수 있는 사용자 프로파일의 개수도 50, 000개부터 150, 000개까지 25,000개 단위로 변화시켰다.
가지형 패턴의 루트 노드에 도착했다는 것은 그 가지 형 패턴이 입력 XML 문서의 서브 시퀀스라는 의미이다. 매칭된 서브 시퀀스가 입력 XML 문서에 실제 가지형 패턴인지를 검사하기 위한 브랜치 노드 검증 단계 (Refinement by Branch Node Verification)을 수행한다. 각각의 프로파일 시퀀스마다, 서브 시퀀스 매칭 단계가 수행될 때 BranchlD set들이 구성된다.
YFilter는 가지형 패턴을 여러 개의 선형 경로로 분해하고 그 각각의 선형 경로에 대하여 매칭 여부를 확인한다. 매칭된 선형 경로들이 가지형 패턴 조건을 만족하는지 알기 위해서 후처리 작업을 수행한다. book[author//name]/titlej4 같은 XPath 식을 예로 들면, YFilter는 이 XPath를 2개의 선형 경로 book/title과 book/author//name으로 분해하고 하나의 NFA로 구성한다.
XML Generator[16]를 사용하여 최대 깊이가 36인 XML 문서들을 1000개 생성하였다. 생성된 문서들은 그 크기에 따라서 [1KB, 10KB), [10KB, 20KB), [20KB, 30KB]와 [30KB, 123KB)로 분류하였다. 이 논문에서는 편의상 이 데이타셋을 Ik, 10k, 20k, 30k 라 한다.
왜냐하면 YFilter는 Java로 구현되었고 FiST는 C++로 구현되었기 때문이다. 서로 다른 언어로 구현된 2개의 시스템의 공평한 비교를 위하여, YFilter와 FiST의 성능을 scaleup이라는 척도와 실행 시간(wall clock time)을 비교하였다. 실행 시간을 측정할 때, 주어진 가지형 패턴 집합과 데이타셋 에 대하여 문서마다 평균 필터링 시간을 측정하였다.
서로 다른 언어로 구현된 2개의 시스템의 공평한 비교를 위하여, YFilter와 FiST의 성능을 scaleup이라는 척도와 실행 시간(wall clock time)을 비교하였다. 실행 시간을 측정할 때, 주어진 가지형 패턴 집합과 데이타셋 에 대하여 문서마다 평균 필터링 시간을 측정하였다. 필터링 시간은 문서 파싱 시간과 필터링 알고리즘이 사용하는 시간을 포함한다.
이 절에서는 FiST와 YFittei.의 성능을 가지형 패턴의 크기, 브랜치의 크기와 문서 크기에 대하여 scaelup 과 실행 시간으로 분석하였다. FiST는 순서 가지형 패턴 매칭을 지원하고 YFilter는 무선서 가지형 패턴 매칭을 지원하지만, YFilter에 후처리 과정을 더하면 순서 매칭을 수행할 수 있다.
이 논문에서는 FiST 시스템과 YFilter 시스템을 비교하였다. 실험은 512MB의 메모리를 가지고 있고 리눅스가 설치되어 있는 Intel Pentium IV 2.
이 논문에서는, 입력 XML 문서에 대하여 가지형 패턴들의 전체 매칭(holistic matching) 여부를 수행하는 FiST(Filtering by Sequencing Twigs) 시스템을 제안한다. FiST 시스템은 가지형 패턴을 여러 개의 선형 경로들로 분해하여 처리하지 않기 때문에 전체 매칭이라고 할 수 있다.
또한 XML에서 문서에 나타나는 엘리먼트들의 순서를 지켜야 하는 응용에서 필요한 순서 가지형 패턴 매칭 문제에 대한 연구도 없었다. 이런 점 들을 해결하기 위해서 순서 가지형 패턴 매칭을 지원하면서 전체 가지형 패턴 매칭을 지원하는 필터링 시스템을 제안하게 되었다.
FiST의 매칭 알고리즘은 점진적인 서브 시퀀스 매칭 단계와 브랜치 노드 검증 단계의 두 단계로 구성된다. 첫 번째 단계에서 입력 XML 문서와 매칭하는 가지형 패턴들의 수퍼셋(supers의:)을 판별하고, 두 번째 단계에서 수퍼셋에 속한 가지형 패턴들 중에서 브랜치 노드에 대한 후처리 과정을 통해 잘못된 결과들을 추려낸다. 실험을 통하여 전체 가지형 패턴 매칭 접근 방법을 이용한 FiST 시스템이 다양한 상황 아래에서 좋은 확장성을 가지고 있음을 보였다.
XFilteH5]는 XML 필터링 문제에서 첫 번째 연구로서 선형 경로(linear path)만 존재하는 XPath 식을 유한 상태 기계(血ite state machine)로 변환하여 입력 XML 문서와의 매칭 여부를 판단하였다. 후속 연구인 YFilter[6]는 더 좋은 확장성을 위해서 XPath 식의 공유 처리 방법을 제안하였고, 사용자가 명세한 모든 XPath 식을 하나의 비결정적 오토마타(non-deterministic finite automata)로 구성하여 이용한다. YFilter는 가지형 패턴을 여러 개의 선형 경로로 분해하고 그 각각의 선형 경로에 대하여 매칭 여부를 확인한다.
대상 데이터
실험을 위하여 TreeBank DTD를 사용하여 생성한 XML 문서를 사용하였다. XML Generator[16]를 사용하여 최대 깊이가 36인 XML 문서들을 1000개 생성하였다. 생성된 문서들은 그 크기에 따라서 [1KB, 10KB), [10KB, 20KB), [20KB, 30KB]와 [30KB, 123KB)로 분류하였다.
실험을 위하여 TreeBank DTD를 사용하여 생성한 XML 문서를 사용하였다. XML Generator[16]를 사용하여 최대 깊이가 36인 XML 문서들을 1000개 생성하였다.
생성된 문서들은 그 크기에 따라서 [1KB, 10KB), [10KB, 20KB), [20KB, 30KB]와 [30KB, 123KB)로 분류하였다. 이 논문에서는 편의상 이 데이타셋을 Ik, 10k, 20k, 30k 라 한다.
성능/효과
보다 34% 빠른 처리 시간을 보였다. 가지형 패턴마다 7개의 브랜치를 가지고 있는 150, 000개의 가지형 패턴(그림 8(b))에 대하여 데이타샛 20k에 해당하는 입력 문서 들을 필터링하는 경우 FiST가 YFilter보다 43% 빠른 처리 시간을 보였다. 데이타셋 10k와 Ik에 대하여서는 FiST는 YFilt母에 필적한 만한 성능을 보여주었다.
Bruno 등은 인덱스-기반과 탐색 기반 XML multiquery 처리 [9] 를 연구하였으며, 그 각각이 장단점이 있음을 보였다. Lazy DFAU0]는 많은 수의 XPath 질의로부터 레이 지(lazy)하게 생성한 하나의 결정적 오토마 타(deterministic finite automata) 가 적은 수의 상태를 가지면서 효과적으로 XML 필터링에 사용될 수 있음을 보였다. 최근에는 관계 데이타베이스 시스템에 기반한 XML 기반의 출판-구독 시스템을 제안한 연구도 있었다[11丄
따라서 scaleup 측정값이 양 수(또는 음수)라는 것은 테스트 케이스가 증가함에 따라서 필터링 시간도 증가(또는 감소)함을 의미한다. 다양한 환경에서 실험을 통하여 FiST가 YFilter보다 좋은 확장성(필터링 시간이 더 늦게 증가함)을 가지는 것을 확인하였다.
이 논문에서는 Priifer 시퀀스를 사용하여 점 진 적 서브 시퀀스 매칭을 수행하는 단계와 브랜치 검증을 통하여 잘못된 결과들을 버리는 정제 단계로 구성된 필터링 알고리즘을 제안하였다. 또한 다양한 환경에서 FiST 시스템이 최신의 연구인 YFilter 시스템보다 좋은 결과를 나타냄을 실험으로서 보였다.
위에서 언급한 대로 YFilter의 필터링 비용은 증가하고 경향을 보이고 FiST의 필터링 비용은 감소하는 경향을 보이는 것을 관찰할 수 있다. 또한 문서의 크기가 증가함에 따라 필터링 비용도 증가하는 것을 알 수 있다.
첫 번째 단계에서 입력 XML 문서와 매칭하는 가지형 패턴들의 수퍼셋(supers의:)을 판별하고, 두 번째 단계에서 수퍼셋에 속한 가지형 패턴들 중에서 브랜치 노드에 대한 후처리 과정을 통해 잘못된 결과들을 추려낸다. 실험을 통하여 전체 가지형 패턴 매칭 접근 방법을 이용한 FiST 시스템이 다양한 상황 아래에서 좋은 확장성을 가지고 있음을 보였다.
문서의 크기가 증가함에 따라 YFilter와 FiST의 차이가 더 벌어짐을 알 수 있다. 이 결과들은 문서 크기가 증가함에 따라서 FiST가 YFilter■보다 더 좋은 확장성을 가짐을 보여준다. 그래프에서 3, 5, 7개의 브랜치를 가질 때의 FiST의 성능 경향이 서로 겹친다는 것은 브랜치의 수가 증가하는 것에도 불구하고 경향은 비슷하다는 것을 나타낸다.
프로파일 시퀀스의 루트 노드를 만날 때마다, 알고리즘 2나 알고리즘 4에서 프로시저 BranchNodeVerificatiori을 호출한다. 후보 가지형 패턴에서 각각의 브랜치 노드마다, BranchlD set들의 교집합을 계산하고, 그 결과가 공 집 합이 아니라는 것은 가지형 패턴의 브랜치 노드 XML 문서에서 실제 연결이 되었다는 것을 의미한다. 만약 가지형 패턴에 존재하는 모든 브랜치 노드들이 모두 연결되었다면, 이 가지형 패턴은 최종 결과가 된다.
참고문헌 (16)
Anders Berglund, Scott Boag, Don Chamberlin, Mary F. Fernandez, Michael Kay, Jonathan Robie and Jrme Simon, XML Path Language (XPath) 2.0 W3C Working Draft 16. Technical Report WD-xpath-20-20020816, World Wide Web Consortium, August 2002
Karim Muller, 'Semi-Automatic Construction of a Question Treebank,' In Proceedings of the 4th International Conference on Language Resources and Evaluation, Lisbon, Portugal, 2004
H. Prufer, 'Neuer Beweis eines Satzes tiber Permutationen,' Archiv fur Mathematik und Physik, 27: 142-144, 1998
Praveen R. Rao and Bongki Moon, 'PRIX: Indexing and Querying XML Using Prufer Sequences,' In Proceedings of the 20th IEEE International Conference on Data Engineering, pp. 288-299, Boston, MA, March 2004
Mehmet Altinel and Michael J. Franklin, 'Efficient Filtering of XML Documents for Selective Dissemination of Information,' In Proceeding of the 26th VLDB Conference, pp. 53-64, Cairo, Egypt, September 2000
Yanlei Diao, Mehmet Altinel, Michael J. Franklin, Hao Zhang and Peter Fischer, 'Path sharing and predicate evaluation for high-performance XML filtering,' ACM Trans. Database Systems, Vol. 28, No.4, pp. 467-516, 2003
Chee Yong Chan, Pascal Felber, Minos N. Garofalakis and Raieev Rastogi, 'Efficient Filtering of XML Documents with XPath Expressions,' In Proceedings of the 18th IEEE International Conference on Data Engineering, pp. 235-244, San Jose, CA, February 2002
Ashish Kumar Gupta and Dan Suciu, 'Stream processing of XPath queries with predicates,' In Proceeding of the 2003 ACM-SIGMOD conference, pp. 419-430, San Diego, CA, June 2003
T. Green, A. Gupta, G. Miklau, M. Onizuka, and D. Suciu, 'Processing XML Streams with Deterministic Automata and Stream Indexes,' ACM Trans. on Database Systems, Vol. 29 No.4, pp. 752-788, December 2004
Nicolas Bruno, Luis Gravano, Nick Koudas and Divesh Srivastava, 'Navigation- vs. Index-Based XML Multi-Query Processing,' In Proceedings of the 19th IEEE International Conference on Data Engineering, pp. 139-150, Bangalore, India, March 2003
Feng Tian, Berthold Reinwald, Hamid Pirahesh, Tobias Mayr and jussi Myllymaki, 'Implementing a Scalable XML Publish/Subscribe System Using a Relational Database System,' In Proceeding of the 2004 ACM-SIGMOD Conference, pp. 479-490, Paris, France, June 2004
Quanzhong Li and Bongki Moon, 'Indexing and Querying XML Data for Regular Path Expressions,' In Proceeding of the 27th VLDB Conference, pp. 361-370, Rome, Italy, September 2001
N. Bruno, N. Koudas, D. Srivastava, 'Holistic Twig Joins: Optimal XML Pattern Matching,' In Proceeding of the 2002 ACM-SIGMOD conference, pp. 310-321, Madison, WI, June 2002
David Megginson, Simple API for XML, http://sax.sourceforge.net/
Apache Xerces C++ Parser. http://xml.apache.org/xerces-c/
Angel Luis Diaz and Douglas Lovell, XML Generator. http://www.alphaworks.ibm.com/tech/xml-generator
※ AI-Helper는 부적절한 답변을 할 수 있습니다.