Skyline queries are widely used in applications that support multi-criteria decision making and analysis. Given a set of data objects, the skyline query returns the objects that are not dominated by others. An object o is said to "dominate" another object o` if o is not worse than o` on all the dimensions and o is strictly better than o` on at least one dimension. Due to the recent growth of applications supporting multi-preference analysis and decision making, skyline computation has received considerable attention. Although skyline computation has been studied extensively for static data, there has been relatively less work on data streams. Recently, a few methods have been proposed to process a single continuous skyline query over a data stream. However, efficient techniques that can handle multiple skyline queries have not been much considered. In this dissertation, we propose a new method, called FAST, for processing multiple continuous skyline queries over a data stream. Since a data stream is often unbounded, a query over a data stream is generally specified with a sliding window. FAST is mainly for processing multiple continuous queries, where each query is associated with a sliding window. FAST uses a filtering technique that can early discard an object that will not be a member of any future skyline of continuous queries, and uses a discriminant that can efficiently determine which objects in memory are skyline objects for which queries. We present that the proposed method FAST can compute skylines of multiple continuous queries very efficiently. Through extensive experiments, we show the high performance and great scalability of the proposed method.
스카이라인 질의는 다기준 의사 결정 및 분석 기능을 지원하는 응용프로그램에서 많이 사용되는 질의 종류다. 스카이라인 질의는 데이터 객체들이 주어졌을 때, 다른 객체에 지배당하지 않는 객체들의 집합을 질의 결과로서 반환한다. 한 객체 o가 다른 객체 o`를 "지배한다"라는 것은 o가 모든 차원에 대해서 o`보다 나쁘지 않고 적어도 한 차원에 대해서는 o가 o`보다 좋을 경우를 뜻한다. 최근 여러 선호도를 기반으로 데이터를 분석하고 의사 결정에 도움을 주는 응용 프로그램들이 많아지면서 스카이라인 질의 처리가 많은 관심을 받고 있다. 최근까지 주로 이뤄진 스카이라인 질의 처리 방법들은 정적 데이터를 대상으로 하는 것들이었고, 데이터 스트림을 처리 대상으로 하는 방법들은 비교적 적었다. 근래 데이터 스트림 상에서 스카이라인 질의를 처리하는 몇 가지 방법들이 제안되긴 했지만 이들은 하나의 연속 스카이라인 질의를 처리하기 위한 방법으로서 여러 개의 스카이라인 질의를 효율적으로 처리하진 못한다. 본 논문에서는 데이터 스트림 상에서 여러 연속 스카이라인 질의들을 효율적으로 처리할 수 있는 방법인 FAST를 제안한다. 데이터 스트림 환경에서는 데이터가 끝없이 입력되기 때문에 질의에 슬라이딩 윈도우 정보를 함께 기술하는 경우가 많다. FAST는 연속 스카이라인 질의에 슬라이딩 윈도우가 함께 기술된 경우, 이들을 효율적으로 처리하는 방법이다. 여러 연속 스카이라인 질의들을 효율적으로 처리하기 위해 FAST는 어떠한 연속 질의에서도 스카이라인 결과에 속할 수 없는 객체들을 최대한 일찍 걸러내기 위한 필터링 기술과 각 질의의 스카이라인을 효율적으로 결정할 수 있는 판별식을 사용한다. 본 논문에서는 실험을 통해 FAST가 여러 연속 스카이라인 질의들을 매우 효율적으로 처리할 수 있음을 보인다.
