점진적 가지치기를 이용한 역 스카이라인 질의처리 (Reverse Skyline Query Processing using Incremental Pruning)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 데이타베이스 / 38권 / 3호 / 184 ~ 193페이지
· 저자명 : 이종혁, 한아, 박영배

초록

최근 정보에 대한 고객의 수요는 “고객 중심의 서비스”에서 “정보 중심의 서비스”로 다양화 되고 있다. “정보중심의 서비스”는 정보제공자가 질의의 주체가 되어 자신을 필요로 하는 고객을 찾아 정보를 제공한다. 이런 서비스는 전체 고객이 아닌 특정된 고객에게만 정보를 제공하는 방식으로 적은 비용으로 높은 효율성을 얻을 수 있다. “정보 중심의 서비스”는 역 스카이라인 기법으로 처리한다. 역 스카이라인 기존 연구에는 RSSA(Reverse Skyline using Skyline Approximations)기법과 ERSL(Efficient Reverse Skyline)기법이 있다. 그러나 RSSA기법은 전처리 단계에 걸리는 시간이 길 뿐만 아니라 고차원 데이터 처리에 비효율적이다. ERSL기법은 RSSA기법에 비해 성능이 우수하지만 실행 시간이 대상 객체 수 변화에 유연하지 못하다.
본 논문에서 제안하는 RSIP(Reverse Skyline query processing using Incremental Pruning)기법은 BBS(Branch and Bound Skyline) 기법을 기반으로 한 새로운 기법이다. RSIP기법은 역 스카이라인 후보객체수를 최대한 줄여 불필요한 질의 횟수를 감소하였다. 그리고 최종 역 스카이라인 판별 기준인 윈도우 질의 시간을 단축하기 위하여 피 비교 객체수를 대폭 줄였다. RSIP기법은 모든 조건에서 기존 기법들보다 향상된 성능을 나타낸다. 제안하는 기법이 기존 연구보다 효율적이라는 것을 실험 결과를 통해 보여준다.

영어초록

Recently, customer demand is changing from "Service of customer perspective" to "Service of information perspective". "Services of information perspective" is meaning that information-providers play a leading role of the query to seek limited prospect who would need the information and provide it. This kind of services can achieve low-cost and high efficiency through providing the information only to specific customer who would need it instead of all customers. This service is processed by reverse skyline method. Regarding reverse skyline method we can raise two previous research-RSSA(Reverse Skyline using Skyline Approximations) and ERSL(Efficient Reverse Skyline). However RSSA need long pre-processing time and it is inefficient in high dimension environment. As for the ERSL, it's performance better than the former, but the process time is unstable when the number of objects change.In this paper, we propose a new method - RSIP (Reverse Skyline query processing using Incremental Pruning) that is based on BBS (Branch and Bound Skyline). First, the RSIP minimized the number of the query by pruning reverse skyline candidate. Second, the RSIP significantly reduced the number of target objects in order to minimize the window query that identify the reverse skyline. The RSIP have improved the performance compare to the existing method in any conditions. Experimental results show that the performance of the proposed method is better than those of the existing ones.

참고자료

· 없음