Radeon HD 4000 series specifications surfaces

article: http://www.nordichardware.com/news,7356.html

The ATI Radeon HD 4000 series is slatedfor late Q2. Information about the high-end RV770 has been leaking ontothe web, from here and there, but the exact specifications has remainedin the shadows. German hardware site Hartware.net has gotten theirhands on what seems to be pretty authentic information. As far as wecan tell, it looks believable and matches the rumors going around.We're still far away from the launch and the figures are subject tochange. We also have some information on our own to share with you.

Ifyou're into extreme single-core GPUs you may want to stop reading now.ATI's future is value-oriented and if you're longing for that 1 billiontransistor megachip, you can stop doing it right now. ATI isn't intothat. We should have told you this sooner. ATI is focusing on bang forthe buck and if you want more performance you should get a second card,or get the card with two cores.

Considering the flexibility and scaling that CrossFireX offers,we're not exactly saddened by AMD's decision to steer ATI towardfocusing more on the price/performance ratio than on raw performance.It is harder to write drivers for a multi-GPU, but when you make surethat you have a good foundation, such as CrossFireX, it might be worththe risk.

The information published elsewheresuggests that ATI will use GDDR5 to a great extent, which surprise us alittle. On the other hand, ATI may know something about GDDR5 that wedon't (we would be surprised otherwise). RV770 has GDDR5 support, butwhether ATI will actually use it remains to be seen. GDDR4 with most ofthe high-end cards is a highly likely scenario. The frequenciessuggested here are actually lower than what good GDDR4 chips arecapable of.

Radeon HD
Frequency (MHz)

RV770 will break 1TFLOPS, while the R700, with two RV770, should becapable of twice that, more than 2TFLOPS. This is higher than what hehad expected, but then again the core frequencies are also higher thanexpected. All cores are made by TSMC and their 55nm process. We'restill trying to hunt down more reliable information on the design ofthe "core".

On top of the information Hartware.net published we've completed thetables with some additional information, among others the target pricepoints. AMD/ATI's goal is to keep the prices at a point where they arefirst of all affordable, but also a thorn in the side of NVIDIA. Theprices in the table are the not the final MSRP, but the price ATI aimsto stick below. Meaning that the retail prices should end up lower thanwhat the tables shows.

When AMD/ATI, unveiled the Radeon HD 3000 series they had added anifty feature called PowerPlay. PowerPlay dynamically controls thepower consumption and will severely reduce the power consumption whenidle, but also reduce the peak consumption somewhat. When we look atthe figures they don't quite add up, but as stated above, these figuresare all most likely going to change before the launch. The idle powerconsumptions of all cards are extremely low and even the dual-coreRadeon HD 4870X2 will consume less than 25W when idle.

Radeon HD

The number of TMUs have finally been increased, actually doubled, to32 with RV770, while RV740 sports 24 TMUs, and the low-end RV710 has 8TMUs. Don't bother getting upset with the 256-bit memory bus because itwill not become any kind of bottleneck. The only time it might be evenclose to that is when you're pouring liquid nitrogen into the containerand have the GPU running at +50% of stock frequency, which will happenthough.


To end this long and speculative post, we would like to say that ifnot all, most of the variables here are subject to change and should beconsidered with a "tiny" pinch of salt. We're still 4 month away fromthe launch.

by Hans | 2008/04/06 03:49 | Interest | 트랙백(86431) | 핑백(1) | 덧글(1)

정말 간만에 튕기는 Guitar Hero II

퇴근하고 집에 와서 간만에 Guitar Hero II CD를 넣고 튕겨봤다..
역시나 오랜만에 해서 그런지 잘 안된다..
그래도 명작답게 재미있네.... 빨리 Guitar Hero III 가 발매되어야 할텐데...

by Hans | 2007/09/11 03:42 | Interest | 트랙백 | 덧글(0)

구글 검색 엔진의 해부학 - The anatomy of large scale search engine

구글 개발자들이 쓴 'The anatomy of large scale search engine' 논문 번역


이 논문을 통해 우리는 구글(Google)이라는, 하이퍼텍스트를 통해 나타나는 구조적 특징을 대폭 사용한 대형 검색 엔진의프로토타입을 제시하고자 한다. 구글은 웹을 능률적으로 긁어와서 인덱싱(색인화)한 다음 (crawling &indexing) 기존의 시스템보다 훨씬 더 만족스런 검색 결과를 나타낼 수 있도록 디자인되었다. 최소 2천 4백만 페이지로이뤄진 하이퍼링크 데이타베이스와 풀 텍스트로 이뤄진 구글의 프로토 타입은 http://google.stanford.edu의주소로 이용해 볼 수 있다.

google search engin 구글검색엔진을 제작한다는 것은 상당히 도전적인 과제다. 검색 엔진은 수억에서 수십억 개의 웹 페이지와 수억-수십억 개의 용어들을 함께인덱싱한다. 또한 검색엔진은 매일 수천 만 개의 질의어에 응답한다. 웹 기반의 대형 검색엔진의 중요성이 분명함에도 불구하고 이에대해 학문적으로 연구된 바는 거의 없다. 게다가 웹의 분화와 테크널러지의 발달이 매우 빠르기 때문에 오늘 웹 검색엔진을 만드는것은 3년 전에 만드는 것과 전혀 다르다. 이 논문에서 우리는 우리가 만든 대형 웹 검색엔진에 대해서 자세하게 묘사하고자한다.(현 시점까지 이렇게 자세한 내용이 공개된 것은 최초라 할 수 있다.)

전통적인 검색 기술을 거대한 크기의 데이타에 맞게 확장하는 것에서 초래되는 문제들은 별개로 하더라도, 보다 나은 검색결과를 나타낼 수 있도록 하이퍼텍스트에 나타나는 부가적인 정보를 이용하는 문제 같은 새로운 기술적 과제들이 있다. 이 논문에서는이와 같은 하이퍼텍스트에 존재하는 부가적인 정보를 실제 사용 가능한 대형 시스템을 구축하는 데 어떻게 활용할 수 있는가라는문제에 대한 해결책을 제시한다. 또한 우리는 웹처럼 아무나 원하는 것을 출판할 수 있는 조절되지 않는 하이퍼텍스트 문서컬렉션(uncontrolled hypertext collections)을 어떻게 효과적으로 다룰 수 있을지의 문제도 살펴본다.

1. 개괄

웹은 정보검색(IR; Information Retrieval)에 새로운 과제를 안겨줬다. 웹에 존재하는 정보들은 매우빠르게 늘어나고 있다. 그리고 웹에서 무엇인가를 찾는 것에 익숙하지 못한 새로운 사용자들의 숫자도 급속하게 늘어나고 있다.사용자들이 웹 써핑을 할 때 대개 링크 그래프(link graph)를 이용하는 경향이 크다. 사람이 직접 만든 목록 중 아주높은 품질의 목록(야후! 같은)에서 출발하거나 검색엔진을 이용한다. 사람이 직접 유지관리하는 목록은 보편적인 주제를 효과적으로커버할 수 있다는 장점이 있지만, 주관적이기 쉽고 구축/유지 비용이 매우 높고, 개선이 느리고 모든 특이한 주제를 커버할 수없다는 단점이 있다. 한편 키워드 매칭(keyword matching)을 기반으로 하는 자동화된 검색엔진(automatedsearch engine)은 대개 너무 많은 낮은 질의 맷치를 결과로 돌려주는 경우가 잦다. 게다가 어떤 광고인들은 자동화된검색엔진이 엉뚱한 결과를 나타낼 수 있는 방법을 사용해서 사람들의 주의를 끌어가려는 시도를 한다. 우리는 이와 같은 기존시스템의 여러가지 문제점들을 해결한 대형 검색엔진을 구축했다. 특히 우리 검색엔진은 훨씬 높은 수준의 검색 결과를 제공하기 위해하이퍼텍스트에 존재하는 부가적인 구조를 대폭 사용했다. 우리는 우리 시스템 이름을 '구글'(Google)로 택했는데, 이것은 10100 또는 'googol'을 뜻하는 일반적인 철자이기 때문이기도 하고 매우 큰 스케일의 검색엔진을 구축하겠다는 우리의 목표와 잘 부합되기 때문이기도 했다.

1.1 웹 검색엔진의 확장: 1994 - 2000

검색엔진 기술은 웹의 성장세에 맞춰 극적으로 확장되어 왔다. 1994 년 최초의 검색엔진 중 하나인 World WideWeb Worm(WWWW)은 110,000 페이지의 웹문서 및 웹을 통해 접근가능한 문서를 색인화(indexing;인덱싱)한다.1997년 현재, 최고 수준의 검색엔진들은 2백만 문서에서(WebCrawler) 1억 개의 문서까지 인덱싱했다고 주장하고 있다.2000년 말쯤이면, 약 10억 개 이상의 문서에 대한 포괄적인 인덱스(comprehensive index)가 만들어질 것으로예상되고 있다. 검색엔진이 다루는 질의어(queries)의 숫자 역시 믿기지 않을 정도로 성장해 왔다. 1994년 3,4월경,WWWW은 매일 평균 1500여 개의 질의어를 받았었다. 그런데 1997년 11월, 알타비스타(AltaVista)의 주장에따르면 매일 약 2천만 개의 질의어를 처리하고 있다 한다. 웹 사용자가 더욱 늘어나게 됨에따라, 2000년 말쯤에 이르면 탑검색엔진들은 매일 평균 약 수억 개의 질의어를 다루게 될 것이다. 우리 시스템은 검색엔진 기술을 위와 같은 놀라운 크기의 숫자를다룰 수 있게 확장하는 데 있어 발생하는 많은 문제점들을 그 질적인 측면에서나 확장성 면에서나 잘 해결해 보겠다는 목표를 갖고있다.

1.2 구글(Google): 웹과 함께 확장한다

오늘날의 웹 정도를 포괄하는 검색엔진을 만드는 일도 많은 도전적 과제를 해결해야 한다. 웹 문서들을 모으고 최신 상태로유지하기 위해서는 빠른 속도의 크롤링 기술(crawling technology)이 필요하다. 그리고 색인(index)을 저장하고때로는 문서 자체를 저장하기 위해 저장 공간은 반드시 효율적으로 사용되어야만 한다. 인덱싱 시스템은 수백 기가바이트의 데이타를효율적으로 처리할 수 있어야만 하고 질의어 역시 초당 수백, 수천 개 이상의 빠른 속도로 처리되어야 한다.

이런 과제들은 웹이 계속 성장해 감에 따라 갈수록 어려워지고 있다. 하드웨어 성능과 비용이 극적으로 좋아지고 있는 것은이런 문제점들을 어느 정도는 상쇄한다. 그러나 거기에도 주목할 만한 예외가 있다. 디스크 검색 속도(disk seektime)라든지 운영체계의 강력함(robustness)은 별로 개선되지 못하고 있다. 구글을 디자인함에 있어, 우리는 웹의 성장속도와 테크널러지의 변천 속도 모두를 고려해 왔다. 구글은 극단적으로 큰 데이타 셋(data sets)을 위해서도 충분히 확장될수 있도록 디자인되어 있다. 인덱스를 저장하기 위한 저장 공간을 효율적으로 사용할 뿐만 아니라 구글의 데이타구조는 빠른 억세스,효율적인 억세스에 적합하도록 최적화되어 있다. (4.2 섹션에서 자세히 다룬다) 그리고 HTML이나 텍스트를 저장하고 인덱싱하는비용은 그 양이 늘어남에 비해 상대적으로 감소할 것으로 예상된다. 이것은 구글과 같은 중앙집중식 시스템의 확장성에 좋은 영향을미치게 된다.

1.3 디자인 목표

1.3.1 검색 품질의 개선

우리의 주된 목표는 웹 검색 엔진의 질적인 면을 개선하는 것이었다. 1994년 당시만 해도 완전한 검색엔진 인덱스를갖춤으로써 무엇이든 쉽게 찾을 수 있을 것이라 믿는 사람들이 있었다. "Best of the Web 1994 --Navigators"에는, "최상의 네비게이션 서비스는 웹상의 거의 모든 것을 쉽게 찾을 수 있도록 해줘야 한다 (일단 모든데이타가 입력되고 나면)" 라고 실려있었던 것이다. 하지만 1997년의 웹은 그 전과 전혀 다른 양상이다. 최근 검색 엔진을사용해 본 사람이라면 누구나 인덱스 자체의 완전성이 검색 결과의 품질을 결정하는 유일한 요소가 아님을 얘기할 것이다. "쓰레기검색 결과"(Junk results)가 원하는 결과를 압도해버리는 것이 드물지 않다. 사실, 1997년 11월 현재, 검색창에검색엔진 자신의 이름을 입력했을 때 탑 10 결과 내에 자신의 이름이 들어있는 검색 엔진은 상위 4 개의 상업적 검색 엔진에불과하다.

이것의 주된 원인은, 문서의 수는 기하급수적으로 증가해온 반면 사용자가 문서를 찾는 능력은 그렇지 못했기 때문이다.사람들은 여전히 검색 결과 중 수십 개 정도만을 보려한다. 그러므로 문서 모음(이하 컬렉션, collection)의 크기가증가함에 따라 대단히 높은 프리시젼(precision)역자주을 가진 툴이 필요해진다. (precision은 검색 결과 중 실제 검색어와 관계되는 결과의 비율)

사실 우리는, "관계되는"이라는 단어의 의미를 아주 높은 수준으로 규정하려 했는데 그 이유는 '약간' 관계되는 문서들만해도 수만 개 이상이기 때문이다. 극도로 높은 수준의 프리시젼은 심지어 리콜(recall)을 희생해서라도 달성해야 할 만큼중요하다. (recall은 관계되는 문서 중 얼마나 많은 것을 찾아낼 수 있느냐를 의미)

최근, 하이퍼텍스트적인 정보를 보다 더 많이 이용함으로써 검색이나 다른 부문의 기능을 개선할 수 있을 것이라는 낙관적인전망이 많이 나오고 있다. 특히 링크 구조와 링크 텍스트는 "관계성 판단"(relevance judgement)과 질적인필터링에 있어서 많은 정보를 제공할 수 있다. 구글은 그 링크 구조와 앵커 텍스트(anchor text)를 사용하고 있다.

역자주 : recall과precision은 정보검색(IR)에서 중요한 성능 측정 기준으로 사용하는 지표입니다. precision은 검색 결과 중에실제로 '관계되는' 문서가 몇 개인가를 의미합니다. 즉, 결과의 '정확도'입니다. recall은 검색어와 관계되는 문서 전체중에 몇 개를 찾아내느냐입니다. precision은 보통 상위 몇 위까지 중 관계되는 문서가 몇 개인가 형태로 평가합니다.

예를 들어 어떤 컬렉션의 총 문서 갯수는 100 개이고 이 중에 '사과'와 관계되는 문서가 30 개 있다고합시다. 질의어 '사과'에 대해서 어떤 검색 시스템이 총 15 개의 결과를 되돌려 주었고 상위 10 위까지의 결과 중 실제로사과와 관계되는 문서가 8 개였다면 precision과 recall은 이렇게 계산합니다.

상위 10 위에서의 precision = 8 / 10 = 0.8
recall = 15/30 = 0.5

논문은, 웹 검색의 경우 리콜이 극도로 높고 (대개 검색결과가 수만 페이지 이상이기 때문에) 사용자들은 상위 몇 개만을 보려하기때문에 프리시젼이 극도로 높아야만 한다는 것을 얘기하고 있습니다. 소규모 도서관 정보 검색 시스템이라면 얘기가 전혀 다릅니다.관계되는 모든 서적을 다 찾아내는 것이 더 중요할 수 있습니다. 그 때는 리콜이 더 중요합니다. 그렇다면 리콜과 프리시젼은 어떤관계일까요? 반비례일까요, 비례일까요? 아니면?
1.3.2 검색 엔진에 관한 학술 연구

웹은 자체 성장속도 뿐만 아니라 상업화의 속도도 엄청나게 빠르다. 1993 년에는 .com 도메인이 전체의 1.5%였다.그러던 것이 1997 년에는 전체의 60%를 차지하고 있다. 검색엔진 역시 학술적 영역에서 벗어나 상업화되어 왔다. 현재까지기업체에서 개발한 검색엔진의 대부분은 기술적인 디테일을 거의 발표하지 않고 있다. 검색 엔진 기술은 장막에 가려진 채 광고지향적인 것으로 남아있는 실정이다. 우리는 구글을 통해서 검색 엔진 개발과 이해를 보다 학술적인 영역으로 끌어와 보고자 했다.

또 하나 중요한 디자인 목표는 상당한 숫자의 사람들이 실제로 사용할 수 있는 시스템을 구축해 보자는 것이었다. 구축한시스템이 실제로 사용되어야 한다는 점이 중요한데 그 이유는, 오늘날의 웹 시스템에서 만들어질 수 있는 대용량의 유시지데이타(usage data)를 활용함으로써 아주 흥미로운 연구가 이뤄질 수 있다고 생각하기 때문이다. 예를 들면 매일매일이뤄지는 수억 건의 검색 행위와 관계되는 데이타가 그렇다. 하지만 이런 데이타는 확보하기가 매우 어렵다. 상업적 가치가 높다고여겨져서 공개되지 않기 때문이다.

마지막 디자인 목표는 대용량 웹 데이타상에서 많은 새로운 연구 활동이 이뤄질 수 있도록 그 기반을 구축해 보겠다는것이었다. 새로운 연구에 사용되게 만들기 위해 구글은 크롤링한 실제 문서 그 자체를 압축된 형태로 저장한다. 구글을 디자인함에있어 우리의 주된 목표 중 하나는 다른 연구자들이 웹의 상당한 부분을 처리해서 흥미로운 결과를 내놓은 것에 쉽게 참여할 수 있는길을 터주자는 것이었다. 구글 시스템을 가동한 지 얼마되지 않았음에도 구글에 의해 생성된 데이타베이스를 이용한 여러 편의 연구가이미 발표되었고 또한 많은 연구가 현재 진행중이다. 또 하나의 목표는 구글을 일종의 우주 실험실과 같은 환경으로 만들어서 다른연구자들이나 학생들이 대형 웹 데이타상에서 여러가지 흥미로운 실험을 제안하고 실행해 볼 수 있게 하겠다는 것이다.

구글 검색 엔진은 검색 결과가 높은 프리시젼을 갖도록 두 가지 중요한 특징을 부여했다.
첫째, 구글은 개별 웹 페이지 품질을 순위 매기기 위해 웹의 링크 구조를 이용한다. 이 랭킹은 페이지랭크(PageRank)라 일컬어지며 다른 논문에서 자세히 설명했다. 둘째, 구글은 검색 결과를 개선하기 위해서 링크를 사용한다.

2.1 페이지랭크(PageRank) : 웹에 순서를 매긴다

웹의 인용(링크) 그래프는 기존의 웹 검색 엔진들이 거의 사용하지 않고 있는 중요한 자원 중 하나이다. 우리는 총5억1800만 개의 하이퍼링크를 담고 있는 링크 지도를 만들었는데 이것은 전체 웹의 상당 부분을 포괄하는 것이다. 이 지도를이용하면 어떤 웹 페이지의 "페이지랭크" 값을 빠르게 계산할 수 있다. 페이지랭크는 일반적인 사용자가 생각하는 특정 페이지의중요성과 잘 상응하는 인용 중요성의 객관적인 측정치다. 인간 판단과의 이런 연관성 때문에 페이지랭크는 웹 키워드 검색 결과를순위 매기는 데 있어 최상의 수단이 된다. 대부분의 일반적 검색어에 있어서, 문서 제목과 검색어가 일치하는지만을 평가하는 단순한텍스트 매칭 검색 엔진을 이용한 결과에서도, 그 결과를 페이지랭크로 순위를 매기는 경우 상당한 성능을 보여준다. 물론 구글시스템과 같이 완전한 텍스트 검색을 수행하는 시스템에서도 페이지랭크는 매우 큰 도움을 준다.

2.1.1 페이지랭크 계산 방법

학술 문헌 인용 방식을 웹에도 적용해보려는 시도가 있어 왔는데 대개 어떤 페이지의 인용 횟수(백링크; back link)를 세는 방식으로 이뤄진다. 어떤 페이지가 얼마나 많이 인용(참조)되고 있는가를 셈으로써 그 페이지의 중요성이나 품질을 추정해볼수 있는 것이다. 페이지랭크는 이 아이디어를 더욱 확장해서 단순히 모든 링크를 세는 것에서 한 발 더 나아가 그 링크가 어떤페이지로부터 왔는지를 차별화했고, 링크를 하고 있는 페이지로부터 외부로 나가는 총 링크 갯수로노멀라이징(normalizing)했다. 페이지랭크는 다음과 같이 정의된다:

페이지 A를 가리키는 다른 페이지들이 T1, T2, ... Tn 까지 있다고 하자. ( = T1,...Tn은 페이지 A를 인용)
퍼래미터 d는 damping factor로 0에서 1 사이의 값을 갖는다. 우리는 보통 d = 0.85로 했다. d값에 관해서는 다음 섹션에서 다룬다.
C(A)는 페이지 A에서 밖으로 나가는 링크의 갯수다. 이때 A 페이지의 페이지랭크 PR(A)는:

pagerank 페이지랭크

페이지랭크 PR(A)는 단순한 반복 알고리듬(iterative algorithm)을 이용해서 계산할 수 있으며, 그 값은웹 링크를 노멀라이징해서 행렬로 바꾸었을 때 주고유벡터(principal eigenvector)에 해당한다. 또한 2천6백만페이지의 페이지랭크는 중간 크기의 웍스테이션에서도 몇 시간 정도면 계산할 수 있다. 이에 관해서는 이 페이퍼의 범위를 벗어나는많은 세부사항이 있다.

2.1.2 직관적 정당화

페이지랭크는 사용자 행동을 모델링한 것으로 생각해볼 수 있다.
"랜덤 써퍼"가 한 명 있다고 하자. 이 사람은무작위로 선택한 어떤 웹 페이지에서 출발해서 백버튼을 누르지 않고 계속 링크를 따라 클릭해 나간다. 그러다가 지루해지면 또 다른무작위로 선택된 페이지에서 써핑을 시작할 것이다. 랜덤 써퍼가 특정 페이지를 방문할 확률이 바로 그 페이지의 페이지랭크다.그리고 d damping factor는 랜덤 써퍼가 어떤 페이지를 읽다가 지루해져서 또 다른 랜덤 페이지를 찾게될 확률을뜻한다. 페이지랭크의 변형된 형태 중에서 중요한 것 중 하나가 댐핑 팩터(damping factor) d를 특정 페이지 하나또는 일군의 페이지에만 선택적으로 적용하는 것이다. 이렇게 함으로써 사용자화(personalization)가 가능하며 랭킹을올리기 위해 교묘하게 조작하는 것을 사실상 불가능하게 만들 수 있다. 그 외에도 많은 페이지랭크의 확장이 있다.

또 하나의 직관적인 정당화는, 페이지랭크가 올라가기 위해서는 많은 페이지가 어떤 한 페이지를 가리켜야 하거나 특정 페이지를가리키는 페이지 그 자체의 페이지랭크 값이 커야 한다는 점이다. 직관적으로도 웹상의 여러 곳에서 인용되고 있는 페이지는 살펴볼만한 가치가 있다는 의미이므로 쉽게 이해가 된다. 또한 Yahoo!와 같은 중요한 곳에서 인용이 되고 있다면 링크가 오직 한개뿐일지라도 그 페이지는 살펴볼 가치가 있을 것이다. 어떤 페이지가 품질이 낮거나 링크가 깨져있다면, Yahoo!같은 곳에서 그페이지로 링크를 걸어놓지 않을 것이기 때문이다. 페이지랭크는 이 두 가지 경우 모두를 잘 다루고 있으며 양자 사이의 모든 부분도웹의 링크 구조를 통해 가중치를 재귀적으로 전파시켜 나감으로써 잘 다루고 있다.

2.2 앵커 텍스트(Anchor Text)

우리 검색 엔진은 링크의 텍스트 그 자체를 특별하게 다룬다. 대부분의 검색 엔진들은 링크의 텍스트를 링크를 담고 있는 그페이지와만 연관시킨다. 우리는 더 나아가 링크가 가리키는 페이지까지 링크의 텍스트와 연관시킨다. 이것은 여러가지 장점이 있다.첫째, 앵커는 종종 그 링크가 담겨있는 페이지보다 그 링크가 가리키는 페이지에 대한 보다 정확한 설명을 담고 있는 경우가 많다.둘째, 일반적인 텍스트 검색 엔진이 인덱싱할 수 없는 이미지나 프로그램, 데이타베이스로의 앵커(링크)도 존재할 수 있다.그러므로 앵커를 활용하면 실제로 크롤링되지 않은 웹 페이지들까지 찾아낼 수 있다. 물론 크롤링되지 않은 페이지들이 문제를 일으킬수 있다는 점은 주의해야 한다. 이 페이지들은 사용자에게 결과로 뿌려주기 전에 유효성을 먼저 테스트 해야한다. 심지어 실제존재하지 않는 페이지인데도 가리키는 링크가 있기 때문에 반환될 수도 있다. 하지만 이런 검색 결과를 분류하는 것이 가능하므로특별한 문제를 일으키는 경우는 거의 없다.

앵커 텍스트를 그 앵커가 가리키는 페이지로 전파시켜 나간다는 아이디어는 World Wide Web Worm 검색 엔진에서구현되었었다. 앵커 텍스트가 텍스트가 아닌 정보를 검색하는데 도움이 되었고, 검색 엔진이 다운로드한 문서보다 훨씬 더 많은부분을 커버할 수 있게 확장해주기 때문이다. 앵커 텍스트를 효율적으로 사용하려면 대용량의 데이타를 처리해야만 하기 때문에기술적으로 까다롭다. 우리는 크롤링한 2400만 페이지에서 약 2억5900만 개 이상의 앵커를 인덱싱할 수 있었다.

2.3 다른 특징들

페이지랭크 기술과 앵커 텍스트를 사용한다는 점 외에 구글은 몇 가지 다른 특징을 가진다.
첫째, 구글은 모든 힛(hit)에 관한 위치 정보를 저장하기 때문에 검색 時 근접도를 광범위하게 활용한다. 둘째, 구글은 어떤단어의 폰트 크기와 같은 시각적인 세부 요소를 추적한다. 폰트 싸이즈가 큰 단어나 볼드체로 된 단어는 그렇지 않은 단어에 비해더 높은 가중치가 부여된다. 셋째, 구글은 완전한 HTML도 저장하기 때문에 이를 이용할 수 있다.

3. 관련 연구

웹 상의 검색 연구는 역사가 얼마 되지 않는다. World Wide Web Worm (WWWW) 검색 엔진이 대표적인최초의 검색엔진이다. WWWW을 기점으로 그 뒤에 몇 개의 학술적 목적의 검색엔진이 나타났다. 웹의 성장세나 검색 엔진의중요성에 비해 현대적 웹 검색엔진에 관한 문서는 거의 없는 실정이다. Michael Mauldin(Lycos 의 ChiefScientist)씨는, "라이코스를 포함한 여러 서비스들은 자기 데이타베이스의 디테일들을 엄격하게 감추고 있다"고 밝혔다.하지만 검색엔진의 특정 기능에 관해서는 상당한 양의 연구가 진행되어 왔다. 특히 기존의 상업적 검색엔진을 이용한 결과물을후처리(post processing)한 것에 관한 부문이 두드러진다. 반면 정보검색(IR, InformationRetrieval)에 관해서는, 특히 잘 조절되고 있는 컬렉션을 대상으로한 것은, 이미 많은 연구가 나와있다. 다음 두섹션에서, 우리는 이들 연구를 웹에서 보다 더 잘 동작하도록 확장하는 방법을 살펴볼 것이다.

3.1 정보 검색

정보 검색 시스템에 관한 연구는 오래 전부터 있어 왔으며 잘 정리되어 있다. 하지만 대부분의 정보 검색 시스템에 관한연구는 소규모의 잘 통제되고 있는 동질적인 컬렉션(a small well controlled homogenouscollection)을 대상으로 하고 있다. 예를 들면 과학 논문이나 서로 연관되는 뉴스 기사들을 대상으로 하고 있다. 실제정보 검색의 가장 대표적인 벤치마크로 사용되는 TREC(Text Retrieval Conference)의 경우 아주 작은 크기의잘 통제되어 있는 컬렉션을 이용한다. "초대형" 벤치마크라고 해 봐야 겨우 20기가 바이트에 지나지 않는다. 반면 우리가모아놓은 2천400만 개의 웹 페이지는 147기가 바이트에 이른다. TREC에서는 좋은 결과를 보이더라도 웹에서는 좋은 결과를나타내지 못하는 경우가 많다. 예를 들어, 표준적인 벡터 공간 모형(Vector Space Model)은 질의어와 문서를 단어빈도에 의거한 벡터로 파악해서 질의어에 가장 근접한 문서를 되돌려주는 방식이다. 하지만 웹에서 벡터 공간 모형을 사용하면 질의어외에 몇 단어 없는 매우 짧은 문서가 반환되는 경우가 많다. 메이져 검색 엔진에 "Bill Clinton"이라는 질의어를 넣어보면 "Bill Clinton Sucks"라는 문장과 사진이 담겨 있는 페이지만 결과로 되돌려 준다. 어떤 사람은 질의어 외에부가적으로 단어를 추가해서 사용자가 찾는 단어를 더 정확하게 표현할 수 있는것 아니냐고 주장한다. 우리는 그런 주장에 전혀동의하지 않는다. 사용자가 "Bill Clinton"이라는 질의어를 입력했다면 당연히 합리적으로 받아들일 수 있는 결과를 얻어야한다. 웹에는 그 주제에 관한 엄청나게 많은 고품질의 페이지가 있기 때문이다. 이런 예들을 보면서 우리는 표준적인 정보 검색연구를 웹에 효과적으로 적용하기 위해서는 더욱 많은 확장이 필요하다고 생각하게 되었다.

3.2 웹과 잘 통제되는 컬렉션 사이의 차이점들

웹은 전혀 통제되지 않는 이질적인 문서들로 이뤄진 거대한 컬렉션이다. 웹상의 문서는 문서 내부적으로도 극단적으로 다양할뿐만 아니라 문서 외부적인 메타 정보 역시 매우 다양하다. 예를 들어, 여러 웹 문서들은 내부적으로 사용 언어 측면에서 다르고(인간의 언어 측면에서도 그렇고 컴퓨터 언어 측면에서도 그렇다), 어휘에 있어서도 다르고 (이메일 주소, 링크, 우편 번호,전화 번호, 제품 번호 등), 포맷이나 유형 면에서도 다르며 (텍스트, HTML, PDF, 이미지, 싸운드) 심지어 어떤문서들은 컴퓨터에 의해 생성되고 있는 것이다. (로그 파일, DB 로부터 출력된 내용)

메타 정보의 경우도 마찬가지다.
우리는 외부 메타 정보를 어떤 문서 내부에는 담겨 있지 않은 정보로, 그 문서 자체에 관해 유추할 수 있는 정보로 정의한다.외부 메타 정보에는 그 페이지의 명성, 업데잇 빈도, 품질, 인기도 또는 유시지(usage), 그리고 인용 등이 있다. 외부메타 정보는 그 잠재적 소스가 다양할 뿐만 아니라, 측정값 역시 큰 차이가 난다. 야후! 홈페이지와 수십 년된 낡은 기사를비교해 보자. 야후!는 매일 수백만 페이지뷰 이상을 받지만, 후자의 경우는 십 년만에 한 번 찾아지거나 할 것이다. 이 경우사용도는 현격하게 차이가 난다. 그리고 검색 엔진은 이 둘을 전혀 다른 방식으로 다뤄야 한다는 것 역시 당연하다.

잘 통제되는 컬렉션과 웹이 크게 다른 또 다른 점은, 웹에서는 누가 무엇을 올려놓을지를 조절할 방법이 사실상 없다는점이다. 무엇이든 퍼블리슁할 수 있다는 웹의 유연성이 트래픽을 안내하는 검색 엔진의 엄청난 영향력과 맞물리면, 검색 엔진을교묘하게 조절해서 이득을 취해가려는 회사들이 심각한 문제가 된다. 이런 점들은 전통적인 폐쇄적 정보검색 시스템에서는 전혀 문제가되지 않았었다.

웹 검색 엔진의 경우 메타 데이타(메타 택 (Meta Tag))를 사용하려는 시도가 거의 실패로 돌아갔다는 점 또한 특기할 만하다. 실패한 이유는 검색 엔진을 악용하기 위해 메타 정보가남용되었기 때문이다. 심지어 메타 태그를 이용, 검색 엔진을 조작하는 쪽으로 특화한 회사들도 상당수 존재할 정도이다.

문서출처: 이명헌 경영스쿨 http://www.emh.co.kr/xhtml/google_search_engine.html
이 문서를 게시하거나 프린트하려면 위 문서출처를 반드시 포함해야 합니다.(참고: 저작권정책)

by Hans | 2007/08/13 20:44 | Search Engine | 트랙백(95) | 덧글(0)

링크 구조 기반 검색 앨거리듬, HITS

클라인버그 교수의 "Authoritative sources in a hyperlinked environment" 논문 요약


논문의 도입부에서는 질의어와 'authoratative sources'의 관계, 그리고 링크 구조의 분석 방법등을다룹니다. 우선 "broad search topic"이란 문구가 나오는데요, 검색어는 주제의 범위가 넓은 것과 특화된 것이있습니다. 예를 들어 "학교"라는 검색어는 대단히 광범위한 검색어로 많은 결과가 리턴됩니다. 반면 "정보검색"이라는 질의어는매우 특별한 것으로 결과로 반환되는 것이 훨씬 적습니다. "Hubs and authorites"라는 링크 구조 모델을 다루는 본논문에서 소개하는 알고리듬은 전자와 같은 광범위한 검색 키워드에 대한 검색결과를 어떻게 링크 구조를 이용해서 정제할 수 있을까를모색해 본 것입니다. 범위가 넓은 주제에 대한 검색 결과중 어떤 것이 가장 '권위 있는' 페이지인지를 찾아내는 방법을 생각해보는 것입니다.

우리가 어떤 검색을 했을 때 결과로 반환되는 페이지가 '좋은 결과다'라고 판단하는 것은 주관적입니다. 검색 결과의 품질에대한 평가는 지극히 주관적이기 때문에 그 결과가 검색어와 관련 있다, 없다를 판단하는 데 있어서 인간의 판단이 배제된 어떤객관적인 기준, 나아가서 알고리듬으로 구현할 수 있을 만큼 공식화된 방법이 없을까를 찾아낼 필요가 있습니다. 이 부분을 무시한대부분의 검색 엔진 기술들은 검색 속도나 저장 효율 등에만 얽매이고 있는데 이것은 중요한 문제를 젖혀둔 채 부수적인 것에 매달린것일 수 있습니다. 무엇이 관련된 페이지이고, 그 관련된 페이지 중에 어떤 것이 '좋은' 페이지인가를 판단하는 객관적인 방법을찾는 것이 훨씬 중요합니다. 이 논문은 그 목적을 달성하기 위한 하나의 방법을 제공하고 있습니다.

"authority"란 무엇인가?

검색어는 특화된 것이 있고 광범위한 것이 있다고 했습니다. 예를 들어, "펄에서 url을 인코딩하는 데 사용되는 모듈은?"같은 질의어는 대단히 특화된 것입니다. 반면, "자바 프로그래밍 언어에 관한 정보"는 광범위합니다. 전자와 같은 질의어는 희소성문제가 생깁니다. 해당 정보를 담고 있는 페이지 수가 매우 적은 데서 비롯되는 문제입니다. 역으로 후자의 경우는 과다성 문제가생깁니다. 관련되는 페이지가 너무 많아서 문제가 됩니다. 과다성 문제가 생기는 경우 인간이 처리할 수 있는 수준을 넘어선 양의정보가 제공되기 때문에 그 결과들 중 어떤 것이 가장 '권위 있는', '확실한' 페이지들인지 찾아낼 방법이 있어야 합니다.

그렇다면 '권위 있다'는 것은 어떤 의미일까요? 예를 들어 이런 것입니다. 검색어로 "harvard"를 입력하면 수만,수십만 페이지가 결과로 뜰 것입니다. 그 중 가장 '권위 있는' 페이지는 당연히 www.harvard.edu입니다. 그런데 이런'권위 있는' 페이지를 찾아낼 문서 자체의 내부적 특성이 없습니다.

예컨데 단어 빈도수를 생각해 봅시다. www.harvard.edu는 "harvard"라는 단어가 가장 많이 등장하는페이지가 아닙니다. 단어 빈도수만을 기준으로 '권위'를 추정하는 경우 전혀 엉뚱한 페이지가 가장 관련성이 높은 페이지가 될 수있습니다.

그렇다면 url은 어떨까요? 위 경우는 ".edu"가 들어간 것 중 "harvard"가 들어간 페이지를 찾으면 해당은되겠습니다만 모든 검색어에 일반적으로 적용할 수 있는 방법은 아닙니다. url 자체가 '권위'를 판단하는데 어떤 힌트를 주기힘듭니다. 문서의 길이는 어떨까요? 그것도 별로 효과가 없습니다. 검색 결과 중 긴 페이지를 찾는다고 반드시 그 페이지가 권위가있느냐면 그렇지 않을 가능성이 훨씬 높습니다.

문서 내부적인 정보만으로는 어떤 페이지가 권위있는 곳이다 아니다를 판단하기가 대단히 곤란합니다.

하나 더 예를 들어 봅시다. "검색 엔진"이라는 질의어에 대한 결과 중 권위 있는 곳은 네이버라든지 구글이라든지, 엠파스,다음 등입니다. 그런데 이들 페이지가 질의어 "검색 엔진"과 어떤 관련성을 갖나요? "검색 엔진"이라는 단어가 가장 많이등장하는 것도 아니고 특별히 문서 자체에서 이들의 권위를 유추해 낼 방법이 없습니다.

그렇다면 검색창에 "검색 엔진"이라고 입력을 했을 때 어떻게 하면 위와 같은 '권위 있는' 곳을 찾아낼 수 있을까요?오쏘리티를 찾겠다는 것은 바로 이 문제를 해결할 방법을 찾는 것입니다. 검색어에 대한 검색 결과 중 어떤 것이 가장 '좋은'페이지인가를 판단해 보겠다는 것이고 그런 '좋은' 페이지들을 오쏘리티라 하는 것입니다.

하이퍼링크가 해결책

위 문제를 해결하는 중요한 수단이 하이퍼링크를 활용하는 것입니다.
하이퍼링크는 사람의 판단이 포함되어 있기 때문입니다. 우리가 어떤 페이지를 링크하는 것은 대체로 그 페이지가 '좋은' 페이지이기때문입니다. 어떤 페이지를 링크할 것인가 말 것인가의 결정에는 인간 판단이 함께 인코딩되어 있습니다. 그러므로 링크를사용함으로써 위에서 말한 오쏘리티를 찾아낼 수 있는 것입니다.

다른 곳에서 링크가 많이 되어 있는 페이지가 있다면 그 페이지는 살펴볼 가치가 있는 페이지일 가능성이 높습니다. 또 하나,링크를 활용할 때의 장점은 문서 자체 내에 그 문서의 우수성을 판단할 기준이 담겨있지 않다는 부분도 해결된다는 점입니다. 그문서가 길든 짧든, 질의어와 맷취가 많이 되든 적게 되든, 그 문서의 우수성을 판단해 볼 수 있습니다.

링크도 물론 문제는 있습니다. 예컨데 링크가 다른 목적으로 된 경우가 꽤 있습니다. 광고성 링크도 있을 수 있고, 내부 네비게이션 목적의 링크도 있습니다. 링크가 반드시 권위있는 곳이기 때문에 이뤄진 것이 아닐 수 있습니다.

HITS 알고리듬

HITS 알고리듬은 크게 2단계로 나뉩니다. 먼저 질의어와 관계있는 페이지들의 부분집합(서브 그래프(subgraph))을만드는 단계입니다. 그 다음엔, 만들어진 서브 그래프를 이용해서 헙과 오쏘리티(hubs & authorities)를계산해내는 단계입니다.

1. 서브그래프(subgraph) 만들기

먼저, 하이퍼링크로 연결된 페이지들의 컬렉션 V를 G = (V,E)라는 directed graph로 표현합니다. 이때 각각의 노드는 각 페이지에 해당하고 (p,q) ∈ E는 p에서 q로의 링크가 있다는 것을 뜻합니다. 그리고,

  • 어떤 노드 p의 out-degree: 밖으로 나가는 링크의 갯수
  • 어떤 노드 p의 in-degree : 노드 p를 가리키는 링크의 갯수
  • G[W] : V에 속하는 부분집합 W로부터 만든 그래프
  • 질의어 : σ라 합니다.

이제 광범위 검색 주제어인 질의어 σ에 대한 오쏘리티를 링크 구조만을 이용해서 어떻게 찾을 수 있는지 생각해 봅시다.질의어 σ를 담고 있는 페이지 전체 집합을 Qσ라 합시다. 알고리듬은 이 Qσ를 대상으로 하면 안 됩니다. 그 이유는 첫째,질의어를 담고 있는 페이지는 아마도 수백만 페이지 이상일 것이기 때문에 'computationally expensive'합니다.둘째, 앞에서 살펴본대로 중요한 오쏘리티는 질의어 자체를 담고 있지 않은 경우도 매우 많습니다.

우리가 원하는 집합을 Sσ라 하면, Sσ는 이런 특성을 가지면 좋을 것입니다.

  1. 상대적으로 작아야 한다.
  2. 관계되는 페이지가 많아야 한다.
  3. 대부분의 오쏘리티들을 담고 있으면 좋겠다.

알고리듬의 첫 단계인 서브 그래프를 만드는 단계는 바로 이런 특징을 갖는 Sσ를 찾아내는 것입니다. 그러면 Sσ를 어떻게 찾아낼까요?

일반적인 텍스트 기반 검색엔진에 질의어를 넣었을 때의 결과 중 상위 t개의 페이지를 루트셋(root set) Rσ라합시다. 이 Rσ는 아마도 위의 조건 중 1,2번은 만족하지만 3번은 만족하지 않을 수 있습니다. 그러므로 Rσ를 이용해서 강한오쏘리티(strong authorities)를 찾아낼 수 있다면 우리가 원하는 Sσ에 가까운 서브 그래프를 만들어 낼 수 있을것입니다.

그런데 오쏘리티는 Rσ에 있는 페이지들이 가리키는 페이지들 중에 많이 존재할 가능성이 높습니다. 관계되는 페이지들이가리키고 있는 페이지는 '권위 있는' 페이지일 가능성이 크기 때문입니다. 따라서 Rσ를 링크를 이용해서 확장하면 우리가 원하는강력한 오쏘리티가 들어있으면서, 작고, 관계성 높은 서브 그래프를 만들어 낼 수 있을 것입니다. 이것을 알고리듬으로 표현하면이렇게 됩니다.

Subgraph(σ, ε, t, d)
σ : a query string
ε : a text-based search engin
t,d : natural numbers
Let Rσ denote the top t results of ε and σ

Set Sσ := Rσ
For each page p ∈ Rσ
Let T+(p) denote the set of all pages p points to
Let T-(p) denote the set of all pages pointing to p
Add all pages T+(p) to Sσ
If |T-(p)| ≤ d then
Add all pages in T-(p) to Sσ
Add an arbituray set of d pages from T-(p) to Sσ
Return Sσ

다른 부분은 쉽게 이해가 될 것이고, T-(p)가 d보다 작거나 같을 때 이것을 Sσ에 포함시킨다는 부분이 약간 이상하게느껴질 겁니다. T-(p)중 몇 개만을 취한 까닭은 무엇일까요? 만약 Rσ에 야후!가 들어있다고 해 봅시다. 그러면 야후!를가리키는 페이지는 수백, 수천만 개 이상일 것이기 때문에 이들을 다 포함시키는 경우 Sσ가 턱없이 커집니다. 그러므로 일정한개수만 포함시키는 것입니다.

위와 같은 과정을 통해서 얻어낸 Sσ를 "σ의 base set"이라고 합시다. 이 베이쓰 셋을 구하기 위해 이 논문에서는검색 엔진으로는 알타비스타를 사용했고 t=200, d=50 으로 했다고 합니다. 이렇게 했을 때 대략 1000-5000개 정도의페이지를 담고 있는 Sσ가 만들어졌다고 합니다.

root set

이렇게 얻어진 서브그래프는 몇가지 휴리스틱스를 적용함으로써 조금 더 줄일 수가 있습니다. 예를 들어, 순수하게 네비게이션의용도로만 쓰이는 링크는 '권위'를 부여하는 기능이 없으므로 배제할 수 있습니다. 도메인 네임을 살펴 봐서 동일한 곳에서 동일한곳으로 연결되고 있는 링크는 네비게이션 목적일 가능성이 높으므로 제외합니다. 또는, 어떤 한 도메인 내의 많은 페이지가 외부의어떤 한 페이지로만 링크가 되고 있는 경우도 광고성 링크거나 특별히 트래픽을 몰아줄 계약을 체결했을 가능성이 높습니다. 이런것들을 제외하기 위해 단일 도메인에서 특정 페이지 p로의 링크가 있는 페이지의 갯수는 4개-8개로 제한합니다.

2. 헙과 오쏘리티 계산

앞 단계에서 만든 서브그래프를 이용, 이제 우리가 최종적으로 구하고자 하는 헙(hubs)과오쏘리티(authorities)를 찾아냅니다. 일단 Sσ를 그래프화 한것을 Gσ라 합시다. 이제 링크 구조를 이용해서 이Gσ속에 존재하는 헙과 오쏘리티를 찾아내는데, 제일 쉽게 생각해 볼 수 있는 것이 Gσ내의 페이지들을 in-degree 순으로순위를 매기는 것입니다. 이것은 직관적으로 좋은 방법일 것 같은 느낌이 듭니다. 일단 Gσ라는 특정 검색어와 관계성이 높은페이지들 집합 속에서 다른 페이지로부터의 링크가 많다는 것은 그 만큼 '좋은' 페이지일 가능성이 높아지기 때문입니다. 하지만실제로 그렇게 해보면 강력한 오쏘리티와 보편적으로 인기가 높은 페이지(universally popular pages) 사이의긴장이라는 문제가 생깁니다. 예를 들어 "java"라는 질의어의 경우 www.gamelan.com과 java.sun.com이라는결과와 함께 카리비안 휴양 관련 싸이트와 아마존 홈페이지가 함께 순위권에 듭니다. 이것은 특정 주제에 관한 오쏘리티와 함께'주제에 관계없이 링크가 많이 된'(universally popular) 것이 존재하기 때문입니다. 이 문제의 해결책은 페이지의텍스트 내용도 같이 감안해서 검색어와 매칭되는 단어가 등장하는 것을 골라낸다 정도가 될 것인데 이것도 실제로 해보면 별로 효과가없다고 합니다.

오히려 논문의 저자는 순수하게 링크 구조만을 활용해서 이 문제를 해결할 수가 있다고 하는데요. 그 출발점은 이렇습니다.

"모든 오쏘리티들은 큰 in-degree를 갖는다는 점과 함께 그 오쏘리티들을 가르키고 있는 페이지들 역시 중복된다는 공통점을 갖는다"

어떤 주제에 관한 오쏘리티들을 많이 링크하고 있는 페이지를 중심축 역할을 한다는 의미에서 헙이라고 명명합시다. 그러면 앞의기술은, "좋은 오쏘리티들은 in-degree가 높다는 점과 함께 많은 헙들로 부터 링크되어 있다는 공통점이 있다."는 얘기가됩니다. 여러 헙들로부터 링크되어 있을수록 좋은 오쏘리티가 되며, 여러 오쏘리티를 링크하고 있을수록 좋은 헙이 되는 것입니다.즉, 헙과 오쏘리티는 상호강화적인 관계(mutually reinforcing relationship)입니다.

그러므로 좋은 오쏘리티는 좋은 헙을 찾는 것을 통해서 찾아낼 수 있고, 좋은 헙은 좋은 오쏘리티를 통해서 찾아낼 수있습니다. 그리고 이들 헙과 오쏘리티는 광범위적 질의어의 검색 결과 중에서도 특별히 '좋은' 페이지로 생각해 볼 수 있는것입니다.

hubs and authorities
반복 알고리듬(An Iteration Algorithm)

위에서 살펴본 내용을 이제 수학적으로 기술해 봅시다.
"authority weight", 즉 오쏘리티 가중치를(높을수록 좋은 오쏘리티) x(p)라 하고,"hub weight", 헙 가중치를(높을수록 좋은 헙) y(p)라 하면 다음과 같은 두 가지의 연산을 생각해 볼 수 있습니다.

I Operation : i operation
O Operation : o operation

q-->p로의 링크가 있을 때 p 페이지의 오쏘리티 가중치는 q 페이지들의 헙 가중치 y(p)를 모두 합한 것입니다.
p-->q로의 링크가 있을 때 p 페이지의 헙 가중치는 q 페이지의 오쏘리티 가중치 x(q)를 모두 합한 것입니다.

그런데 이것은 반복적 알고리듬(iterative algorithm)이기 때문에 이터레이션을 시켜서 계산해야 합니다. 그렇게반복 연산을 했을 때 어떤 일정한 값으로 수렴하면서 평형을 이루는지 알아보는 것입니다. 그리고 수렴해서 일정한 값들을 갖는다면,우리는 각 페이지들의 최종 헙 가중치와 오쏘리티 가중치를 알게 될 것입니다. 어떤 페이지가 얼마나 좋은 헙인지, 얼마나 좋은오쏘리티인지를 알 수 있게 되는 것입니다.
이것을 알고리듬 형태로 표시해 볼까요?

x(p)의 집합 {x(p)}를 벡터 x라 하고, y(p)의 집합 {y(p)}를 벡터 y라 하면,

G : a collection of n linked pages
k : a natural number
Let z denote the vector (1,1,1,...,1) ∈ Rn.
Set x0 := z.
Set y0 := z.
For i = 1,2,...,k
Apply I operation to (xi-1, yi-1), obtaining new x-weights x'i.
Apply O operation to (x'i, yi-1), obtaining new y-weights y'i.
Normalize x'i, obtaining xi.
Normalize y'i, obtaining yi.
Return (xk, yk).

처음에는 모든 페이지에 대해서 헙 가중치, 오쏘리티 가중치를 1로 해서 I operation을 시행한 다음 얻은 새로운 x'를 이용, 이번에는 O operation (x만 x'i 이고 y 는 i-1 이라는 점에 주목하세요)을 시행해서 새로운 y'을 얻고, 이를 노멀라이징한 다음 다시 반복합니다. 언제까지? 우리가 정한 k번까지로 되어 있습니다. 알고리듬 자체는 아주 단순한 것입니다.

이때 노멀라이징하는 방법으로는 이 논문에서는,

∑ x(p)2 = 1
∑y(p)2 = 1

을 사용했습니다.

위에서 최종적으로 얻은 벡터 x의 각 원소는 각 페이지의 오쏘리티 가중치입니다. 벡터 y의 각 원소는 각 페이지의 헙가중치를 가리킨다는 점을 다시 상기하세요. 그리고, k값을 '상당히' 크게 해서 이터레이션을 계속 시키면 x, y 모두 일정한값으로 수렴합니다. 일정한 값으로 안정이 되고 나서 얻은 xk, yk 중에서 각각 상위 c개씩을 뽑아 내면 이들이 바로 우리가 찾는 좋은 헙과 좋은 오쏘리티가 되는 것입니다.

이 알고리듬을 실제 구현해서 그 결과를 싣고 있는데 상당히 인상적입니다. 예를 들어, "Gates"라는 검색어에 대해서 상위 3개의 오쏘리티는,
http://www.roadahead.com/ , http://www.microsoft.com/, http://www.microsoft.com/corpinfo/bill-g.html
로 나타났습니다. 순수하게 알타비스타에서 검색한 결과는 http://www.roadahead.com 페이지가 123번째 결과로 나왔다 합니다.

"search engines"라는 검색어에 대해서도 상위 5위까지를 살펴보면,
http://www.yahoo.com/, http://www.excite.com/ , http://www.mckinley.com/ (Magellan 검색엔진),http://www.lycos.com/, http://www.altavista.digital.com/
입니다. 우리가 찾는 오쏘리티를 잘 찾아낸다는 것을 알 수 있습니다.

정리해 봅시다. 이 논문을 통해 텍스트적인 정보를 전혀 감안하지 않은, 순수하게 링크 구조만을 사용해도 상당한 수준으로'좋은' 페이지를 판단해낼 수 있다는 사실을 알 수 있니다. 특히 페이지 내부적인 정보만으로는 그 페이지가 검색 결과 내에서얼마나 '좋은' 페이지인지를 판단하기가 힘든 데, 이 때 하이퍼링크를 이용함으로써 이 문제를 보다 객관적으로 해결할 수 있다는것을 알 수 있습니다.

문서출처: 이명헌 경영스쿨 http://www.emh.co.kr/xhtml/hubs_and_authorities.html
이 문서를 게시하거나 프린트하려면 위 문서출처를 반드시 포함해야 합니다.(참고: 저작권정책)

by Hans | 2007/08/13 20:39 | Interest | 트랙백(1) | 덧글(0)

Google Search Engine 해부 - 구글 페이지랭크(PageRank) 알고리즘.


웹 페이지의 '중요성'은 본질적으로 주관적인 문제여서 읽는 사람의 관심사나 지식 그리고 태도 등에 의존한다. 하지만 웹페이지의 상대적 중요성에 관해서는 객관적으로 얘기할 수 있는 부분이 많다. 이 논문은 객관적이고 기계적으로 웹 페이지를 랭킹해서읽는 사람의 관심이나 기울이는 주의를 효과적으로 측정할 수 있는 수단인 "PageRank"를 소개한다. 우리는페이지랭크(PageRank)를 이상적인 랜덤 웹 써퍼(random web surfer)에 비교해 볼 것이며, 어떻게 많은 웹페이지를 대상으로 PageRank를 능률적으로 계산할 수 있는지를 설명할 것이다. 그리고 어떤 방식으로 PageRank를검색이나 사용자 네비게이션에 응용할 수 있는지도 보여 주고자 한다.

1. 도입과 동기(Introduction and Motivation)

월드와이드웹(World Wide Web)은 정보검색(Information Retrieval)에 새로운 과제를 안겨 주었다.웹은 매우 거대하며 이질적(heterogenous)이다. 현재 추산으로도 약 1억5천만 페이지 이상이 웹에 존재하며, 이 숫자는매년 적어도 두 배씩 커지고 있다. 더욱 중요한 점은, 웹 페이지들이 극단적으로 다양하다는 것이다. 예를 들면 "Joe가 오늘점심 때 뭘 먹었지?"와 같은 질문이 있는가하면 정보검색에 관한 전문적 논문집이 있기도 하다. 이런 주된 도전 과제들 외에도웹에는 익숙하지 못한 초보 사용자들과 검색 엔진의 랭킹 기능(ranking function)을 교묘히 이용하려는 많은 웹페이지들로부터 비롯되는 문제점이 있다.

그러나 웹은 다른 "평면적"인 문서 컬렉션(flat document collections)과 달리 하이퍼텍스트가 있다.하이퍼텍스트(hypertext)는 웹 페이지 자체의 텍스트 외에 링크 구조(link structure)나 링크 텍스트(linktext)같은 상당한 수준의 부가적인 정보를 제공한다.

이 논문에서 우리는, 모든웹 페이지를 보편적 "중요도" 순으로 순위를 매기기 위해 웹의 링크 구조를 사용하였다. 이 랭킹은 페이지랭크(PageRank)라하며, 검색엔진 사용자나 웹 사용자가 거대한 이질적 세계인 월드와이드웹을 빠르게 이해할 수 있게 도와준다.

1.1 웹 페이지의 다양성(Diversity of Web Pages)

학술적 인용(academic citation)을 분석한 문헌은 이미 많이 존재하지만 웹 페이지와 학술 출판물 사이에는 많은 중요한차이가 있다. 학술 논문은 철두철미하게 리뷰되지만 웹 페이지는 '품질 관리'나 '출판 비용' 없이 늘어난다. 단순한 프로그램하나만으로도 아주 많은 페이지를 손쉽게 만들어 낼 수 있으며 인위적으로 인용 횟수를 쉽게 부풀릴 수 있다. 웹 환경 속에는 그안에서 이익을 찾는 많은 벤쳐들이 있기 때문에 이들이 사용자의 주의를 끌어오는 전략 역시 검색엔진 알고리듬의 발달에 맞춰서 함께진화되어 왔다. 이러한 이유로 복제가능한 특징을 세는 방식으로 웹 페이지를 평가하려는 전략은 손쉽게 악용될 수 있다. 게다가,학술 논문의 경우는 그 갯수를 정확히 셀 수 있을 뿐만 아니라 사실상 질적인 면 및 인용 횟수 등에서 유사하고 그 목적 역시비슷하다.(대개 '지식의 몸체'를 키우기 위한 목적으로 만들어진다.) 하지만 웹 페이지는 질적인 면에서나 사용적인 측면, 인용,길이 등에 있어서 학술 논문보다 훨씬 더 다양하다. IBM 컴퓨터에 관한 애매한 질문들을 모아놓은 것은 IBM 홈페이지와 매우다르다. 운전자에게 휴대폰이 미치는 영향에 관해서 연구한 논문은 특정 휴대폰 회사의 광고와 매우 다르다. 사용자가 읽은 웹페이지의 평균적인 질은 평균적인 웹 페이지의 질보다 높다. 그것은 웹 페이지를 만들고 퍼블리슁하는 것이 매우 쉽기 때문에 웹에는사용자들이 읽지 않으려 하는 많은 저품질의 웹 페이지가 있기 때문이다.

웹 페이지에는 여러 가지 분화될 수 있는 요소가 많이 있다. 이 논문에서 우리는 그 중의 하나 - 웹 페이지의 상대적 중요성을 어떻게 추산할 것인가 - 라는 문제를 주로 다룬다.

1.2 페이지랭크(PageRank)

웹페이지의 상대적 중요성을 측정하기 위해 우리는 웹 그래프를 기반으로 웹 페이지를 랭킹(ranking)하는 방식인 페이지랭크를제안한다. 페이지랭크는 검색이나 브라우징, 트래픽 추산에 적용될 수 있다. 섹션 2에서는 페이지랭크의 수학적 기술을 다룰 것이며직관적인 정당화(intuitive justification)를 얘기할 것이다. 섹션 3에서는 5억1800만 개에 이르는하이퍼링크에 대해 어떻게 효율적으로 페이지랭크를 계산할 수 있는지 보여주고자 한다. 페이지랭크의 유용성을 테스트하기 위해 우리는구글(Google)이라는 웹 검색 엔진을 구축했다. 이것은 섹션 5에서 다룬다. 섹션 7.3에서는 페이지랭크가 어떻게 브라우징을 도울 수 있는지 보여주고자 한다.

2. 웹 상의 모든 페이지의 순위 매기기(A ranking for every page on the Web)

2.1 관련 자료

학술 인용 분석에 관해서는 매우 많은 연구가 이미 존재한다. Goofman은 과학 커뮤니티에서 일종의 유행병처럼 정보 흐름이 퍼져 나간다는 것을 주장한 흥미로운 이론을 발표하기도 했다.

웹같은 대형 하이퍼텍스트 시스템에서 어떤 방식으로 링크 구조(link structure)를 이용할 수 있는지에 관해서도 최근들어상당한 연구가 이뤄지고 있다. Pitkow는 얼마 전에 다양한 방식의 링크 기반 분석을 설명한 "월드와이드웹 생태계의특징"이라는 제목의 박사 학위 논문을 완성했다. Weiss는 링크 구조를 감안한 클러스터링 방식에 대해서 논했다.Spertus는 여러 가지 적용사례에 있어서 링크 구조로 부터 얻어낼 수 있는 정보에 관해 발표했다. 좋은 시각화를 위해서는하이퍼텍스트에 부가적인 구조가 필요하다는 연구도 있었다. Kleinberg는 웹을 서로 인용하는 행렬로 보고 그고유벡터(eigenvector)를 계산하는 방식을 기반으로 "헙 & 오쏘리티(Hubs and Authorities) 모델"이라는 흥미로운 모델을 개발했다. 마지막으로, 도서관 커뮤니티 쪽에서는 웹의 "질"이라는 것에 대해 관심을 갖고 있기도 하다.

일반적인 인용 분석 테크닉을 웹의 하이퍼텍스트적 인용 구조에 적용하고자 시도하는 것은 너무도 자연스러운 것이다. 단순하게 웹페이지에 있는 각각의 링크를 학술적 인용처럼 생각해 볼 수 있는 것이다. 야후! 같은 메이져 페이지는 야후!를 가리키는 수 만,수십 만 개의 백 링크(backlinks) 또는 인용을 갖고 있는 것이다.

야후!홈페이지가 아주 많은 백 링크를 갖고 있다는 사실은 야후! 홈페이지가 매우 중요하다는 사실을 함축한다. 사실 많은 웹검색엔진들은 어떤 페이지가 얼마나 중요한가 내지는 높은 질을 갖고 있는가를 판단할 때 백 링크 숫자를 바탕으로 가중치를 주고있다. 하지만 단순히 백 링크의 갯수를 세는 것은 많은 문제점을 갖는다. 이 문제점들은 학술 인용 데이타베이스에는 존재하지 않는웹만의 특징과 관련이 있는 것들이다.

2.2 웹의 링크 구조(Link Structure of the Web)

약간의 편차는 있지만 현재 크롤링 가능한 웹 그래프는 약 1억5천만개의 노드(node;페이지)와 17억 개의엣지(edge;링크)가 있다고 알려져 있다. 각각의 웹 페이지는 그 페이지로부터 밖으로 나가는 포워드 링크(forwardlink; outedges)와 그 페이지를 가리키는 백 링크(backlink; inedges)를 갖는다. 어떤 페이지의 모든 백링크를 다 찾아낸다는 것은 불가능하지만 페이지를 다운로드하고 나면, 포워드 링크가 무엇인지는 알 수 있다.

backlink 백 링크

웹페이지가 백 링크를 몇 개나 갖느냐는 매우 다양하다. 우리가 갖고 있는 데이타베이스에 따르면 넷스케잎 홈페이지는 62804개의백 링크를 갖는데 반해 대개의 페이지들은 단지 몇 개의 백 링크만을 갖는다. 일반적으로 링크가 많이 된 페이지일수록 그렇지 못한페이지보다 더 "중요하다". 학술 인용에서도 인용의 횟수를 세는 단순한 방법이 미래의 노벨상 수상자를 예측하는 데 사용될 수있다. 페이지랭크는 인용 횟수를 세는 방식 이상의 훨씬 더 정교화된 방법을 제시한다.

페이지랭크가 흥미로운 이유는 인용 횟수가 일반적인 의미의 중요성과 일치하지 않는 경우가 매우 많기 때문이다. 어떤 웹 페이지가야후!에 링크가 되어 있다면 그 페이지는 오직 하나의 백 링크밖에 없지만 그 링크는 매우 중요한 링크다. 야후!에 링크된 그페이지는 다른 별 볼 일 없는 여러 곳에서 링크된 페이지보다 더 높은 순위를 가져야 한다. 페이지랭크는 링크 구조만을 사용해서어떻게 "중요성"을 정확히 추정해낼 수 있을까를 시도한 것이다.

2.3 링크를 통한 랭킹의 전파(Propagation of Ranking through Links)

위의 논의를 기초로, 우리는 페이지랭크에 대한 직관적 기술을 다음과 같이 할 수 있다: 어떤 페이지가 높은 랭크의 백 링크를 많이가질수록 그 페이지의 랭크도 올라간다. 이것은 어떤 페이지가 많은 백 링크를 갖는 경우와 몇 개의 높은 랭크값 백 링크를 갖는경우 모두를 포괄하는 것이다.

2.4 페이지랭크(PageRank)의 정의

어떤 웹 페이지를 u라고 하고 u 페이지가 가리키는 페이지들의 집합을 Fu, u 페이지를 가리키는 페이지의 집합을 Bu라하자. Nu = |Fu|라 하고, 이것은 u 페이지로부터 나가는 링크의 갯수, 즉 Fu의 갯수다. 그리고 노멀라이제이션에사용되는 팩터를 c라고 하자.(노멀라이제이션은 전체 웹 페이지의 랭크 총합을 일정하게 하기 위해서다.)

일단, 단순 랭킹 R을 정의하는 것에서 출발해 보자. 단순 랭킹 R은 페이지랭크(PageRank)를 약간 단순화시킨 버전이다.

Simple PageRank

위 식은 전 섹션에서 얘기한 직관을 공식화한 것이다. 어떤 페이지가 가리키는 페이지들의 랭크에 균일하게 기여하기 위해,링크가 나가는 페이지의 랭크를 그 페이지의 포워드 링크 갯수로 나누고 있다는 점에 주의하자. 그리고 c는 1보다 작아야 하는데,c < 1인 이유는 포워드 링크가 없는 페이지도 많이 있기 때문에 그런 페이지들의 가중치는 시스템 속에서 사라질 수 있기때문이다.(섹션 2.7을 참조하라.) 위 등식은 재귀적(recursive)인 식이지만 초기 랭크 집합을 주고 수렴할 때까지연산을 함으로써 계산할 수 있다.

단순 버전 페이지랭크

그림 2 단순화된 페이지랭크의 계산

단순 버전 페이지랭크의 계산
그림 3 정상상태를 이루고 있는 페이지들

그림 2는 한 쌍의 페이지로부터 다른 한 쌍의 페이지로 랭크가 전파되어 나가는 것을 보여주고 있다. 그림 3에서는 일군의 페이지들 사이에서 일정한 정상상태(steady state)의 솔루션을 이루고 있는 것을 볼 수 있다.

이것을 다른 방식으로 표현해 보자. 각 행과 열이 웹 페이지에 대응하는 정방행렬을 A라 하자. 그리고, 페이지 u에서 v로 가는 연결(edge)이 있다면 Au,v = 1/Nu이라 하고, 엣지가 없다면 Au,v는 0이라 하자. R을 웹 페이지들의 벡터로 생각해 보면, R = cAR이된다. 그러므로 R은 A의 아이겐벡터(eigenvector; 고유벡터)가 되고 아이겐밸류는 c이다. 사실, 우리가 원하는 것은A의 지배적 고유벡터(dominant eigenvector)다. 이것은 A를 여러 비퇴화적 시작 벡터(nondegeneratestart vector)에 반복적으로 적용함으로써 계산될 수 있을 것이다.

랭크 싱크
그림 4 랭크 싱크

위에서 살펴 본 단순화된 랭킹 함수는 약간의 문제가 있다. 두 페이지가 서로서로 가리키고 있으며 다른 페이지로는 연결되어있지 않은 경우를 생각해 보자. 다른 웹 페이지가 그 두 페이지 중 하나를 가리키고 있는 경우, 반복연산(iteration)이진행되면서 그 루프에서는 랭크가 계속 축적될 뿐 외부로 전혀 분산하지 못 한다.(왜냐하면 외부로 나가는 엣지가 전혀 없으므로.)루프는 일종의 함정을 형성하게 된다. 우린 이것을 랭크 싱크(rank sink)라 부른다. 랭크 싱크로부터 초래되는 문제를해결하기 위해, 우리는 랭크 소스를 도입한다.

정의 1:
랭크의 소스에 해당하는 웹 페이지의 벡터 중 하나를 E(u)라 하자. 그러면 일군의 웹 페이지들의 페이지랭크는 다음 식을 만족하며 ||R||1 = 1(||R||1은 R'의 L1 norm)이고 c가 최대값을 가질 때의 R'이다.역자주

PageRank 페이지랭크

E가 모두 다 양수이면 등식의 균형을 위해서 c 값이 줄어들어야만 한다는 것에 주의하자. 그러므로 이 테크닉은 소멸계수(decay factor)에 해당한다. 위 식을 행렬 용어로 표현하면 R' = c(AR' + E)이고, ||R||1 = 1이므로 이 식은 R' = c(A + E x 1)R'로 다시 쓸 수 있다. 여기서 1은 1로만 구성된 벡터다. 그러므로, R'은 (A + Ex1)의 아이겐벡터라고 할 수 있다.

역자주 L1 norm은(a,b,c,d,e,..)라는 벡터가 있을 때 (a+b+c+d+e+..)의 값을 의미합니다. '소스'(source)와'싱크'(sink)는 그래프 이론에서 나온 용어로, 아웃엣지가 없는, 즉 밖으로 나가는 링크가 없는 것을 싱크라 하고 반대로인엣지가 없는, 즉 안으로 들어 오는 링크는 없고 밖으로 나가는 것만 있는 것을 소스라 합니다.

2.5 랜덤 써퍼 모델(Random Surfer Model)

위와 같은 페이지랭크의 정의는 그래프 상의 랜덤 워크(random walks)라는 또 하나의 직관적 기반을 갖고 있는것으로 볼 수 있다. 단순화된 버전의 페이지랭크는 웹 그래프 상에서 랜덤 워크의 확률분포에 해당한다. 직관적으로 생각해 보면이것은 "랜덤 써퍼"의 행동을 모델링한 것으로 볼 수 있다. "랜덤 써퍼"는 무작위로 일련의 링크들을 클릭해 나간다. 하지만실제 웹 써퍼가 작은 루프에 빠져 들었을 때도 계속해서 그 루프 내를 맴돌 가능성은 거의 없다. 대신, 그 써퍼는 다른 페이지로점프하려 할 것이다. 부가적 팩터인 E는 바로 그 행동을 모델링한 것으로 볼 수 있다. 즉, 써퍼는 주기적으로 "지루해지고"E의 분포에 기반해서 선택된 무작위 페이지로 점프하는 것이다.

지금까지 우리는 E를 사용자 정의 퍼래미터로 생각했다. 대부분의 테스트에서 우리는 E를 모든 웹 페이지에 걸쳐 동일하게α값을 갖는 것으로 했다. 하지만, 섹션 6에서는, E 값이 달라짐에 따라 페이지의 랭크가 어떻게 "사용자화"될 수 있는지를보여줄 것이다.

2.6 페이지랭크 계산(Computing PageRank)

페이지랭크를 계산하는 것은 규모의 문제를 무시한다면 아주 간단명료하다. S를 웹 페이지의 벡터(E 같은)라 하자. 그러면 페이지랭크는 다음과 같이 계산될 수 있을 것이다.

R0 <--- S
Ri+1 <--- ARi
d <--- ||Ri||1 - ||Ri+1||1
Ri+1 <--- Ri+1 +dE
δ<--- ||Ri+1 - Ri||1
while δ> ε

d 팩터가 수렴속도를 빠르게 하고 ||R||1을 유지하는 것에 주목하자. 또 다른 노멀라이제이션 방법은 적절한 팩터를 R에 곱하는 것이다. d의 사용은 E의 영향에 작은 효과만 미칠 것이다.

2.7 댕글링 링크(Dangling Links)

이 모델과 관계되는 이슈 중 하나는 댕글링 링크 문제다. 댕글링 링크란 외부로 나가는 링크가 없는 페이지를 가리키는 링크를뜻한다. 댕글링 링크가 모델에 영향을 주는 이유는, 이것의 가중치가 어디로 분산되고 있는지가 불분명하고 또 아주 많은 댕글링링크가 존재하기 때문이다. 종종 댕글링 링크가 가리키고 있는 페이지는 다운로드되지 않은 페이지일 수도 있다. 웹을 통째로샘플링하는 것은 어렵기 때문이다.(현재 우리가 다운로드한 2400만 페이지에는 아직 URL이 가리키는 문서가 다운로드되지 않은5100만 개의 URL이 있는 상태다. 즉, 5100만 개의 댕글링 링크가 있는 것이다.) 댕글링 링크는 다른 페이지의 순위에직접적으로 영향을 주지는 않기 때문에, 우리는 모든 페이지랭크가 계산될 때까지 댕글링 링크를 그냥 제거했다. 페이지랭크 계산이다 끝난 뒤에, 즉 큰 문제를 일으키지 않게 되었을 때, 댕글링 링크를 다시 첨가할 수 있다. 링크가 제거됨으로써 그 페이지에있는 다른 링크의 노멀라이제이션이 영향받을 수는 있지만 크게 변화되는 건 아니다.

3 임플리멘테이션(Implementation)

스탠포드 웹 베이스 프로젝트(Stanford WebBase project)의 일환으로, 우리는 현재 총 2400만 페이지의리파지터리(repository)를 갖고 있는 완전한 크롤링 & 인덱싱 시스템을 구축했다. 웹에 있는 모든 URL을 찾을수 있게 하기 위해서는 모든 웹 크롤러가 URL 데이타베이스를 유지하고 있어야 한다. 웹 크롤러는 페이지랭크의 임플리멘테이션을위해, 크롤링하면서 만나는 링크의 인덱스만 구축하면 된다. 작업 자체는 단순한 것이지만 볼륨이 거대하기 때문에 쉽지 않다. 예를들어, 현재 우리가 구축한 2400만 페이지의 데이타베이스를 5일 안에 인덱싱하기 위해서는, 초당 50 페이지를 프로세싱해야한다. 보통의 페이지 하나에 통상 11개의 링크가 있으므로(무엇을 링크로 셀 것인가에 따라 달라질 수는 있다.) 초당 550개의링크를 프로세싱해야 하는 것이다. 또한, 우리가 구축한 2400만 페이지의 데이타베이스는 7500만 개의 각기 다른 URL을참조하고 있으며, 각각의 링크는 반드시 서로 비교되어야만 하는 것이다.

웹에 깊숙히 그리고 미묘하게 존재하는 결함들에 유연하게 대응할 수 있는 시스템을 구축하기 위해서 많은 시간이 걸렸다.웹에는 한없이 커다란 싸이트, 페이지, 심지어 끝없이 계속되는 긴 URL들이 있다. 상당수의 웹 페이지가 잘못된 HTML을 담고있기 때문에 파서(parser)를 디자인하는 것이 까다로왔다. 예를 들어, 우리는 URL에 /cgi-bin/이들어 있는 경우 크롤링하지 않았다. 물론, 웹은 계속해서 변하고 있기 때문에 "전체 웹"을 정확하게 샘플링한다는 것은불가능하다. 싸이트가 다운되는 경우도 있고, 어떤 경우는 자신의 싸이트를 인덱싱되지 않도록 해 놓기도 한다. 이런 모든 점에도불구하고, 우리는 공개적으로 접근가능한 웹의 실제 링크 구조를 상당한 수준으로 표현했다고 생각하고 있다.

3.1 페이지랭크 임플리멘테이션

우리는 각각의 URL을 각기 유니크한 정수로 변환하고, 하이퍼링크의 페이지를 구분할 수 있도록 모든 하이퍼링크를 페이지의 정수 ID를 이용해서 데이타베이스에 저장했다. 임플리멘테이션에 관한 자세한 사항은 구글 검색엔진의 해부학 논문에서 밝혔다. 보통, 페이지랭크는 다음과 같은 식으로 임플리멘테이션했다.

먼저, 부모 ID(Parent ID)를 이용해서 링크 구조를 정렬한다. 그 다음, 앞에서 말한 것과 같은 이유로 링크데이타베이스에서 댕글링 링크를 제거한다. (몇 번의 반복 작업만으로도 대부분의 댕글링 링크를 제거할 수 있다.) 그 다음, 랭크값을 초기화한다. 초기화 값을 어떻게 할 것인가는 어떤 전략을 갖고 있느냐에 따라 달라진다. 수렴할 때까지 반복작업을 계속할생각이라면, 일반적으로 초기값은 최종값에 영향을 미치지 않는다. 단지 수렴 속도만 빠르게 할 뿐이다. 하지만 초기값을 잘선택하면 수렴과정의 속도를 높일 수 있다. 우리는 초기 할당값을 신중하게 선택하면 제한적 횟수의 많지 않은 반복 작업만으로도아주 좋은 결과를 얻거나 더 나은 퍼포먼스를 만들어 낼 수 있다고 믿고 있다.

각 페이지의 가중치에 메모리를 할당한다. 우리는 단정도 부동소수점(single precision floatingpoint) 값을 사용했고, 각각은 4바이트씩 할당했으므로 7500만 개의 URL은 곧 300메가바이트의 크기가 된다. 만약모든 가중치를 담고 있을 만큼 램이 충분치 않으면 여러 번의 패쓰(pass)를 사용해도 된다.(우리가 임플리멘테이션한 것은메모리의 절반과 2개의 패쓰를 사용했다.) 현재 진행 중인 단계의 가중치는 메모리에 저장되고, 전단계의 가중치는 디스크를 통해리니어(linear)하게 억세스한다. 또한, 링크 데이타베이스 - 즉 알고리듬 정의에서의 A - 로의 모든 억세스도 정렬되어있기 때문에 리니어하다. 그러므로 A 역시 디스크에 저장될 수 있다. 이러한 데이타 구조들이 매우 큰 크기임에도 불구하고,리니어 디스크 억세스를 통한 각 반복작업에 걸리는 시간은 보통의 웍스테이션상에서 약 6분 정도면 된다. 가중치들이 수렴하고나면, 다시 댕글링 링크를 추가하고, 랭킹을 재연산한다. 댕글링 링크를 되돌려 넣은 뒤에 필요한 반복 작업 횟수는 댕글링 링크를제거하는 데 요구되었던 횟수와 똑같다는 점에 주의하라. 그렇지 않으면, 댕글링 링크의 일부는 가중치가 0이 될 것이다.

이상의 모든 과정은 현재의 임플리멘테이션의 경우 총 5시간이 소요된다. 수렴 조건을 덜 엄격하게 하고, 더 최적화를 한다면계산속도는 더 빨라질 수 있을 것이다. 또는, 아이겐벡터를 추산하는 보다 더 효율적인 테크닉이 사용되어도 퍼포먼스가 더 좋아질것이다. 어쨌든, 페이지랭크를 계산하는 데 필요한 코스트는 풀 텍스트 인덱스를 구축하는 데 필요한 것에 비하자면 아주 사소한것이라 할 수 있다.

4 수렴 특성(Convergence Properties)

그림 5에서 볼 수 있는 것처럼, 3억 2200만개라는 큰 링크 데이타베이스를 합리적으로 감내할 만한 수준으로 수렴시키는데 필요한 반복작업은 약 52회다. 데이타의 크기가 반이라면 대략 45회면 된다. 이 그래프를 통해서, 극단적으로 큰 크기의컬렉션에서도 페이지랭크가 아주 쉽게 확장될 수 있다는 것을 알 수 있다. 스케일링 팩터가 대략 logn과 거의 선형관계를 이룬다.

페이지랭크의 수렴
그림 5 페이지랭크 연산의 수렴

페이지랭크 연산이 아주 빠르게 수렴한다는 사실로부터 파생되는 한 가지 흥미로운 점은 웹이 익스팬더양그래프(expander-like graph)라는 점이다. 이 부분의 이해를 돕기 위해서 그래프 상의 랜덤 워크 이론의 간단한개론을 살펴 보자. 자세한 것은 Motwani-Raghavan이 쓴 페이퍼를 참조하라.

그래프 상의 랜덤 워크는 스토캐스틱(stochastic)한 과정이다. 즉, 임의의 한 타임스텝에 우리는 그래프 상의 특정노드에 서 있고, 다음 타임스텝에 어떤 노드로 이동할 것인지는 균일하게 무작위적으로 분포하는 아웃엣지 중 하나를 선택해서결정하는 것이다. 만약 모든 (너무 크지는 않은) 서브셋 노드 S가 이웃(neighborhood; S에 속한 노드들로부터아웃엣지를 통해 접근가능한 꼭지점들의 집합)을 가지고 있고, 그 이웃 노드의 크기가 |S|보다 α배 이상 크다면 그 그래프는하나의 익스팬더(expander)라고 할 수 있다. 그리고 만약, 특히 가장 큰 아이겐벨류가 두 번째로 큰 아이겐벨류보다 충분히더 큰 경우, 그 그래프는 좋은 익스팬젼 팩터를 갖고 있다고 볼 수 있다. 랜덤 워크가 빠른 속도로 그래프 상의 노드들의 제한된분포로 수렴해 가면 그 그래프는 래피들리-믹싱(rapidly-mixing)하다. 또한 그래프가 익스팬더이고 아이겐벨류분리(eigenvalue separation)를 갖고 있다면 그 랜덤 워크는 래피들리-믹싱인 경우라 할 수 있다.

이상의 내용을 페이지랭크 연산과 관련 지어 보자. 페이지랭크란 본질적으로, 웹 그래프 상의 랜덤 워크의 제한된 분포로결정짓는 것이다. 어떤 노드의 중요도 랭킹이란, 본질적으로 충분히 시간이 흐른 뒤에 랜덤 워크가 그 노드에 있을 확률인 것이다.페이지랭크 연산이 로그 시간 내에 종결될 수 있다는 사실은 랜덤 워크가 래피들리 믹싱이거나 그래프가 좋은 익스팬젼 팩터를 갖고있다는 말이 된다. 익스팬더 그래프는 여러 가지 바람직한 특성을 많이 갖고 있기 때문에 웹 그래프와 관계된 연산을 함에 있어서앞으로 다양하게 활용할 수 있을 것이다.

5 페이지랭크를 이용한 검색

페이지랭크의 주된 적용처는 검색이다. 우리는 페이지랭크를 활용한 두 가지 검색엔진을 임플리멘테이션했다. 하나는 단순한타이틀 기반의 검색엔진이고 다른 하나는 풀 텍스트 검색엔진이다. 후자의 이름은 구글이다. 구글은 표준적인 IR 측정치,근접성(proximity), 앵커 텍스트(웹 페이지를 가리키는 링크의 텍스트), 그리고 페이지랭크 등의 많은 요소를 바탕으로검색 결과를 랭킹한다. 페이지랭크가 어떤 이점을 갖는지에 관한 포괄적인 유져 스터디는 이 논문의 범위를 벗어나지만, 몇 가지비교 실험과 검색 결과 샘플을 이 논문을 통해 얘기해 보려 한다.

페이지랭크의 이점이 가장 크게 활용될 수 있는 부분은 덜 특화된 질의어(underspecified queries)를처리하는 것이다. 예를 들어, "스탠포드 대학"이라는 질의어를 넣으면, 일반적인 검색엔진은 스탠포드가 들어 간 많은 페이지들을결과로 보여 줄 뿐이다. 하지만 페이지랭크를 활용하면 스탠포드 대학 홈 페이지가 순위의 가장 위로 올라 오는 것이다.

5.1 타이틀 검색

페이지랭크가 검색에 활용되면 얼마나 유용한지를 시험해 보기 위해 우리는 1600만 페이지의 제목만을 사용하는 검색엔진을만들어 보았다. 그 검색엔진은 질의어를 넣으면 문서 제목에 질의어가 들어 있는 모든 웹 페이지를 찾은 다음, 그 결과를페이지랭크를 이용해서 정렬한다. 이 검색엔진은 아주 단순한 것이고 간단하게 구축할 수 있는데, 비공식적인 시험을 해 본 결과놀랄 만큼 훌륭한 성능을 보여 주었다. 그림 6에서 볼 수 있는 것처럼 "University"라는 검색어에 대해 페이지랭크를이용한 제목 검색엔진은 대표적인 대학들의 목록을 보여 준 것이다. 이 그림은 우리가 만든 MultiQuery 시스템으로, 두개의 검색엔진에 동시에 질의를 할 수 있는 시스템이다. 그림의 왼 편에 있는 것이 페이지랭크를 기반으로 한 타이틀 검색엔진이다.검색 결과에 있는 바 그래프와 퍼센티지는 탑 페이지를 100%로 잡고 페이지의 실제 페이지랭크 값에 로그를 취한 다음노멀라이징한 값이다. 이 논문의 다른 곳에서는 계속 퍼센타일(percentile)을 사용했지만 여기서는 아닌 것이다. 그림의오른 쪽에 있는 것은 알타비스타 검색엔진이다. 알타비스타의 검색 결과를 보면 "University"라는 질의어에 맷칭되는무작위적으로 보이는 웹 페이지들 그리고 여러 써버의 루트 페이지가 보인다. (알타비스타는 퀄리티 휴리스틱으로 URL의 길이를사용하는 것 같다.)

Multi Search
그림 6 "University" 검색어에 대한 결과 비교

5.2 랭크 머징(Rank Merging)

타이틀에 기반한 페이지랭크 시스템이 아주 훌륭한 결과를 보여 주는 이유는, 제목을 맷칭하는 것이 페이지의 높은 프리시젼을보장하고, 페이지랭크가 페이지의 높은 품질을 보장하기 때문이다. 웹 검색에서 "University" 같은 질의를 하는 경우,사용자가 살펴 볼 페이지보다 훨씬 많은 페이지들이 존재하기 때문에 리콜은 그다지 중요하지 않다. 리콜이 중요하게 요구되는 특화된검색의 경우는 풀 텍스트에 대한 전통적인 정보검색 점수와 페이지랭크를 함께 적용할 수 있을 것이다. 구글 시스템은 그런 형태의랭크 머징을 사용한다. 랭크 머징은 아주 까다로운 문제로 알려져 있어서 우리는 그런 형태의 질의어를 합리적으로 평가할 수 있게구축하기 위해 상당한 노력을 부가적으로 기울여야만 했다. 하지만, 그런 형태의 질의어에 있어서도 페이지랭크가 상당히 도움이된다고 생각된다.

5.3 몇 가지 샘플 결과

우리는 페이지랭크를 이용한 풀 텍스트 검색엔진인 구글을 이용해서 상당히 많은 테스트를 해 보았다. 완전한 형태의 유져스터디는 이 논문의 범위를 벗어나지만, 몇 개의 샘플을 이 논문의 부록 A에 수록했다. 더 많은 질의어에 대한 결과를 원하는분은 직접 구글을 테스트 해보면 된다.

표 1은 페이지랭크에 기반한 탑 15위 페이지 목록이다. 이 리스트는 1996년 7월 시점의 결과다. 최근 다시 페이지랭크를 계산해 보았을 때는 마이크로소프트가 넷스케잎보다 조금 더 큰 페이지랭크를 보여 주었다.

Top 15 페이지랭크
표 1

5.4 커먼 케이스(Common Case)

페이지랭크의 디자인 목표 중 하나가 질의어의 커먼 케이스를 잘 처리하게 한다는 것이었다. 예를 들어, 미시건 대학의 학생관리자 기능 시스템의 이름에 "wolverine"이라는 게 들어 있었던 것으로 기억하고 있는 사람이 "wolverine"이라는검색을 한다고 하자. 우리의 페이지랭크 기반 타이틀 검색엔진은 "Wolverine Access"를 검색 결과의 첫 번째로 보여준다. 이것은 대단히 합리적이다. 왜냐하면 모든 학생들은 Wolverine Access 시스템을 사용하고 있고,"wolverine"이라는 질의를 한 사람이라면 Wolverine Access 페이지를 살펴 보려 할 가능성이 매우 크기때문이다. 그런데 Wolverine Access 싸이트가 좋은 커먼 케이스라는 사실은 그 페이지의 HTML에는 전혀 담겨 있지않다. 심지어 이런 형태의 메타 정보를 페이지 내에 담을 수 있는 방법이 있다고 하더라도, 이런 류의 평가에 있어서는 페이지를만든 사람을 신뢰하기 힘들다는 게 문제가 된다. 웹 페이지를 만드는 많은 사람들이 자신이 만든 페이지가 웹에서 가장 훌륭하고가장 자주 읽힌다고 주장할 것이기 때문이다.

wolverine이라는 것에 관해서 가장 많은 정보를 담고 있는 페이지를 찾는 것과 wolverine 싸이트의 커먼케이스를 찾는 것은 전혀 다른 일이라는 사실이 중요하다. 웹의 링크구조를 통해 텍스트의 매칭 점수를 전파해 나감으로써 어떤주제를 자세하게 다룬 싸이트를 찾아내는 흥미로운 시스템이 있다.(Massimo Marchiori. The quest forcorrect information on the web: Hyper search engines.) 그 시스템은 그런 과정을 통해가장 중심적인 경로에 포함되는 페이지들을 결과로 보여주는 것이다. 이런 방식은 "flower" 같은 질의어의 경우 좋은 결과를보여 준다. 즉, 그 시스템은 '꽃'이라는 주제를 자세히 다루고 있는 싸이트에 도달할 수 있는 경로 중 가장 좋은 것을 보여주는것이다. 이것과 커먼 케이스를 찾는 접근법을 비교해 보자. 커먼 케이스 접근법은 꽃에 관한 정보대신 꽃을 구입하는 방법만이담긴, 사람들이 가장 많이 찾는 꽃 판매 싸이트를 보여줄 지도 모른다. 두 가지 방식 모두 중요하다는 게 우리의 생각이고,일반적 목적의 웹 검색엔진이라면 마땅히 위의 두 가지 태스크 모두에 있어서 만족스러운 결과를 보여줘야 한다고 생각한다. 이논문에서는, 우리는 커먼 케이스적 접근법에만 집중하고 있다.

5.5 커먼 케이스의 하부 구성요소(Subcomponents of Common Case)

페이지랭크가 도움이 될 수 있는 커먼 케이스 시나리오가 어떤 성격을 갖는가를 생각해 보는 것은 무척 유익하다. Wolverine Access 싸이트처럼 가장 자주 사용되는 페이지 외에도, 페이지랭크는 협동적 오쏘리티또는 신뢰할 수 있는 싸이트 역시 표현해 준다. 예를 들어, 사용자는 어떤 뉴스가 단지 뉴욕 타임즈 홈 페이지로부터 직접링크되어 있다는 이유만으로 더 선호할 수 있다. 물론, 그 뉴스 페이지는 뉴욕 타임즈처럼 중요도가 높은 페이지로부터 링크되어있다는 사실만으로 매우 높은 페이지랭크 값을 갖게 된다. 이것은 일종의 협동적 신뢰(collaborative trust)의특성을 잡아내고 있는 것처럼 보인다. 왜냐하면, 신뢰도가 높고 권위 있는 소스로부터 언급된 페이지일수록 그 페이지의 신뢰도와권위가 올라가기 때문이다. 유사하게, 페이지의 품질이나 중요도 역시 이런 류의 순환적 정의에 잘 부합되는 것 같다.

6 개인화된 페이지랭크(Personalized PageRank)

페이지랭크 연산의 중요한 요소 중 하나가 E이다. E는, 랭크 싱크처럼 아웃엣지가 없는 싸이클을 보충하기 위한 랭크 소스웹 페이지의 벡터다. 한편, E는 랭크 싱크 문제에 대한 해결책으로써뿐만 아니라, 페이지랭크 값을 조정할 수 있는 강력한퍼래미터이기도 하다. 직관적으로 보자면, E 벡터는 랜덤 써퍼가 주기적으로 점프해 가는 웹 페이지의 분포에 해당한다. 밑에서살펴 보겠지만, 이것은 웹을 거시적으로 관찰하거나 특정 부분에 대해 집중적이고 개인화된 관찰을 하는 데 사용될 수 있다.

우리가 수행한 실험은 대부분 E 벡터를 모든 웹 페이지에 걸쳐 균일하게 ||E||1 = 0.15로가정했다. 즉, 랜덤 써퍼가 주기적으로 또 다른 랜덤 웹 페이지로 점프하는 것을 가정한 것이다. 이것은 모든 웹 페이지가 단지존재하고 있다는 이유만으로 똑같이 가치를 부여받는 것이므로 E를 무척 민주적으로 선택한 것이다. 이런 테크닉이 상당히성공적이었기는 했지만 중요한 문제점도 갖고 있다. 관련 링크가 많은 어떤 웹 페이지들이 지나치게 높은 랭킹을 받을 수 있는문제다. 예컨데, 저작권 관련 페이지나 상호간에 링크가 많이 된 메일링 리스트 모음 등이 여기에 해당한다.

또 하나의 극단적 형태로, E를 오직 하나의 웹 페이지로만 구성할 수 있다. 우리는 두 가지로 실험해 보았다. 하나는넷스케잎 홈 페이지로 해 보았고 다른 하나는 유명한 컴퓨터 과학자인 존 맥카씨(John McCarthy)의 홈 페이지로 했다.넷스케잎의 홈 페이지로 한 실험은, 넷스케잎을 기본 홈 페이지로 하고 있는 초보 사용자의 시각에서 페이지의 랭크를 만들어 내려는시도를 한 것이다. 존 맥카씨의 홈 페이지를 이용한 실험은, 그의 홈 페이지에 있는 링크를 바탕으로 우리에게 상당한 문맥적정보를 제공한 개인의 시각에서 페이지랭크를 계산한 것이다.

두 경우 모두, 위에서 말한 메일링 리스트 문제가 나타나지 않았다. 그리고 두 경우 모두에서, 각각의 홈 페이지가 가장높은 페이지랭크 값을 나타냈으며 그 페이지로부터 직접 연결된 페이지들이 그 뒤를 이엇다. 그 다음 시점부터는 불균형은 줄어들었다. 표 2는 각각의 경우에서 여러 페이지들의 페이지랭크 퍼센타일을 나타낸 것이다. 컴퓨터 사이언스에 관계된 페이지일수록넷스케잎 쪽 랭크보다 매카씨 랭 크쪽이 더 높은 값을 갖고, 특히 스탠포드 대학의 컴퓨터 사이언스 학과와 관계되는 페이지는 더욱높은 매카씨 랭크 값을 갖는 것을 볼 수 있다. 예를 들어 스탠포드 컴퓨터 사이언스 학과의 또 다른 교수의 웹 페이지는 매카씨쪽 랭크가 넷스케잎의 경우보다 6 퍼센타일 더 높다. 그리고 페이지랭크 값을 퍼센타일로 표시한 것에 주의하자. 이렇게 한 것은상위 순위에서 나타나는 페이지랭크 값의 큰 차이를 줄여서 표현하기 위해서다.

Netscape vs McCarthy
표 2

위와 같은 개인화된 페이지랭크는 개인화된 검색엔진처럼 다양하게 응용할 수 있을 것이다. 개인화된 검색엔진은, 단순히북마크나 홈 페이지를 입력하는 것만으로 사용자의 취향을 상당 부분 효과적으로 추측해내서 사용자의 수고를 대폭 덜어줄 수 있을것이다. "Mitchell"이라는 질의어로 시행한 예를 부록 A에 수록했다. 그 예를 보면, 웹 상에 "Mitchell"이라는이름을 가진 사람이 아주 많음에도, 존 매카씨 교수의 동료인 존 밋첼 교수의 홈 페이지가 결과의 1위로 나타난 것을 볼 수 있다.

6.1 상업적 이익을 위한 조작

이런 형태의 개인화된 페이지랭크는 상업적 이익을 위해 조작하는 것을 사실상 완전히 차단할 수 있다. 높은 페이지랭크 값을갖기 위해서는 중요한 페이지로부터 언급되거나 중요하지 않은 많은 페이지로부터 링크되어야만 한다. 최악의 경우, 중요한 싸이트에서광고(링크)를 구입하는 형태의 조작이 있을 수 있겠지만 그건 비용이 소요되므로 충분히 조절 가능하다. 조작에 대한 이런 저항성은정말로 중요한 특성 중 하나다. 왜냐하면 상업적 조작 때문에 많은 검색엔진이 골머리를 앓고 있으며 훌륭한 기능을임플리멘테이션하는 것이 조작 때문에 매우 어려워지기 때문이다. 예컨데, 문서가 자주 업데잇되는 것은 매우 바람직한 특징임에도검색 결과를 조작하고자 하는 사람에 의해 이런 특징이 남용되고 있는 것이다.

균일한 E로 할 것인지 아니면 단일 페이지 E로 할 것인지의 절충안으로 E를 모든 웹 써버의 루트 수준 페이지로 구성할수도 있다. `이 경우, 어느 정도의 페이지랭크 조작이 가능하다는 것에 주의해야 한다. 많은 루트 레벨 써버를 확보해서 특정싸이트로 링크하면 간단히 조작되기 때문이다.

7 적용(Applicaitons)

7.1 웹 트래픽의 추산

페이지랭크는 대략 랜덤 웹 써퍼에 해당하기 때문에(섹션 2.5 참조), 페이지랭크가 실제 사용도와 어떻게 대응되는지 알아 보는 것은 아주 흥미로운 일이다. 우리는 NLANR(NLANR)의 프록시 캐쉬로부터 얻은 웹 페이지의 접근 횟수를 페이지랭크와 비교해 보았다. NLANR 데이타는 미 전역에 있는 프록시캐쉬에 있는 여러 달에 걸쳐진 기록으로, 11,817,665개의 각기 다른 URL에 관한 자료이다. 그 데이타에 따르면 가장히트가 높은 것은 알타비스타로 638,657 히트다. 그 데이타베이스는 우리가 갖고 있는 7500만 개 URL 데이타베이스와260만 페이지가 중복된다. 이들 데이타셋을 분석, 비교하는 것은 몇 가지 이유에서 대단히 까다로운데, 우선 캐쉬 억세스데이타에 있는 많은 URL들이 무료 이메일 서비스에 있는 개인 메일을 읽기 위해 접근한 것들이라는 점이 있다. 그리고 중복된써버 이름과 페이지 이름도 심각한 문제점이다. 불완전성과 편향됨은 페이지랭크 데이타와 사용도 데이타 모두에서 문제가 된다.하지만, 몇 가지 흥미로운 트렌드를 볼 수 있었다. 캐쉬 데이타에서는 포르노그래프 싸이트들이 높은 사용도를 보였음에도 이들의페이지랭크 값은 대부분 낮았다. 이것은, 사람들이 자신의 웹 페이지에 포르토그래피 싸이트로 링크하는 것을 원하지 않기 때문인것으로 생각된다. 그러므로 페이지랭크와 사용도 데이타 사이의 차이점을 살펴 보는 것을 통해, 사람들이 보고는 싶어하는데 자신의웹 페이지에서는 언급하고 싶어 하지 않는 게 어떤 것이 있는지를 알아낼 수 있을 것이다. 어떤 싸이트는 매우 높은 사용도를갖는데 페이지랭크가 낮은 경우가 있다. netscape.yahoo.com 같은 게 그렇다. 이것은 아마도 우리 데이타베이스에중요한 백 링크가 누락되어 있기 때문인 것 같다. 우리 데이타베이스는 웹 링크 구조이 일부분만을 담고 있기 때문이다. 사용도데이타를 페이지랭크 계산의 시작 벡터로 사용하고 페이지랭크 연산을 몇 차례 반복하는 것도 가능할 것이다. 이렇게 하면 사용도데이타가 채워주지 못 한 부분을 메꿀 수 있을 것이다. 어떤 식이 되었든, 이런 형태의 비교는 향후 연구를 위한 흥미로운주제이다.

7.2 백 링크 예측자로써의 페이지랭크

페이지랭크는 백 링크의 예측자로써의 의미가 있다. "Efficient crawling through urlordering"(Junghoo Cho, Hector Garcia Molina, and Lawrence Page) 논문에서,우리는 어떻게 웹을 효율적으로 크롤링할 수 있는지, 더 좋은 문서들을 먼저 크롤링할 수 있는지의 문제를 탐색했다. 우리는스탠포드 웹에서 시행한 테스트를 통해서 페이지랭크가 단순히 인용 횟수를 세는 것보다 훨씬 더 좋은 미래 인용 횟수의 예측자라는것을 알게 되었다.

실험은, 다른 정보 없이 단일 URL에서 출발해서 가급적 최적의 순서에 가깝게 페이지를 크롤링하는 것을 목표로 하고 있다.최적의 순서란 평가함수에 따른 랭크 순서와 정확히 일치하는 순서로 페이지를 크롤링하는 것이다. 이 실험에서의 평가함수는 완전한정보가 주어졌을 때의 인용 횟수 순서로 했다. 문제는, 평가함수를 계산할 정보를 완전히 알게 되는 것은 모든 문서를 크롤링한다음이라는 점이다. 이렇게 불완전한 데이타를 사용해서 크롤링 순서를 정할 때, 단순히 이미 알고 있는 인용 횟수를 활용하는것보다 페이지랭크를 이용하는 쪽이 더 효과적인 것으로 드러났다. 바꿔 얘기하자면, 심지어 측정 기준이 인용횟수를 세는것일지라도, 페이지랭크가 인용회수를 직접 세는 것보다 더 좋은 예측자라는 얘기다! 이것의 이유는 페이지랭크의 경우 인용 횟수를세는 것이 국소적으로만 최대화되는 것을 피할 수 있기 때문인 것 같다. 예를 들어, 인용 횟수를 직접 세는 경우에는 스탠포드CS 웹 페이지들의 컬렉션 속에만 빠져 드는 경향이 있어서 그곳을 벗어나 다른 곳에 있는 인용 회수가 높은 페이지를 찾아 나서는데 오랜 시간이 걸린다. 하지만 페이지랭크는 스탠포드 홈 페이지가 중요하다는 것을 금방 알게 되고, 그 하부 페이지들에게우호적인 점수를 주기 때문에 더 효율적이고 광범위한 검색이 가능한 것이다.

이러한 인용 횟수의 예측자로써의 페이지랭크의 능력은 페이지랭크를 사용해야 하는 아주 설득력 있는 이유가 된다. 웹의인용구조를 완전히 매핑하는 것은 아주 까다롭기 때문에, 인용 횟수를 직접 세는 것보다 페이지랭크가 훨씬 더 좋은 인용 횟수근사치가 될 수 있는 것이다.

7.3 사용자 네비게이션: 페이지랭크 프락시(User Navigation: The PageRank Proxy)

우리는 사용자가 각 링크의 페이지랭크와 함께 부가적인 설명을 볼 수 있는 웹 프락시 애플리케이션을 개발했다. 그애플리케이션은 아주 유용했는데, 사용자가 링크를 클릭하기 전에 관련 정보를 미리 알 수 있기 때문이다. 그림 7은 프록시프로그램의 스크린샷이다.빨간 바의 길이는 URL의 페이지랭크 값에 로그를 취한 값이다. 그림을 보면 스탠포드 대학 같은 메이져조직은 매우 높은 랭킹을 받게 되고, 뒤이어 리서치 그룹이, 그 다음으로 개인이 -개인의 경우 스케일의 최상단에는 교수가위치한다 - 나타남을 알 수 있다. 또한 ACM이 스탠포드 대학보다는 높지 않지만 매우 높은 페이지랭크를 갖는 것도 볼 수있다. 재미있는 것은, 아주 지명도가 높은 교수의 페이지가 심할 정도로 낮은 페이지랭크 값을 갖고 있는 것을 찾으면 URL이잘못 되어 있는 것을 찾아낼 수 있다는 점이다. 결과적으로, 프락시 툴은 네비게이션 뿐만 아니라 페이지 제작에도 도움이 될 수있는 것 같다. 이 프락시 애플리케이션은 다른 검색엔진의 결과를 살펴 보는 데에도 아주 유용하다. 그리고 야후의 리스팅 같이링크가 매우 많은 페이지를 파악하는 데도 큰 도움이 된다. 프락시를 통해서 많은 링크 중 어떤 것이 더 흥미로운 것인지를 짐작할수 있기 때문이다. 또는 자신이 찾고 있는 링크가 "중요도" 측면에서 어느 정도인지를 알 수도 있고, 훨씬 더 빠르게 페이지를전체적으로 살펴볼 수 있다.

PageRank Proxy
그림 7 페이지랭크 프락시

7.4 페이지랭크의 다른 용도

페이지랭크의 최초 목표는 백 링크를 정렬해서, 만약 어떤 문서가 많은 백 링크를 갖는다면 그 중 어떤 것이 "최상"의것인지를 찾아서 그걸 가장 먼저 보여주려는 것이었다. 그리고 우리는 그런 시스템을 임플리멘테이션했다. 페이지랭크를 기준으로정렬된 백 링크를 살펴 보는 것은 경쟁을 파악하는 측면에서도 아주 흥미롭다. 예를 들어, 뉴스 싸이트를 운영하는 사람이라면경쟁자가 확보한 중요한 백 링크가 어떤 것인지 지속적으로 관찰하고자 할 것이다. 또한, 페이지랭크는 사용자가 어떤 싸이트가신뢰할 수 있는 것인지 아닌지 판단하는 데 도움을 준다. 예를 들어, 스탠포드 홈 페이지에서 직접 인용된 정보라면 아무래도사용자가 더 신뢰하려 할 것이다.

8 결론

이 논문에서, 우리는 웰드 와이드 웹 상의 모든 페이지를 페이지랭크라는 단일한 숫자로 압축하고자 하는 담대한 작업을 다루어보았다. 페이지랭크는 페이지의 컨텐트와 상관없이, 오직 웹의 그래프 구조 상의 위치에만 의존하는 모든 웹 페이지의 글로벌랭킹이다.

페이지랭크를 사용함으로써 우리는 더 중요하고 중심적인 웹 페이지들을 더욱 선호하는 식으로 검색 결과를 정렬할 수 있다.여러 실험을 통해서, 페이지랭크는 고품질의 검색 결과를 보여줌을 알 수 있었다. 페이지랭크의 기반이 되는 직관은 웹 페이지외부에 있는 정보, 즉 일종의 피어 리뷰인, 백 링크를 사용한다는 것이다. 게다가, "중요한" 페이지들로부터의 백 링크는평균적인 페이지들로부터의 백 링크보다 더 중요하며, 이것은 페이지랭크의 재귀적인 정의(섹션 2.4 참조)를 통해 확실히 구현되어있다.

페이지랭크는 대부분의 질의어에 대한 답변이 될 수 있는 소수의 자주 사용되는 문서들을 분리해 내는 데에도 사용될 수 있다.풀 데이타베이스는 작은 데이타베이스가 질의어에 적절히 응답할 수 없을 때만 참조되면 된다. 마지막으로, 페이지랭크는 클러스터의센터로 사용할 수 있는 대표 페이지를 찾아내는 좋은 방법이 될 수도 있을 것이다.

페이지랭크는 검색 외에도 트래픽 추산이나 사용자 네비게이션 같은 다른 많은 곳에 적용될 수 있다. 또한, 웹을 특정 시점에서 바라볼 수 있는 사용자화된 페이지랭크 역시 만들어 낼 수 있다.

종합하자면, 페이지랭크를 이용한 실험은 웹 그래프의 구조가 다양한 정보검색 작업에서 매우 유용하게 사용될 수 있음을 보여 준다고 할 수 있다.

by Hans | 2007/08/13 20:33 | Search Engine | 트랙백(3211) | 덧글(0)

◀ 이전 페이지 다음 페이지 ▶