구글 검색 랭킹 알고리즘 개선 제안

Posted at 2007. 11. 29. 17:55 // in 구글이야기 // by 김윤수


전문 자료를 검색할 때는 PageRank 라는 알고리즘이 탁월하지만 시간에 따라 계속해서 바뀌어가는 사람들의 관심사를 따라갈 수는 없다. 시간에 따라 바뀌는 사람들의 관심사를 따라갈 수 있는 새로운 랭킹 알고리즘(편의상 TrendRank라고 하자)이 필요하다. TrendRank에 따라 미리 계산된 랭킹이 PageRank 와 함께 참조되어 검색 결과가 리턴되어야 한다. 아니면 검색 UI 에 '관심도순'이라는 걸 누르면 이런 TrendRank가 적용되게 할 수 있을 것이다.

TrendRank 는 다음과 같은 사항들이 고려되어야 한다

  • Ranking을 매기려는 문서와 비슷한 키워드(또는 태그)를 갖는 문서들 또는 내용을 갖는 문서들이 많을 경우, 그 안에서는 오래된 문서의 랭크를 높인다. why ? 한 번 기사 또는 글이 뜨면 계속해서 확대 재생산되는 현상을 모델링하기 위해
  • Document Cluster 안에서 그 Cluster 가 생성된 시점(가장 오래된 문서가 생성된 시점)부터  PageRank 가 높아진 문서들에 대해서는 랭크를 더 높인다. why ? PageRank 도 일종의 Attention 이므로 그 Cluster 안에서 PageRank가 높다면 상당히 좋은 검색 결과가 될 것임. 보통 이슈가 된 것들에 대해서는 한참이 지나면 그 내용을 정리하는 글이 나오기 마련임. 그런 글들은 들어오는 링크도 많고 나가는 링크도 많아짐.
  • 최근에 많은 사람들이 입력한 키워드에 매치가 되는 Document Cluster 의 랭크를  전체적으로 높인다
  • Attention 이라고 할 수 있는 것들을 반영: 댓글, 트랙백, 검색 후 클릭된 회수 및 체류 시간, 북마크 회수 등을 고려
  • 해당 키워드를 사람들이 얼마나 많이 입력하고 있는가 ? 키워드가 많이 입력되기 시작한 시점을 찾아내어 그 이후 문서의 랭크를 높인다.
  • Document Cluster 는 계속해서 Update 하되 그 안에서의 랭킹을 매기는 주기는 PageRank 보다는 자주해야 할 것임.
구글이 이미 이렇게 하고 있나요 ? 이렇게 하고 있으면 검색 결과가 지금처럼 나올 것 같진 않은데 말입니다.

Daum 블로거뉴스
블로거뉴스에서 이 포스트를 추천해주세요.
제 글이 유익하셨다면 오른쪽 버튼을 눌러 제 블로그를 구독하세요. -> 한RSS에 추가
블로그를 구독하는 방법을 잘 모르시는 분은 2. RSS 활용을 클릭하세요.
RSS에 대해 잘 모르시는 분은 1. RSS란 무엇인가를 클릭하세요.

  1. META-MAN

    2007.11.29 17:21 신고 [수정/삭제] [답글]

    재미있네요~~~
    저도 이런 알고리즘에 관심이 많답니다.
    머 프로세스 스케쥴에 관한 유명한 알고리즘이 많은데, 그런 알고리즘들은 기본적으로 Priority와 Staving Problem 그리고 Round Robin Problem 그리고 님의 알고리즘 제안에서 발생할 개연성이 보이는 Exclusive Problem에 대해 고민을 하더군요....

    문제는 님이 잘 지적하신대로, 과연 Preference를 어떻게 수치화 하는 거겠네요, 수학적으로 Preference는 NP-complete이니, 완벽한 검색엔진은 시도 자체가 개소리라는~~~
    하지만 Optimization은 할 수 있겠지요, 잘 정리 하시면 누가 알겠습니까. 님의 알고리즘이 특허로 보호받는 비지니스 서치엔진의 근간이 될지....

    참고로 몇년전까지 잉크토미,구글,알타비스타등은 서로의 검색엔진의 인덱스 숫자로 경쟁했었다고 하네요, 그런데 암만 검색로봇이 돌아 다녀도 이미 무한의 크기처럼 커져버린 웹을 다 검색 할 수 없어서 포기했다고 합니다.
    대신 님이 지적한 Preference와 Quality에 치중한다고 들은 기억이 납니다. 현재 구글의 전체 웹 커버리지는 10%가 조금 넘는다고 합니다. 아직 웹은 암흑의 세계~~~~~~

    남이 포기한걸 하는걸 바보 스러울수도 있지만, 남이 포기한걸 함으로써 또~~~ 엄청난 무엇이....

  2. yundream

    2007.11.29 20:29 [수정/삭제] [답글]

    검색된 Term을 포함한 문서중 오래된 문서에 더 많은 점수를 주는 것은 현재의 PageRank에서도 어느정도 수용이 되는 것 같습니다. 오래된 문서일 더 많이 인용(링크)되었을 확률이 높기 때문입니다.

    "최근에 많은 사람들이 입력한 키워드에 매치가 되는 Document Cluster 의 랭크를 전체적으로 높인다"의 경우에는 사용자가 두개 이상의 Term으로 이루어진 쿼리를 날렸을 경우에 쓸모가 있습니다. 왜냐면 Term A의 쿼리수치가 높아져서 Document Cluster의 랭크를 전체적으로 높인다고 하면, 해당 Cluster의 모든 문서들에 동일하게 값이 적용되기 때문입니다.
    단 사용자가 "TermA TermB"로 쿼리를 만들었고 TermA가 뜨는 단어라면 TermA를 포함한 문서를 TermB만 포함한 문서보다 가중치를 줄 수는 있을 거라 생각됩니다.
    하지만 역시 좀 문제가 있는데요. 복수개의 Term이 주어질 경우에는 Term간의 거리가 스코어에 미치는 영향이 큰데, 여기에 Term의 트랜드를 포함시키고자 할경우 가중치를 계산하기가 애매모호해 집니다.
    블로그 문서로 검색 범위를 축소시킨다면, 인기검색어와 태그를 가중치로 곱해주는 방법은 유효할 수 있을거 같습니다.
    하지만.. 블로그라는게 "시간"이 매우 중요한 요소라는게 문제입니다. 뜨는 단어는 시간적으로 최신에 만들어진 문서일 것이니 일반적으로 최근시간은 최근트랜드를 반영한다고 볼 수 있거든요. 그러므로 대개의 경우 TF*IDF*시간가중치를 주는 정도로도 거의 비슷한 효과를 낼 수가 있습니다.

    물론 해당 Cluster 내에서 예전문서의 Rank를 높여주는 방법도 생각해 볼 수 있겠지만, 오래된 문서가 더 나은 가치를 보장하는 웹문서와는 다른 특징 때문에 예전 문서의 Rank를 올려주는 것도 애매모호한 측면이 있습니다.

    그리고 위의 방식들은 2개 이상의 Term이 주어질 경우에 효과를 발휘할 확률이 높은데, 제가 알기로는 90% 이상의 쿼리가 단일 쿼리입니다.

  3. yundream

    2007.11.29 20:32 [수정/삭제] [답글]

    제 생각에는 Page Rank를 수정하는 개념보다는 Site Rank, Bloger Rank 등을 도입하는게 더 나을거 같습니다.

    개인적으로 생각하는 바가 있는데, 나중에 시간이 되면 정리해볼 생각입니다. 좋은글 잘 읽었습니다.

  4. 김윤수

    2007.11.29 21:19 신고 [수정/삭제] [답글]

    컥! 번데기 앞에서 주름 잡았군요

  5. markov

    2007.12.01 06:03 신고 [수정/삭제] [답글]

    좋은 글 잘 읽었습니다. 제안하신 아이디어는 굳이 PageRank에 국한될 필요 없이, 임의의 랭킹 함수를 튜닝하는 목적으로 유용하게 쓰일 수 있을 것 같습니다.
    사실 PageRank 자체는 다른 criterion들과 쉽게 융합시키기가 힘듭니다. '주어진 페이지에 랜덤 서핑을 통해 도달할 확률'이라는, 하나의 완성된 수학적 틀 안에서 정의된 값이라, 이론을 깨뜨리지 않고 확장시키려면 여러모로 제한적이죠. yundream님도 아마 이런 의미로 새로운 ranking measure를 도입하는 것을 말씀하시지 않았을까 싶네요..

댓글을 남겨주세요.