[논문]스타이너트리 기반의 효과적인 모바일 웹 오브젝트 네비게이션

이우기; 송종수; 이정훈

[국내논문] 스타이너트리 기반의 효과적인 모바일 웹 오브젝트 네비게이션
An Effective Mobile Web Object Navigation Based on the Steiner Tree Approach 원문보기

經營科學 = Korean management science review, v.28 no.1, 2011년, pp.1 - 10

이우기 (인하대학교 산업공학과) , 송종수 (인하대학교 산업공학과) , 이정훈 (인하대학교 산업공학과)

Abstract ▼ AI-Helper

One of the fundamental roles of web object navigation is to support what the user wants precisely and efficiently from the enormous web database to the web browser. As long as the web search results are a set of individual lists, it is all right to display each and every web result for the web browser to display a web object one by one. However, in case the search results are a collection of multiple interrelated web objects, then there is a need to represent for a new mechanism for linked web objects at a time. We define a unit of web objects derived from a Steiner tree where the web objects include a set of specific keywords calculated by the weight from which the solutions are extracted. Even if a web object does not include all the keywords, then the related hypertext linked web objects are derived and displayed onto the mobile web browser with meta data in one shot. In this paper, it is applied for the mobile browser that the web contents can dynamically be displayed with Steiner trees until each renewal of the navigation request may be issued. In this paper, a new synchronized mobile browsing method is developed so that the navigating time can drastically be reduced and the web navigating efficiency can be dramatically enhanced without sacrificing memory consumption.

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 연구에서는 글로벌가중치와 로컬가중치의 곱을 사용하여 가중치로 사용하였지만, 가중치방식의 선정과 그 결합방식이 본 연구에 제약요인이 되지는 않는다. 그러므로 웹을 기본적으로 유향그래프로 인식하고, 이러한 웹 그래프에서 특정 키워드를 포함하는 노드와 아크들의 부분집합인 스타이너 트리들을 구조적 네비게이션 트리(structured navigation tree)라고 부르고, 이를 모바일 환경에 적용하는 것이 본 연구의 목표이다.
본 방법은 [16, 17]에 기반을 둔 엔진에 의거하여 모바일 시스템으로 새로이 구현하였으며, 주어진 그래프에서 모든 아크의 중요도 및 루트 노드 r을 입력으로 하여 다음 알고리즘은 중요도 합을 최대로 하는 네비게이션 트리구조를 생성하는 것이다. 참고로 기존의 연구에서 웹 그래프 구조에 대한 다양한 전처리과정 및 데이터베이스에 로딩하는 과정을 채용한 것임을 밝히는 바이다.
본 연구에서는 웹사이트를 구조화하기 위해, 아크중요도의 합을 최대화하는 계층적인 구조를 만들어 내는 것이 목표가 된다. 이러한 문제는 스타이너 트리 문제라고 할 수 있다.
본 연구에서는 새로운 웹 네비게이션 접근법을 구현한 것으로서 동적인 스타이너 트리 및 그 시스템에 대한 구현한 결과를 제시하였고, 특히 모바일 환경에 적용한 것을 보여주었다. 이러한 웹 네비게이션 시스템은 기존의 검색엔진들과는 전혀 다른 새로운 접근법이다.
물론 이는 장차 모바일 디바이스의 기능 및 프로토콜이 이를 포함하도록 개선되어야 할 것이다. 또한 본 연구에서 그래프 인덱스를 결합할 경우, 상업적인 검색엔진 및 모바일 네비게이션 엔진이 가능하며 이를 위한 연구가 진행중이다.

가설 설정

이러한 페이지랭크의 성공에 기인하여 여러 가지 성능향상 및 보완을 시도하는 다양한 가중치 계산 기법들이 개발되고 있다[7, 12]. 한편 HITS는 웹 오브젝트들을 중요 오브젝트를 권위있는 노드(Authority node)로 분류하는 가정에서 출발하여, 다른 오브젝트에 연결기능이 강화된 노드를 허브노드(Hub node)로 정의하면, 이 경우 중요한 허브노드는 권위있는 노드에 많이 연결되고, 역으로 권위있는 노드는 중요한 허브노드에 연결되는 경향이 강하다는 가정 하에 개발되었다. 이 개념은 정작 처음 의도했던 정보검색 및 네비게이션 시스템 개발로는 이어지지 못하고, 대신에 사회망(Social Network)이나 논문참조방식(Citation reference), 특허정보 응용 시스템(Patent information) 등의 분야에서 본원적인 알고리즘이 되어 주목받고 있다[14, 20].
Top-k 질의 문제는 각각 n개의 데이터를 가진 m개의 리스트가 있다고 가정한다. 그리고 각 리스트에 속한 데이터는 지역 값을 갖는다.

제안 방법

그리고 데이터베이스와 정보 네비게이션 측면을 모두 고려한 평가기준을 가지고 Top-k의 네비게이션 결과에 대한 정확도 등을 평가할 수 있다. 우선 이를 위해 예제로 그래프 방식의 산출물을 제시하고 이를 통해 본 문제를 설명하기로 한다. 본 예제는 논문 데이터베이스로 DBLP를 용용한 내용의 일부[10]로서, 4개 테이블(Authors, Paper Reference, Author-Paper, Papers) 및 그 메타정보가 제시되어 있다.
본 연구에서는 유향 그래프 스타이너 문제를 이용하여 웹을 거대한 그래프로 인식하고 그 중에서 키워드가 있는 부분적인 트리 혹인 그래프를 찾는 방법을 이용하여 최대 중요도 트리생성 문제로 치환할 수 있으며, 이는 기본적으로 최소비용트리 문제로 다음과 같은 트리생성 알고리즘으로 생성할 수 있다. 아크 가중치는 [19]에서와 같이 임의로 부여하거나, 트리의 높이[13], 노드 간 키워드 합과 거리계수의 곱[10] 등의 방법으로 부여할 수 있다.
본 연구에서는 [10]의 계수를 사용했다. 본 방법은 [16, 17]에 기반을 둔 엔진에 의거하여 모바일 시스템으로 새로이 구현하였으며, 주어진 그래프에서 모든 아크의 중요도 및 루트 노드 r을 입력으로 하여 다음 알고리즘은 중요도 합을 최대로 하는 네비게이션 트리구조를 생성하는 것이다. 참고로 기존의 연구에서 웹 그래프 구조에 대한 다양한 전처리과정 및 데이터베이스에 로딩하는 과정을 채용한 것임을 밝히는 바이다.
여기서는 다양한 시스템으로 구현하였는데, 우선 데스크 탑 및 서버방식의 시스템이며 다음으로 이를 구체화한 모바일 방식이 그것이다. 모바일에서도 다양한 데이터 조합에 대해 제대로 된 결과를 얻는지 확인하기위해 조합한 데이터에 대해 실험하였고, 또한 실제 데이터에 대해서도 시스템을 구현하였다.
다음으로 웹 그래프에서 Top-k 네비게이션트리를 찾아내는 것으로 그 절차는 다음과 같다. 대상이 되는 웹 사이트를 선정하는 방법은 우선 하나의 네비게이션엔진에서 키워드를 입력하여 얻어진 결과를 가지고 네비게이션트리로 구현하는 것이다. 본 연구에서 구현한 시스템의 수행절차는 다음과 같다.
노드 및 아크 집합을 확정하고 난 다음 아크의 가중치를 구하게 된다. 여기서는 글로벌 가중치로서 PageRank, 로컬 가중치로서 tf-idf를 구하고 이들 양자의 곱으로 아크 가중치를 정의하며, 이에 따라 가중치를 계산하였다.
상기 방식에 따라 얻어지는 자료를 대상으로 본 연구에서는 앞서 설명한 방식에 기반을 두어 트리를 유도하였다. 이때 다양한 네비게이션 요구기준을 적용하여 필요한 트리를 구한다.
우선 데스크 탑 및 서버 방식에 대하여, 앞서 언급한 절차를 따라 특정 도메인에 대한 웹 오브젝트 정보들을 수집하여 그래프 형태의 구조를 트리 형태로 변환하고 웹 브라우저에 구현한 결과를 다음 예에서 확인할 수 있다.
다음으로, 네비게이션 절차에서 중요한 점은 우선 시작단계에서 네비게이션 대상을 결정한 다음, 루트노드 선정하되, 사용자가 임의로 결정할 수 있으므로 동적인 특성을 가진다. 다음으로 루트노드로부터 도달 가능한 URL 집합 즉, 네비게이션 대상 도메인에 따라 해당 URL 웹 사이트의 노드와 아크가 분석하고, 최종적으로 절차에 따라 네비게이션 요구기준을 바꿀 수 있는 네비게이션 트리를 메타정보로서 구현한 것이다. 실험을 통해 보여준 것은 웹 오브젝트들의 연결 노드를 통합하여 모바일 브라우저에 제시해준다.

대상 데이터

우선 이를 위해 예제로 그래프 방식의 산출물을 제시하고 이를 통해 본 문제를 설명하기로 한다. 본 예제는 논문 데이터베이스로 DBLP를 용용한 내용의 일부[10]로서, 4개 테이블(Authors, Paper Reference, Author-Paper, Papers) 및 그 메타정보가 제시되어 있다. 여기서 저자와 논문을 노드로 인식할 경우 인접행렬 및 그 2단계 행렬은 <그림 2>와 같이 표현될 수 있다.

성능/효과

양자 간의 성능의 차이에서 결정적인 부분은 웹 오브젝트의 양의 차이에서 오는 장점도 조금 있지만, 오히려 전체 오브젝트를 재요청하는 Classic 방식에 비해 Graph based 방식은 변경된 부분만 요청하는 브라우징 기술적 차이에 따른 장점이 메모리의 부담이 없이도 가능하다는 것이다. 결과적으로 네비게이션된 웹 오브젝트들을 어떻게 사용자에게 표현할 것인지 문제도 중요한데, 본 연구에서처럼 스타이너트리라는 새로운 네비게이션 접근법으로 여러 오브젝트로 구성된 네비게이션 결과도 매우 효과적으로 지원하므로, 따라서 이는 새로운 네비게이션 패러다임이 될 수 있다.
실험을 통해 보여준 것은 웹 오브젝트들의 연결 노드를 통합하여 모바일 브라우저에 제시해준다. 결과적으로 새로운 모바일 브라우저를 구현하여 각 웹 오브젝트를 동기적으로 보여주는 새로운 네비게이션 방식을 구현하여, 시간을 획기적으로 단축하는 효율성 증가를 입증하였다. 또한 그래프를 네비게이션하여도 메모리를 희생시키지 않고, 동시에 효과적으로 지원할 수 있는 현실성 있는 기법이라 것을 보였다.
결과적으로 새로운 모바일 브라우저를 구현하여 각 웹 오브젝트를 동기적으로 보여주는 새로운 네비게이션 방식을 구현하여, 시간을 획기적으로 단축하는 효율성 증가를 입증하였다. 또한 그래프를 네비게이션하여도 메모리를 희생시키지 않고, 동시에 효과적으로 지원할 수 있는 현실성 있는 기법이라 것을 보였다.

후속연구

그러므로 로컬 가중치는 노드 기반의 노드 가중치 평가방식이라 명명될 수 있으며, 글로벌 가중치는 링크기반 노드 가중치라 부를 수 있다. 본 연구에서는 글로벌가중치와 로컬가중치의 곱을 사용하여 가중치로 사용하였지만, 가중치방식의 선정과 그 결합방식이 본 연구에 제약요인이 되지는 않는다. 그러므로 웹을 기본적으로 유향그래프로 인식하고, 이러한 웹 그래프에서 특정 키워드를 포함하는 노드와 아크들의 부분집합인 스타이너 트리들을 구조적 네비게이션 트리(structured navigation tree)라고 부르고, 이를 모바일 환경에 적용하는 것이 본 연구의 목표이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	웹 그래프라고도 불리는 정보화의 역설을 해결하는 정보 접근법은?	물론 Small World 효과도 있지만, 이렇게 정보의 원천 자체가 초대형화 되어가고 웹 오브젝트의 종류가 다양해질수록, 사용자는 점점 더 원하는 정확한 내용을 확인하기가 어려워지는 정보화의 역설이 성립하므로, 이를 해결하기 위한 다종의 해법이 제안되고 있다. 현재 가장 중요한 접근법의 하나로서 웹 정보에 대한 구조화 즉, 그래프 접근법이 있는데, 이는 최근 웹 데이터베이스 및 정보처리 연구 집단에서 핵심적인 방법의 하나로 최근 2～3년 사이에 집중적으로 연구되고 있다. 이는 웹을 그래프 관점으로 나타내는 것으로 이를 웹 그래프(Web as a graph)라고도 부른다[7, 21].
	웹은 양적으로 어떠한 규모인가?	웹의 폭발적 성장은 질적 양적으로 괄목할 만하다. 양적으로 웹은 현재 조 단위를 넘어선지 오래되었다. 질적으로는 HTML, XML 등의 단순한 웹 페이지 뿐만 아니라, 그림이나 동영상, 전자화된 매뉴얼이나 데이터베이스부터 트위터나 이메일, 뉴스, 동영상, 웹 서비스 및 앱(App) 스토어 등을 포괄하므로, 이를 포괄적으로 표현하는 용어로서 본 연구에서는 웹 오브젝트(Web Object)라고 부르기로 한다.
	웹 오브젝트가 포괄하는 대상은 어떤 것들이 있는가?	양적으로 웹은 현재 조 단위를 넘어선지 오래되었다. 질적으로는 HTML, XML 등의 단순한 웹 페이지 뿐만 아니라, 그림이나 동영상, 전자화된 매뉴얼이나 데이터베이스부터 트위터나 이메일, 뉴스, 동영상, 웹 서비스 및 앱(App) 스토어 등을 포괄하므로, 이를 포괄적으로 표현하는 용어로서 본 연구에서는 웹 오브젝트(Web Object)라고 부르기로 한다. 물론 Small World 효과도 있지만, 이렇게 정보의 원천 자체가 초대형화 되어가고 웹 오브젝트의 종류가 다양해질수록, 사용자는 점점 더 원하는 정확한 내용을 확인하기가 어려워지는 정보화의 역설이 성립하므로, 이를 해결하기 위한 다종의 해법이 제안되고 있다.

참고문헌 (24)

Akbarinia, R., E. Pacitti, and P. Valduriez, "Best Position Algorithms for Top-k Queries," VLDB, (2007), pp.495-506.
Amer-Yahia, S., A. Doan, J.M. Kleinberg, N. Koudas, and M. Franklin, "Crowds, clouds, and algorithms : exploring the human side of 'big data' applications," SIGMOD, (2010), pp.1259-1260.
Byrka, J., F. Grandoni, T. Rothvob, and L. Sanita, "An improved LP-based approximation for steiner tree," STOC, (2010), pp.583-592.
Consoli, S., K. Darby-Dowman, N. Mladenovic, and J.A. Moreno-Perez, "Variable neighbourhood search for the minimum labelling Steiner tree problem," Annals OR, Vol. 172, No.1(2009), pp.71-96.
Fagin, R., A. Lotem, and M. Naor, "Optimal aggregation algorithms for middleware," PODS, (2001), pp.102-113.
Fagin, R., "Combining Fuzzy Information from Multiple Systems," PODS, (1996), pp.216-226.
Glover, E.J., D.M. Pennock, S. Lawrence, and R. Krovetz, "Inferring Hierarchical Descriptions," Proc. CIKM, (2002), pp.507-514.
Gouveia, L. and J. Telhada, "The multiweighted Steiner tree problem : A reformulation by intersection," Computers and OR, Vol.35, No.11(2008), pp.3599-3611.
Gouveia, L., P. Moura, and A. Sousa, "Prize collecting Steiner trees with node degree dependent costs," Computers and OR, Vol.38, No.1(2011), pp.234-245.
Guoliang, L., O.C. Beng, F. Jianhua, W. Jianyong, and Z. Lizhu, "EASE : an effective 3- in-1 keyword search method for unstructured, semi-structured and structured data," In Proc. SIGMOD, (2008), pp.903-914.
Gupta, A. and A. Kumar, "A constant-factor approximation for stochastic Steiner forest. STOC," (2009), pp.659-668.
Hammami, M.Y. Chahir, and L. Chen, "Web-Guard : A Web Filtering Engine Combining Textual, Structural, and Visual Content-Based Analysis," IEEE TKDE, Vol.18, No.2 (2006), pp.272-284.
Kasneci, G., M. Ramanath, M. Sozio, F. M. Suchanek, and G. Weikum, "STAR : Steiner-Tree Approximation in Relationship Graphs," In Proc. ICDE, (2009), pp.868-879.
Kleinberg, J.M., A. Slivkins, and T. Wexler, "Triangulation and embedding using small sets of beacons," J. ACM, Vol.56, No.6(2009).
Kleinberg, J.M. and S. Lawrence, "The Structure of the Web," Science, Vol.294 (2001), p.1849.

상세보기
Lee, W., K.S. Carson, J. Leung, J.H. Lee, "Mobile Web Navigation in Digital Ecosystems Using Rooted Directed Trees," IEEE TIE, 2011(in-print).
Lee, W.J., J.-H. Lee, Y. Kim, C.K-S. Leung, "AnchorWoman : top-k structured mobile web search engine," CIKM, (2009), pp.2089-2090.
Lee, W., J. Song, J. Baek, and J. Lee., "Steiner Tree based Effective Mobile Web Search," Proc. KORMS Conference, 2010.
Li, W., K. Candan, Q. Vu, and D. Agrawal, "Retrieving and Organizing Web Pages by Information Unit," In Proc. WWW, (2001), pp.230-244.
Maserrat, H. and J. Pei, "Neighbor query friendly compression of social networks," KDD, (2010), pp.533-542.
Pandurangan, G., P. Raghavan, and E. Upfal, "Using PageRank to Characterize web Structure," Proc. COCOON, (2002), pp.330-339.
Pinto, L.L. and G. Laporte, "An efficient algorithm for the Steiner Tree Problem with revenue, bottleneck and hop objective functions," European Journal of Operational Research, Vol.207, No.1(2010), pp.45-49.

상세보기
Rothlauf, F., "On Optimal Solutions for the Optimal Communication Spanning Tree Problem," Operations Research, Vol.57, No.2 (2009), pp.413-425.

상세보기
Whittaker, G., R. Confesor Jr., S.M. Griffith, R. Fare, S. Grosskopf, J.J. Steiner, G.W. Mueller-Warrant, and G.M. Banowetz "A hybrid genetic algorithm for multiobjective problems with activity analysis-based local search," European Journal of Operational Research, Vol.193, No.1(2009), pp.195-203.

상세보기

저자의 다른 논문 :

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증