검색엔진
Pagerank의 가장 큰 문제점은 좋은 글이 시간이 가면 갈수록 너무 유명해져서 새롭게 등장하는 좋은 글이 랭킹의 위로 올라갈 기회를 안준다는데 있다. 물론 구글에서도 이런것에 대한 개선사항이 있었겠지만, 어제 화장실에서 철학책을 뒤적이면서 링크 정보를 활용한 랭킹시스템에 위의 문제를 개선할 좋은 방법을 생각해 냈다. 상대적인것과 절대적인 것의 의미의 차이를 잘 생각해보면 알수 있다. 다만 구현상에 중요한것은 링크정보를 [...]
문서 중복에 대해서 예전에 Shingle 방법에 대한글을 쓴 경험이 있다. 주로 중복문서의 제거의 Key Issue는 검색 복잡도를 해결하는것이라고 할 수 있다. md5 hash를 이용하는 방법은 O(n)의 복잡도를, Shingle 계열의 방법을 사용하는것은 O(n^2)의 복잡도를 자랑한다. 어느글과 비슷한 글을 찾기 위한 기능을 검색엔진에서 제공한다면 아마도 주로 Shingle을 이용한 여러가지 방법들중에 하나를 사용해서 제공하리라 본다. 하지만 이는 미리 [...]
오늘 오픈마루에서 inverted index compression 발표를 했다. ppt는 아래 논문과 서적을 참고로 만들었다. 무엇보다 이 발표자료를 만들면서 그동안 몇가지 알고리즘을 알고 있었던것과 더불어 새로운 알고리즘까지 내 자신이 스스로 총정리 할 수 있었던 아주 좋은 기회가 되었던거 같다.그리고 앞으로 어떤 Doc Id특성을 가지고 있을경우는 어떤걸 쓴다든지 하는 그런 나만의 아니 그 누구나 수긍할 수 있는 설득력 [...]
Continue reading about 오픈마루에서 Inverted Index Compression에 대해서 발표했습니다.
오늘 커널 공부하다가 지루한 나머지 Distribute Indexing에 대한 공부를 좀 해봤다. (역시나 지루한 코드를 보는것보다 이런 개념 학습이 더 재미난다. ^^) 예전에 MapReduce에 대한 개념을 설명할 때가 있었다. 이때 내가 느낀것은 단 한가지 였다. MapReduce는 큰일을 작은 일로 분산시켜서 처리할때 굉장히 심플한 처리 공정을 보여 준다는 것이다. 그럼 여기서 Distribute Indexing을 하는 이유는 무엇인가? 1. 웹 [...]
쿼리 프로세싱(Query Processing)은 검색 결과를 가져오는 프로세스이다. 그럼 어떻게 Query에 맞는 결과를 가져올 것인가? 각 term의 모든 posting list를 가져와서 교집합을 하던가 합집합을 하던가… 아니면 이것들 후보 문서 모두를 vector space 모델이나 확률모델을 적용해서 가져오는 방법이 있겠다.하지만 위의 방법은 너무 복잡도가 크고, 이 문제때문에 검색 시간이 많이 걸릴것이다. 그래서 Query Process분야에서는 얼마나 빨리 가져오는 문제가 [...]