QUISIS: Interval Skip List를 활용한 질의 색인 기법
QUISIS: A Query Index Method Using Interval Skip List
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
인터넷과 인트라넷의 확산에 따라, 스트림 데이터 처리(stream data processing)와 같은 새로운 분야가 등장하게 되었다. 스트림 데이터는 실시간적이고 연속적으로 생성된다. 스트림 데이터 환경에서는 복수 개의 질의들이 미리 등록되고 후에 도착되는 데이터는 등록된 질의들에 의하여 평가된다. 따라서 질의 성능을 향상시키기 위하여, 스트림 데이터 처리 시스템을 위한 다양한 연속성 질의 색인 방법들이 제안되었다. 본 논문에서는 스트림 데이터를 위한 질의 색인에 대하여 다룬다. 일반적으로, 스트림 질의는 간격 조건식을 포함하고 있다. 따라서, 간격 조건식을 이용하여, 질의들을 색인화할 수 있다. 이 논문에서, 탐색 속도를 향상시키기 위하여, Interval Skip List를 수정한 효율적인 질의 색인 방법, QUISIS를 제안한다. QUISIS는 최근 데이터 값이 근 미래에 도착하는 값과 비슷하다는 지역성을 활용한다. 성능 평가를 통하여, 본 논문에서 제안하는 기법의 효율성을 보인다.
Abstract
Due to the proliferation of the Internet and intranet, new application domains such as stream data processing have emerged. Stream data is real-timely and continuously generated. In stream data environments, a lot of queries are registered, and then, the arrived data item is evaluated by registered queries. Thus, to accelerate the query performance, diverse continuous query index schemes have been proposed for stream data processing systems. In this paper, we focus on the query index technique for stream data. In general, a stream query contains the range condition. Thus, by using range conditions, the queries can be indexed. In this paper, we propose an efficient query index scheme, called QUISIS, using a modified Interval Skip Lists to accelerate search time. QUISIS utilizes a locality where a value which will arrive in near future is similar to the current value. Through the experimental study, we show the efficiency of our proposed method.
참고문헌 (17)
- D. Terry, "Continuously Queries over Append-Only Databases", In Proceedings of ACM SIGMOD Conference (1992)
- D. Carney, "Monitoring streams-a new class of data management applications", In Proceedings of VLDB Conference, pp.215~226 (2002)
- "Niagara Project"[URL]
- C. Cortes, "Hancock: a language for extracting signatures from data streams", Proceedings in ACM SIGKDD Conference, pp.9~17 (2000)
- A. Arasu, "Stream: The stanford stream data manager", IEEE Data Engineering Bulletin, 26(1), pp.19~26 (2003)
- J. M. Hellerstein, "Adaptive query processing: Technology in evolution", IEEE Data Engineering Bulletin, 23(2), pp.7~18 (2000)
- S. Choi, "Accelerating Database Processing at e-Commerce Sites", In Proceedings of International Conference on Electronic e-Commerce and Web Technologies. (2004)
- H. M. Deitel, "An Introduction to Operating Systems" (1990), Addison-Wesley
- R. Avnur, "Eddies: Continuously adaptive query processing", In Proceedings of ACM SIGMOD Conference, pp.261~272 (2000)
- S. Babu, "Adaptive ordering of pipelined stream filters", In Proceedings of ACM SIGMOD Conference, pp.407~418 (2004)
- S. Madden, "Continuously adaptive continuous queries over streams", In Proceedings of ACM SIGMOD Conference (2002)
- S. Chandrasekaran, "Telegraphcq: Continuous dataflow processing", In Proceedings of ACM SIGMOD Conference, pp.668~ (2003)
- A. Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching", In Proceedings of ACM SIGMOD Conference (1984)
- T. Brinkhoff, "The R*-tree: An Efficient and Robust Access Method for Points and Rectangles", In Proceedings of ACM SIGMOD Conference (1990)
- H. S. Lim, "Continuous query processing in data streams using duality of data and queries", In Proceedings of ACM SIGMOD Conference, pp.313~324 (2006)
- J. Lee, "BMQ-Index: Shared and Incremental Processing of Border Monitoring Queries over Data Streams", In Proceedings of International Conference on Mobile Data Management (MDM’06), (2006)
- E.N. Hanson, "Selection Predicate Indexing for Active Databases Using Interval Skip Lists", Information Systems, 21 (1996)