본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

GAGPC : 데이타 스트림에 대한 다중 연속 질의의 최적화 알고리즘
GAGPC : An Algorithm to Optimize Multiple Continuous Queries on Data Streams

서영균   (한국과학기술정보연구원 NTIS 사업단 통합기술개발팀CC0007658  ); 손진현   (한양대학교 컴퓨터공학과UU0001519  ); 김명호   (한국과학기술원 전산학과UU0001375  );
  • 초록

    데이타 스트림에 대한 다중 연속 질의들 사이에는 질의들의 윈도우 중첩 및 주기적 실행 간격으로 인해 재사용이 가능한 중간 결과들이 다수 생길 수 있다. 본 논문은 다중 연속 질의들을 위한 전체 실행 계획을 구성하기 위해, 효율적인 탐욕 기반의 경험적 알고리즘인 GAGPC를 제안한다. 제안한 GAGPC 알고리즘은 질의들의 전체 실행 사이클을 결정하고 관련된 실행 시점들의 최대 집합인 SRP를 찾는다. 다음, 각 SRP에서 실행될 질의들이 가장 높은 이익을 갖는 공통의 조인 부분들을 공유하도록 전체 실행 계획을 구성한다. 본 논문은 공통된 질의 부분의 존재뿐만 아니라 그것과 관련된 중첩된 윈도우 크기에 따라 통일한 연속 질의라 하더라도 최상의 질의 계획아 바뀔 수 있다는 점을 제시한다. 또한 기존 연구와는 달리, 윈도우가 부분 또는 전체적으로 중첩될 수 있으므로 중간 결과의 전체뿐만 아니라 일부도 재 사용할 것을 반영한다. 마지막으로, 본 논문은 GAGPC의 유효성을 위한 시뮬레이션 결과를 제시한다.


    In general, there can be many reusable intermediate results due to the overlapped windows and periodic execution intervals among Multiple Continuous Queries (MCQ) on data streams. In this regard, we propose an efficient greedy algorithm for a global query plan construction, called GAGPC. GAGPC first decides an execution cycle and finds the maximal Set(s) of Related execution Points (SRP). Next, GAGPC constructs a global execution plan to make MCQ share common join-fragments with the highest benefit in each SRP. The algorithm suggests that the best plan of the same continuous queries may be different according to not only the existence of common expressions, but the size of overlapped windows related to them. It also reflects to reuse not only the whole but partial intermediate results unlike previous work. Finally, we show experimental results for the validation of GAGPC.


  • 주제어

    다중 연속 질의 .   데이타 스트림 .   센서 네트워크.  

  • 참고문헌 (11)

    1. Lukasz Golab M. Tamer Ozsu, Issues in data stream management, ACM SIGMOD Record, Volume 32, Issue 2, June 2003 
    2. S. Madden, and M.J. Franklin. Fjording the Stream: An Architecture for Queries over Streaming Sensor Data, Proc. ICDE, pp. 555-566, 2002 
    3. S. Madden, M. Shah, J.M. Helierstein, and V. Raman. Continuously Adaptive Continuous Queries over Streams, Proc. ACM SIGMOD, pp. 49-60, 2002 
    4. Y.Yao and J.Gehrke. Query Processing for Sensor Networks. In Proc. 1st Biennial Conf. on Innovative Data SystRes. (CIDR) 2003. pp. 233-244 
    5. Jianju Chen, David J.DeWitt, Feng Tian, Yuan Wang, A Scalable Continuous Query System for Internet Databases, ACM SIGMOD, 2000 
    6. Babu S. and Widom J. Continuous Queries Over Data Streams, ACM SIGMOD Record archive Volume 30, Issue 3, 2001, 109-120 
    7. Moustafa A.Hammad, Michael J.Franklin, Walid G.Aref, Ahmed K.Elmagarmid, Scheduling for shared window joins over data streams, Proc. VLDB, 2003 
    8. Lukasz Golab M., Tamer Ozsu, Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams, Proc. VLDB, June 2003 
    9. TIMOS K.SELLIS, Multiple-Query Optimization, ACM Transactions on Database Systems, March, 1988 
    10. Yousuke Watanabe, Hiroyuki Kitagawa, A Multiple Continuous Query Optimization Method Based on Query Execution Pattern Analysis, DASFAA 2004 
    11. Hector Garcia-Molina, Jeffrey D.Uliman, Jennifer Widom, Database System Implementation, Prentice Hall 

 저자의 다른 논문

  • 서영균 (3)

    1. 2008 "e-Science 워크벤치를 위한 그리드 서비스 통합 기술" 정보처리학회지 = Korea information processing society review 15 (2): 69~74    
    2. 2007 "e-Science 워크벤치 기능 설계" 한국콘텐츠학회 2007년도 추계 종합학술대회 논문집 2007 (11): 259~264    
    3. 2007 "e-Science 서비스 통합 워크벤치를 위한 그리드 미들웨어 지원" 한국콘텐츠학회 2007년도 추계 종합학술대회 논문집 2007 (11): 574~577    
  • 손진현 (13)

  • 김명호 (66)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기