Inverted Indexing
2 minute read

Background

Information retrieval 은 주어진 query 에 대해 relevant document 을 찾는 과정으로 정의된다. 이때 text document 는 단어로 이루어져있기 때문에 우리는 text 를 bag of words 로 볼 수 있다. 이 관점을 이용하면 document 와 term 을 하나의 행렬로 표현할 수 있다.

td

이 term-document matrix $X$ 의 중요한 특징은 대부분의 값이 0으로 굉장히 sparse 하다는 것이다.

Query 도 vocab 의 벡터로 표현할 수 있는데, 전체 vocabulary 의 사이즈에 비해 query 는 주로 몇개의 단어만으로 이루어져있기 때문에 query vector 도 굉장히 sparse 하다.

이를 retrieval 에 활용하려면 term-document matrix $X$ 와 query vector $q$ 을 곱한다. 이를 통해 각 document 와 query 의 연관도 / 유사도 점수를 구할 수 있다.

xq

여기서 연산의 복잡도를 고려해보자. $y = Xq$ 를 계산하기 위해서는 $O(mn)$ 만큼의 시간 복잡도와 $O(mn)$ 의 공간 복잡도($n\times m$ 차원의 행렬 $X$ 를 저장해둬야함)가 소요된다 (m = 문서 벡터 하나의 크기이자 쿼리 벡터의 크기, n = 문서의 수).

이때 $X$ 와 $q$ 가 둘다 sparse 하다는 점을 생각해보면 0 값을 다루는데에 대부분의 시간, 공간이 소요되는 셈이다.

Inverted Indexing

이 문제를 해결하기 위해 도입된 것이 inverted indexing 이다. Inverted indexing 을 잘 활용하면 저장공간을 더 효율적으로 사용할 수 있고 연산 또한 scalable 해진다.

Inverted indexing 은 아래의 꼴로 각 term 에 대해 document 의 index 를 만드는 것이다.

termID: ((docID, weight), (docID, weight), …, (docID, weight))

이때 주어진 query 가 등장한 document 를 알기 위해서는 전체 term 중에서 query term 을 찾기만 하면 되기 때문에 constant time 이 소요된다. 소요 시간은 collection 의 크기와도 무관하다.

그 다음 주어진 query 가 등장한 document 의 list 에 대해 연관성 점수를 매겨야한한다. Cosine similarity 로 점수를 계산한다고 해보자.

Time & Space Savings

Inverted indexing 을 사용했을 때 공간, 시간복잡도를 얼마나 절약할 수 있는지 보자.

Space Saving

아까 inverted indexing 을 사용하지 않았을 때는 공간복잡도는 $O(mn)$ 이었다. ($mn$: term-document matrix 의 크기)

여기서 inverted indexing 을 사용하면 공간 복잡도는 $O(ln)$ 으로 줄어든다. (Term, document 의 bipartite graph 를 고려. term 이 document 에 등장했을때 두 node 간의 connection 이 생긴다고 정의했을때 총 connection 의 수는 (document 의 수)*(각 doc 이 가진 unique word 의 수), 즉 $n \times l$ 이 되기 때문)

Time Saving

Inverted indexing 을 사용하지 않았을 때는 $O(mn)$ 이었다.

Inverted indexing 을 사용하면 time complexity 는 $O(\frac{kln}{m})$ 으로 줄어든다.

먼저 하나의 document 가 평균적으로 $l$ 개의 unique term 을 가지고 있으므로 bipartite graph 에서 connection 의 수는 $ln$ 개가 된다. 이때 vocabulary 내 하나의 단어가 평균적으로 몇개의 document 와 connection 을 가지고 있는지를 계산하려면 $\frac{ln}{m}$ 를 구하면 된다. 마지막으로 아래의 식에 나와있듯이 이 계산을 query 의 단어수(평균적으로 $k$개)만큼 해주면 되기 때문에 총 계산량은 $\frac{kln}{m}$ 이 된다.

정리하자면 inverted index 를 사용할 경우 공간복잡도는 $\dfrac{m}{l}$ 만큼, 시간복잡도는 $\dfrac{m^2}{kl}$ 만큼을 절약할 수 있게 된다. Vocabulary 의 크기 $m$ 이 커질수록 inverted index 가 가져오는 효율성도 커진다.

Conclusion

이처럼 inverted indexing 은 $Xq$ 를 계산해야하는데 $X$ 가 굉장히 크고 sparse 한 경우에 유용하다.

하지만 새로운 document 가 빈번하게 추가된다면 $X$ 를 매번 업데이트해야하기 때문에 그때는 오히려 비효율적이다.

Recent Posts

Matrix Calculus
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Deep Contextualized Word Representations
Pretraining-Based Natural Language Generation for Text Summarization
Style Transfer from Non-Parallel Text by Cross-Alignment