1 Introduction

  웹 검색엔진들의 탄생은 전통적인 inverted index 기술들에 대해 새로운 도전을 초래했다. 특히 eager (또는 term-at-a-time) query evaluation은 lazy (또는 document-at-a-time) query evaluation으로 바뀌게 되었다. 첫번째 사례로 쿼리 안의 단어 중의 하나의 inverted list가 먼저 계산된다. (보통, 가장 빈도가 적은 단어를 선택한다[4].) 그리고 다른 list들과 합쳐지거나 걸러내진다. 대신 lazy evaluation을 하면 쿼리를 만족하는 각 document를 차례차례로 검색하면서 inverted list들이 병렬적으로 스캔된다.

  Lazy evaluation은 여러 inverted list들이 동시에 지속적으로 유지되어야 한다. 이 operation을 효과적으로 수행하기 위해 skip method는 호출한 사람이 주어진 포인터보다 크거나 같은 첫 문서의 포인터에 빠르게 도달하게 해주는 것이 가능해야 한다. 이 문제에 대한 고전적인 해결책[1]은 inverted list가 그 안에 skip에 대한 정보를 가지고 있어야 한다는 것이다. 일정한 간격마다 추가적으로 약간의 정보(문서의 포인터와 그 포인터에 도달하기위해 건너뛰어야 하는 bit의 수로 이루어진 한쌍의 정보)가 skip을 표현하는 것이다. [1]에 나오는 skipping의 분석은 스킵이 단어가 나오는 주기의 제곱근 간격을 두게 되어야 하고 한 레벨의 skip이면 대부분 충분하다고 결론을 내린다.

  그렇지만 위에서 한 분석은 두가지 중요한 한계점을 가지고 있다.
1. 위치에 대해서 전혀 고려하지 않는다. 즉, 문서안에서 단어가 나오는 정확한 위치의 기술이나 application에 엮인 추가적인 데이터를 우습게 보고 있다.
2. 기본으로 eager evaluation을 기반으로 하고 그 결과가 lazy evaluation으로 확장될 수 없다. 
  이런 이유로 우리는 granularity의 수준이 매우 높은 self-index inverted list의 일반적인 method를 이야기할 것이다. 이 method는 문서 record 구조나 inverted index의 사용 패턴에 어떤 가정도 하지 않는다. skip은 주어진 포인터(또는 주어진 포인터의 양)에 의해 항상 여러 low-level read, bit-level skip과 함께 수행될 수 있다. 그럼에도 불구하고 index의 크기는 몇 퍼센트 정도밖에 증가하지 않는다.

  우리 기술은 특히 in-memory index에 도움이 된다. 즉 index를 RAM에서 유지하기 위해 문서검색 대부분의 시간을 inverted list의 scanning과 decoding에 쓰고 동시에 압축률을 높이는 것이다. 이 문서에 기록된 모든 결과는 MG4J에서 구현되었고 다음 주소에서 이용 가능하다.

http://mg4j.dsi.unimi.it/.

2 Perfect Embedded Skip Lists for Inverted Indices

Perfect skip lists.
  Skip list [3]는 각각의 원소들이 순서를 갖고있는 리스트이지만, 필요에따라 리스트에서 현위치보다 앞으로 건너 뛸수 있는 자료구조이다. 더 정확히 말하자면, skip  list는 x_i의 모든 item마다 x₀, x₁, . . . , x_n−1처럼 오름차순으로 아이템이 정렬된 singly linked list이고, 다음 item을 참조하는것 이외에도, item의 skip tower라고 불리는 h_i ≥ 0인 여분의 참조값을 가지고 있다. 이 타워의 t번째 참조값은 h_j ≥ t이며, 이것은 j > i를 만족하는 첫번째 item을 말한다.

  이제 perfect skip list에 대해서 이야기해보자. deterministic skip list(원래는 임의의 term으로부터 공식화된 것이다)는 inverted list에 딱 알맞다. 이제 2개의 제한용 변수를 정해보자.

1. list안의 item들의 갯수
2. tower의 최대 높이

  단순화 하기 위해, 이상적인 경우(infinite perfect skip list)에서 부터 시작하자. LSB(x)는  x가 유효한 최소 bit (Least Significant Bit of x)으로서 x는 양의 정수이고 x = 0인경우 LSB(x) = ∞ 이 된다. 그 다음, h_i=LSB(i)인 infinite perfect skip list에서 item x_i의 skip tower 높이를 정의한다. 우리는 h+1개이상의 참조값을 갖는 tower가 없고, infinite perfect skip list에 존재하는 모든 참조값들은 item이 T보다 작거나 같은 인덱스를 참조하며, 첫번재 조건도 위반하지 않을 때 주어진 높이 h와 크기 T에 관해서 완벽하다고 말한다.  

Theorem 1. T개의 item과 최대높이가 h인 perfect skip list 내 원소 i에서 tower의 높이는 min(h, LSB(k),MSB(T − i)) + 1, where k = i % 2h 이다. 여기서 MSB(x) 는 x의 최대 유효 bit (most significant bit of)이고,  x는 양의 정수값을 갖는다. 만일 x가 0이면 MSB(x) = −1. 특히 i < T - T % 2h 인 경우 타워의 높이는 min(LSB(k),MSB(T mod 2h−k))+1 = min(h,LSB(k))+1

  inverted list의 모든 포인터를 직접 addressing하면 관리하기 힘든 index가 만들어진다. 따라서, q중에 1개의 item만 indexing한다. 여기서 q는 item의 최소 addressable block을 나타내는 고정 값(quantum)이다. Figure 1 은 perfect skip list의 예이다.

3 Inherited Towers

  이전 섹션에서 말한바와 같이, tower의 정상으로 갈수록 많이 분산되고 압축하기도 힘들어 진다. 이상하게 보일지 모르지만 우리의 다음 목표는 tower의 정상에 모두 기록하는 걸 피하는 것이다. inverted list를 선형적으로 scanning할 때, search fingers[2]처럼 지금까지 모은 모든 "skip knowledge"(fig 2)로 상속된 tower를 유지하는 것이 가능하다. 

  만일 defective한 블럭이 있다면 계승된 entry들이 높이 h까지 도달하지 못할지도 모름에 주의해라(Fig 1의 오른쪽 부분). 보편성을 위해서 q = 1이라 하자.

Theorem 2. 상속받은 tower에서 길이 L인 defective block에 대해 가장 높은 유효 entry는 이다. 이때 는 bit-by-bit exclusive or 이다.

위의 계산 결과는 우리에게 다음과 같은 것을 알려준다. 최고 높이가 h'인  nontruncated tower는 top entry와 동일한 h'+1 level의 entry를 상속한다. 결과적으로 만일 list가 처음부터 travers되면, nontruncated tower의 top entry는 생략할 수 있다. top entry의 생략은 기록되는 entry의 수를 반으로 줄이고 우리가 절(paragraph)의 처음에서 봤듯이, skip structure의 크기도 한층 줄인다.


Experimental Data and Conclusions
  우리는 약 50GiB정도의 parse된 text(index는 count와 occurrence를 포함한다.)을 가지고 있는 .uk 도메인으로부터 13Mpage의 일부 스냅샷을 가져와서 그것에 대한 indexing 통계를 모았다. document의 crawl order에서 보여주듯이 스냅샷 분포가 매우 치우치게 된다. 임의의 높이를 갖는 tower에 embeded perfect skip list를 더하면 q = 32일때 크기가 2.3%(317MiB) 증가하고, q = 64일때 1.23%증가한다. 제곱근 간격으로 인덱싱 할 경우 0.85% 증가한다. 동일한 skip 구조체를 pointer skip에 대해 Gaussian Golomb code대신 γ나 δ를 이용해서 압축하면 각각 42%와 18.2%의 pointer skip크기의 증가를 초래한다.

  물론 속도가 우리 주 관심사이다. skip list에 추가적인 기록으로 인한 overhead는 선형 scan의 수행 시간을 5%이상 증가시키지 않는다(평균 0.5%). 반면 일반적인 or를 이용한 형태에서 복합적으로 생성된 query에 대해서는 제곱근 간격으로 했던것 보다 20 ~ 300%의 속도 증가를 보인다.

References

1. Alistair Moffat and Justin Zobel. Self-indexing inverted files for fast text retrieval. ACM Trans. Inf. Syst., 14(4):349–379, 1996.
2. William Pugh. A skip list cookbook. Technical report UMIACS-TR-89-72.1, Univ. of Maryland Institute for Advanced Computer Studies, College Park, College Park, MD, USA, 1990.
3. William Pugh. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM, 33(6):668–676, 1990.
4. Ian H. Witten, Alistair Moffat, and Timothy C. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann Publishers, Los Altos, CA 94022, USA, second edition, 1999.