Query Biased Snippet Generation in XML Search

PPT목차 Overview Problem Definition Solutions Experiments Summaries

1. Overview

본 논문의 의미 XML 검색의 Snippet에 대한 첫작업 4가지 목표의 식별 우리가 주어진 크기제한 안에서 중요한 모든 정모를 담으면서 Snippet을 생성할수있는지의 의사결정 문제가 NP-Complete라는것을 증명 중요한 정보들을 제한된 크기내에서 생성 할 수 있는 효과적인 알고리즘을 디자인 시스템을 구현하고 실험적 연구를 통해 효율성과 능력을 테스트

Abstraction XML 검색의 Snippet을 생성하는 것은 아직 연구 되지않음

Introduction 검색 엔진의 랭킹 시스템에서 검색결과의 의미상의 모호성을 정확하게 해결 하지 못해서 텍스트의 일부분을 보여주는 Snippet을 사용함 사용자는 Snippet을 이용하여 여러 검색 결과중에 가장 타당한 것을 빠르게 판단 할 수 있다.

Introduction 2 XML데이터가 웹 데이터를 나타내는 표준임에도 불구하고 XML데이터에 대한 Snippet을 생성해 내는 것에 대한 연구가 진행되지 않았다. 텍스트 검색은 구조의 부족으로 인해(컴퓨터가 읽기 어려워) 키워드의 주변을 잘라 Snippet을 제공한다. XML은 텍스트 검색에 비하여 의미있는 검색을 제공할 수 있는 기회가 많다.

Snippet Snippet 일반적으로 작은 단위의 무엇을 뜻함 컴퓨터에서 Snippet은 자주 쓰는 코드들을 주로 일컬으며 IDE등에 Snippets라고 되어 있는 윈도우를 보면 소스코드가 나옴 본 논문에서 말하는 Snippet은 검색 엔진 결과에 특정 검색 결과에 대한 요약 메시지를 뜻함.

Objective XML문서들을 검색해서 키워드와 관련있는 문서를 찾고 해당 문서에서 의미 있는 부분을 찾아 간결한 문장으로 출력하여 사용자가 많은 Snippet들을 보고 쉽고 빠르게 판단 할 수 있게 한다. 논문의 가장 핵심은 Snippet의 크기의 적절한 크기를 찾는 방법을 제시 하는 것이다. 요구사항 이유 Self-Contained 유저가 이해할수 있도록 Distinguishable 유저가 적은 노력으로 다른 것과 구별할 수 있도록. Representative 유저가 핵심을 포착 할 수 있도록 Small 유저가 여러 Snippet을 빠르게 훝어 볼 수 있도록

logic XML데이터는 구조화 되어 있기 때문에 노드의 부모/자식 관계를 통해 자식 노드들이 부모 노드와 관계가 있다는 것을 알 수 있다. 따라서 특정 노드의 자식 노드들을 요약함으로써 특정 노드의 특징을 알 수 있다. 단어(노드)의 출현 빈도가 그 단어의 중요도를 나타 낸다. 남성옷이 100개 여성옷이 10개라고 하면 남성옷을 주로 파는 가계이다. 키워드와 중요 단어를 Snippet에 추가하면 Snippet자체에 결과를 요약 포함 할 수 있다.

문제 정의

Result tree 구조 키워드와 매치되는 것들을 가짐

Self-contained Self-contained를 위해서 의미를 포함해야함 검색엔진이 하는 것처럼 키워드 근처에서 XML문서를 잘라서 출력 하면 무슨 말인지 모름 구글 Desktop의 경우 내용만 붙여서 출력해줌 자신들의 엔진을 공개 할 수 없어서 Query Result 만 보여줌. 키-값 쌍으로 노드 출현 통계치를 낸다.

distingulish 텍스트 검색에서는 문서 제목을 이용하여 구별을 했지만 이와 비슷하게 키를 이용하여 구별한다. 검색 결과의 키를 식별해 내는 것이 문제 쿼리 결과의 있는 같은 이름을 가진 노드들의 값이 distinct하다면 key로 사용가능 Texas apparel retailer로 검색하면 store이름을 키로 사용가능하겠지만 retailler로 검색하면 백여개의 store이름이 있을 수 있음

Representative summary 직관적으로 중요한 feature들은 출현빈도가 매우 높다. 1000개의 옷중에 600개의 남자옷과 40개의 아동복이 있다면 남자를 대상으로 하는 상점이라는 것을 알 수있다. 하지만 houston:6를 살펴보면 brook Brothers가 houston에 있다는 것을 생각해 봤을때 아동복 40보다 더 중요한 값인 것을 알 수 있다.

문제. Snippet의 크기가 크다면 위의 문제는 쉽게 해결 된다.

Solution

문제 해결 overview 쿼리 결과에서 의미를 분석한다. 엔티티들을 찾는다. 키와 중요한 Feature들을 찾는다. 정보들의 리스트가 찾아지면 값의 중요도에 따라서 Snippet에 들어갈 것을 선택하여 넣는다. 제한된 크기 안에서 최대한 많은 아이템을 넣어야 한다. 이는 NP-complete며 제한된 크기 안에서 효과적으로 의미 있는 snippet을 생성한다. Entity단위로 값을 축약해서 중요한 특징이 모두 나타나면서 Edge의 갯수가 가장 작은 부분 집합을 찾아 낸다.

NP-complete NP-완전 . NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP의 형태로 풀리게 된다. 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 P≠NP의 형태로 풀리게 된다. 정의 NP-완전은 다음의 조건을 만족하는 결정 문제 C의 집합이다: C가 NP에 속한다. NP에 속하는 모든 문제를 다항 시간 안에 C로 변환할 수 있다. 즉, 다항 시간 환산을 할 수 있다. 여기에서 두 번째 조건은 NP-난해의 정의이고, 즉 NP-완전은 NP-난해 중 NP인 문제들의 집합이다. 또한 위 정의에서 알 수 있듯이, NP-완전인 C를 다항시간 안에 풀 수 있다면 모든 NP-완전 문제를 다항시간 안에 풀 수 있다.

기호 정의 항목 내용 D Root, Labeled, Unordered tree Internal node 이름으로 labeled Leaf node 값으로 labeled R(Q,D) D에서 쿼리를 통해 추출된 Qurey result TREE S(R,Q) R에서 추출된 Snippet Tree IList(R,Q) 가장 중요한 정보를 담은 리스트

Self-contained Snippet 사용자는 하나 이상의 완전한 구나 절로 키워드가 매치된 곳이 보이길 원한다. 그편이 Self-contained되어 있고 읽기 쉽기 때문이다. 앞서 본 것처럼 XML은 키워드 매치된 부분을 제공한다고 Self-contained 되지 않는다. 하지만 구조가 있기 때문에 내용의 정보를 제공할 수 있다.

노드 구성 하나의 엔티티가 하나의 기초적인 의미있는 단위를 표현한다. Leverages XML데이터 들을 엔티티, 에트리뷰트, 노드커넥션의 3가지 분류로 나누는 것을 사용한다.

노드 구분 분류 조건 Entity *-node 라고 DTD에 있는경우 Attribute *-node라는게 없고 하나의 자식만을 가지고 있으며 자식노드가 값만을 가지고 있을 때 Connection Entity도 아니고 Attribute도 아닐 때 한 속성이 entity E와 관련이 있을 경우 E는 A의 엔티티의 가장 가까운 조상이다. 하나의 엔티티가 하나의 기초적인 의미있는 단위를 표현한다. Leverages XML데이터 들을 엔티티, 에트리뷰트, 노드커넥션의 3가지 분류로 나누는 것을 사용한다. 본 프로젝트에서는 XML데이터를 Tree로 만들기 위해서 노드를 구별을 위한 데이터를 준비해 놓았다.

Distinguishable Snippet 다른 검색 결과와 구별 검색된 entity들의 키는 검색 결과의 키로 고려될수 있다. 사용자의 검색 목표에 의해서 엔티티들은 두 분류로 나뉘어 진다. Entity 내용 Return Entity 쿼리가 수행될때 사용자가 보는 엔티티 Supporting Entities 쿼리 결과에서 return entity를 설명하기 위해 사용되는 entity들

Return Entity 구별방법 Heuristics하게 구현 될 수 있다. 제안 Entity, attribute의 이름의 키워드와 매치 될경우 매치가 아무것도 없을 경우 트리의 가장 높은 노드를 사용 주 속성을 찾는데 return Entity에서 가장 중복된 값이 적은 것을 선택한다.

Representative Snippets 가장 중요한 값들에 초점을 맞추어 요약을 하고 그 정보를 토대로 Summary를 제공 Feature를 Triplet으로 정의한다. 항목 표기 Entity e Attribute a Value v

Representative Snippets 중요한 특징과 출현빈도의 관계는 다음의 이유로 신뢰 할수 없다. Different features have different domain (e,a)의 도메인 크기는 (e,a,v)의 distinct values의 개수에 의해 정해진다. 표기 내용 해석 D(e,a) (e,a,v)의 distinct값 개수 값이 전체 에서 차지하는 비중 N(e,a) (e,a)의 전체 값 개수 값 하나의 중요도

Outwear 와 women비교 D(clothes, category)=11 D(clothes, fitting)=3

Dominance score 다른 타입에서의 출현빈도가 중요한 정보를 결정하기에는 부족함 Normalized frequency가 필요 Dominance score를 통해서 쿼리 결과에서 중요한 특징을 측정 예외 조건 처리 D(e,a)=1 DS(f,R)=1 중요한 값으로 처리 D(e,a)>1 DS(f,R)>1 중요한 값으로 처리

2.5 Algorithm for snippet information List Construction Entity면 Ilist에 추가 Keyword면ReturnEntity에 추가 Attr면 E(e,a)++ 값이면 N(e,a,v)++ 새 값이면 D(e,a) ++ ReturnEntity의 주 속성 Ilist에 추 DS계산 중요한 Feature를 Ilist에 추가 DS값에 따라 정렬

문제정의 최대한 많은 정보를 가지면서 크기 제한을 고려 해야한다. 크기제한 c에서 label의 집합P를 T’를 찾을수 있는가? 노드 u는 T의 원소이다. label(T)는 label(u)의 전체 집합이다. |T|는 T의 edge의 개수다 cont(T,v)는 label v가 T에 있는지 P는 label v들의 집합 v는 label(T)의 원소 크기제한 c에서 label의 집합P를 T’를 찾을수 있는가?

3. Generating small and meaningful result snippets 집합 덮개 문제 이 문제에서는 집합이 여러 개 있을 때 그 중 일부 집합을 골라내서, 골라낸 집합이 원래 전체 집합에 있던 원소를 모두 포함하도록 해야 한다. 이때 집합을 가능한 한 적게 골라내는 것이 목표이다. 이 문제는 리처드 카프가 NP-완전임을 보인 최초의 21문제 중 하나이다. 엄밀히 말하면, 전체집합 와 의 부분집합으로 이루어진 집합족 가 있을 때, 덮개란 합집합이 U가 되는 부분집합족 를 뜻한다. 집합 덮개 문제의 결정 문제판은 쌍과 정수 k가 입력될 때, k 이하인 집합 덮개가 있는지 묻는 문제이다. 최적화 문제판에서는 입력이 쌍뿐이고, 집합 수가 가장 적은 덮개를 찾는 문제가 된다.

증명 NP-complete임을 증명함으로써 동적 프로그래밍을 할 수 없음을 이야기 하고 Greedy알고리즘 제시의 타당성 제공

Algorithm for Instance Selection 주어진 문제는 NP-complete다. 주어진 한계크기 내에서 meaningful 하고 Informative한 snippet을 제공하는 Greedy알고리즘을 제시한다.

Several Chananges isolation되어 있는 노드는 큰 노드가 될수있다.(비용이 많이든다.) 깊이 우선 탐색을 이용 노드에 대한 연관 비용은 선택 과정에 따라서 동적으로 변한다. 비용이 동적으로 변하기 때문에 연산이 완전히 끝날 때까지 비용을 알 수 없다.

item의 가중치 IList의 아이템들은 다른 가중치를 가진다. 완전히 작업이 끝날때 까지는 아이템은 고려되어서는 안된다 그럼 결과를 믿을 수 없게된다. 리스트의 앞쪽에 있는 아이템이 더 높은 가중치를 가지게 된다. 아이템의 가중치는 앞의 것의 반이다. 키워드, 엔티티이름등 앞의 것은 값이 1이다.

Entity Path Based Selection 노드에서 가까운 부모노드까지의 path가 필요하다. root에서 leaf까지의 path가 해결책일수있다.하지만 이는 leaf노드끼리의 관계는 나타낼 수 없다. 따라서 entity기반의 path를 제안한다. 이는 부모entity와 leaf entity까지의Path를 갖는다. 만약 informative item이나 관련 entity가 경로 상에 있으면 Covered된것이다. F.1에서 leaf entity가 5개 이므로 패스는 5개

Benefit-cost of an Entity Path p.cost는 p를 선택했을 때 추가 edge수다 p.benefit은 covered item들의 가중치의 합계이다. 이는 init에서 초기화 된다. benefit이 크려면 바로 밑의 자식노드 수가 많아야 한다. n.ancCover는 n이 선택되었을때 커버되는 아이템을 표시한다. n이 선택되면 패스p의 n의 부모 n까지 snippet에 추가된다.

Path Selection and Benefit-cost Updates v가 cover되어 있으면 v를 넣는다. v가 cover되어 있지 않으면 v를 커버하는 p’까지를 경로로 추가하고 p’에서 p’’까지의 cost는 뺀다.

Algotithm

알고리즘 전개 요약 대상 요약 값 값 값 값 값

4.Experiments 한계 값 범위 6 에서 11까지 알고리즘 사용 알고리즘 Google DeskTop 텍스트 검색 테스트 시스템 eXtract Metric Quality, Processing time , scalability 테스트 시스템 CPU 3.6Ghz 펨티엄 4 OS XP memory 2GB HDD 160GB 한계 값 범위 6 에서 11까지 테스트 데이터 Firm 영화와 감독에 대한 정보 Retailer 앞의 예제와 같은 구조 알고리즘 사용 알고리즘 Google DeskTop 텍스트 검색 Optimal 한계 없음, Algorithm1 Greedy Algorithm 2, Algorithm1

snippet Quality 프로젝트에 참가하지 않은 공대 대학원생 10명이 참가 대부분의 쿼리에서 우리의 방식이 optimal 방식에 근접하거나 optimal알고리즘에서 하나 혹은 두 개의 아이템이 빠져 있었다. 그렇기 때문에 그 값이 optimal에 가깝게 나왔다.

보충, 재현 Precision Measurement에서는 좋은 값을 가지지만 Recall에서는 그렇지 못하다. 가끔씩 IList의 내용이 달라지기 때문에 발생한다.(Size Limit이 변한다)

Processing Time 소스가 되는 쿼리 결과 1KB~13KB Snippet size 제한 6~11 edges Greedy가 Optimal보다 더 빠를 것으로 예상 Optimal 방법은 exponential하게 증가 쿼리 크기가 작거나 size limit이 작으면 처리 시간은 둘다 작다.

Scalability

요약 키워드와 도메인별 노드 출연빈도에 따라서 도출된 중요 Feature가 중요 정보다. 중요 정보를 빠지지 않고 가장 작은 형태로 보여주기 위해서 Greedy알고리즘사용 Greedy를 사용하면 데이터가 많은 시 탈락되는 것도 있지만 빠르고 일정한 크기의 결과를 보여줄 수 있다.