키워드 부합 스카이라인 처리 (On Processing Keyword-Matched Skylines)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 25권 / 3호 / 113 ~ 129페이지
· 저자명 : 최현식, 성민경, 정연돈

초록

본 논문에서는 새로운 형태의 스카이라인 질의인 키워드 부합 스카이라인 질의를 소개한다. 키워드 부합 스카이라인 질의는 텍스트 정보를 포함한 차원 튜플 집합에서 질의 키워드를 가지는 집합의 스카이라인을 구하는 문제이다. 기존 스카이라인 질의처리 기법은 텍스트 검색을 처리하지 못하기 때문에 이미 찾은 키워드 부합 튜플들로부터 다시 스카이라인을 구해야 하며 이는 많은 부하를 유발한다. 따라서 본 논문에서는 키워드 부합 스카이라인 질의를 위한 효율적인 질의처리 알고리즘을 제안한다. 제안 알고리즘은 IR2-Tree을 색인 구조로 사용하고 분기한정법을 이용해 트리를 순회한다. 따라서 순회동안 튜플의 벡터와 텍스트 정보를 둘 다 고려하여 방문할 필요가 없는 노드는 효율적으로 가지치기 한다. 제안 알고리즘의 성능평가를 위해 기저 알고리즘인 역색인 스카이라인 검색기법을 추가적으로 제안하고 키워드 부합 스카이라인 질의처리 기법과 비교평가 한다. 성능평가는 연산 시간 및 I/O비용 및 초점을 맞추어 수행되며 성능평가 결과는 제안 알고리즘이 기저 알고리즘보다 우수하다는 것을 잘 보여준다.

영어초록

In this paper, we introduce a new type of queries, keyword-matched skyline queries, that retrieve tuples which are not dominated by any other tuples and whose text description matches with the given query keywords. Since conventional skyline processing methods do not handle keyword matching, skyline query processing would be necessary on the keyword-matched tuples computed from n-tuples with textual information. However, this combination approach incurs a significant processing overhead. In this paper, we propose an efficient algorithm for keyword-matched skyline
queries. Our proposed algorithm makes use of IR2-Tree as the index structure and branch and bound search to traverse the tree. Therefore, our proposed algorithm can prune unqualified nodes during traversing the tree. We carried out extensive experiments with various parameters and data sets. The results of the experiments show our proposed algorithm is very efficient with regard to computational cost and I/O cost.

참고자료

· 없음