쿼리 프로세싱(Query Processing)은 검색 결과를 가져오는 프로세스이다.

그럼 어떻게 Query에 맞는 결과를 가져올 것인가?

각 term의 모든 posting list를 가져와서 교집합을 하던가 합집합을 하던가… 아니면 이것들 후보 문서 모두를 vector space 모델이나 확률모델을 적용해서 가져오는 방법이 있겠다.
하지만 위의 방법은 너무 복잡도가 크고, 이 문제때문에 검색 시간이 많이 걸릴것이다.

그래서 Query Process분야에서는 얼마나 빨리 가져오는 문제가 화두가 되었었다.
물론 얼마나 정확하게 가져오는가도 이슈이지만 일단 얼마나 빨리 가져오는것에 초점을 맞춰 보자.

위와 같이 Brute force방법으로 검색 결과를 가져오는건 정말 맘에 안든다. 그러면 어떻게 검색 결과를 가져오는게 좋을까?

여기엔 한가지 중요한 가정이 있다.

“문서 빈도수가 적은 term이 랭킹이 높은 문서에 확실이 기여한다.”

쉽게 이야기 하자면 term의 Document Frequency가 작은 term이 정확한 문서를 가져오는데 기여를 한다는 것이다. (대부분의 책에서 tf * idf 로 term의 일반적인 가중치를 결정하는것을 생각하면 이해하기 쉬울 것이다.)

바로 알고리즘으로 넘어가면

1) query term들을 빈도순으로 오름차순 정렬을 한다.
2) term (적은)빈도 순서대로 posting list를 추가하면서 원하는 문서 갯수 d개가 만들어질때까지 추가한다.
3) d개가 만들어지면 나머지 term들을 이용해 해당 텀이 존재하는 문서들의 스코어를 높여준다.(여기서 부터는 AND 연산에 가깝게 되겠다.)
4) 그렇게 만들어진 d개의 문서 집합을 리턴한다.

이렇게 하면 연산속도와 메모리 효율에 상당한 잇점을 보여줄 수 있다.

그리고 개선사항사항으로는 문서 갯수 d개의 리스트를 메모리에 유지해야 하는데 이 d개의 문서는 부분적으로 정렬이 되어 있을수도 있지만 새로운 문서가 들어왔을때 빠르게 append가 되어야 하고 doc id검색을 위해 정렬이 되어 있을 필요가 있기에 문서번호별로 파티셔닝을 해서 파티션 각각에 수집한 결과 후보문서셋의 처음과 마지막 문서번호 정보, 다음 파티션의 포인터를 유지해  해당 파티션에 append하기 편하게 구조를 취해주는 것도 좋다.
append시 문서번호가 해당 파티션의 범위에 들지 않으면 다음 파티션의 포인터를 이용해서 이동하면 될것이다.(이런방법말구 들어오는 족족 merge를 해버리면 어떨까도 생각해봤다. 문서집합으로 merge가 된다면 그렇게 속도 차이가 나지 않을거라는 생각도 되는거 같은데.. merge의 평균 복잡도 ‘O(n) * 쿼리 갯수  +++ 여기에다가 merge에 쓰이는 공간복잡도 O(n)까지 하면 좀 심각할수도있겠다.’ ㅜㅜ )

위와 같은 방법으로 문서 결과 셋을 만든 다음에 취향에 맞는 검색모델을 적용해서 Max heap sort하고 검색 페이지별로 결과를 가져오면 될 것이다.

ps. 그냥 리눅스 커널 공부하다 심심해서 써봤다. 역시 생각을 정리하기는 블로깅이 최고다.

Query Processing을 효율적으로 하자면? by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.