Blocked sort-based indexing

Pembuatan sebuah non-positional index terdiri atas beberapa langkah dasar. Pertama adalah membuat sebuah pass melalui koleksi semua pasangan term-docID. Kemudian mengurutkan pasangan, dengan term sebagai dominant key dan docID sebagai secondary key. Terakhir, mengorganisir docID untuk setiap term ke dalam posting list dan menghitung statistik, seperti frekuensi term dan dokumen. Untuk koleksi yang kecil, langkah-langkah tersebut dapat dilakukan di memori.

Agar pembuatan index lebih efisien, kita merepresentasikan term sebagai termID, dimana setiap termID adalah sebuah unique serial number. Pemetaan dari term menjadi termID dapat dibuat saat pemrosesan koleksi, atau dengan pendekatan two-pass, dimana kita menyusun kosakata pada pass pertama dan membangun inverted index pada pass yang kedua.

Sebagai contoh, kita menggunakan koleksi Reuters-RCV1 sebagai model collection. Untuk setiap dokumen pada koleksi tersebut, kita mengabaikan informasi multimedia seperti gambar, dan hanya terfokus pada teks. Statistik dari koleksi Reuters-RCV1 pada tabel berikut:

Reuters-RCV1 memiliki 100 juta tokens. Pengumpulan seluruh pasangan termID-docID pada koleksi tersebut menggunakan 4 byte, oleh karena itu untuk setiap termID dan docID membutuhkan kapasitas penyimpanan 0.8 GB. Beberapa koleksi saat ini membutuhkan media penyimpanan yang lebih besar daripada Reuters-RCV1. Jika ukuran file saat pembentukan index lebih besar dari kapasitas memori yang tersedia, maka dapat dilakukan teknik kompresi. Namun, posting file dari beberapa koleksi yang besar tidak akan cukup di memori walaupun sudah dikompresi.

Jika memori utama tidak mencukupi, diperlukan penggunaan suatu external sorting algorithm, yaitu hanya satu yang menggunakan disk. Untuk kecepatan yang dapat diterima, kebutuhan sentral dari algoritam tersebut adalah meminimalkan jumlah random disk seeks selama sorting – sequential disk membaca lebih cepat daripada seeks. Salah satu solusinya adalah blocked sort-based indexing algorithm atau BSBI. BSBI melakukan segmentasi koleksi menjadi bagian-bagian dengan ukuran yang sama, mengurutkan pasangan termID-docID dari setiap bagian di memori, menyimpan hasil pengurutan sementara pada disk, dan menggabungkan seluruh hasil sementara menjadi final index. Algoritmanya adalah sebagai berikut:

Algoritma tersebut menguraikan (parsing) dokumen menjadi pasangan-pasangan termID-docID dan mengakumulasi pasangan-pasangan tersebut di memori sampai sebuah block dari suatu ukuran yang tetap menjadi penuh (PARSENEXTBLOCK pada algoritma di atas ). Pemilihan ukuran block dilakukan agar cukup di memori, untuk mengizinkan pengurutan yang cepat di memori. Blok kemudian dibalikkan (inverted) dan ditulis ke disk. Inversi meliputi dua langkah, pertama mengurutkan pasangan-pasangan termID-docID, kemudian mengumpulkan seluruh pasangan termID-docID dengan termID yang sama pada sebuah postings list, dimana sebuah posting adalah sebuah docID yang sederhana. Hasilnya, sebuah inverted index untuk blok yang telah dibaca, kemudian ditulis di disk. Penerapan algoritma ini di Reuters-RCV1 dengan asumsi terdapat 10 juta pasangan termID-docID yang memenuhi memori, dengan 10 blok masing-masing inverted index dari satu bagian koleksi tersebut.

Gambar diatas menunjukkan penggabungan pada blocked sort-based indexing. Dua blok (”posting list to be merged”) di-load dari disk ke memori, digabungkan di memori (”merged postings lists”) dan ditulis kembali ke disk. Ditampilkan term sebagai ganti termID agar lebih mudah dibaca.

Pada langkah terakhir, algoritma ini secara simultan menggabungkan 10 blok menjadi sebuah index gabungan yang besar. Sebagai contoh dengan dua blok pada gambar di atas, digunakan di untuk menandakan dokumen ke-i dari koleksi. Untuk melakukan penggabungan, dilakukan dengan cara membuka semua block files secara simultan, dan memelihara small read buffer untuk 10 blok yang sedang dibaca dan sebuah write buffer untuk final merged index yang sedang ditulis. Pada setiap iterasi, dipilih termID terendah yang belum diproses dengan menggunakan suatu prioritas antrian atau struktur data serupa. Semua posting list untuk termID tersebut dibaca, digabungkan, dan list gabungan ditulis kembali ke disk. Setiap read buffer diisi kembali dari file tersebut jika dibutuhkan.

Kompleksitas waktu dari BSBI adalah Ө(T log T) karena langkah dengan kompleksitas waktu tertinggi adalah pengurutan dan T adalah upperbound untuk jumlah item yang harus diurutkan (dalam hal ini jumlah pasangan termID-docID). Tapi waktu indexing yang nyata pada umumnya didominasi oleh waktu untuk parsing dokumen (PARSENEXTBLOCK) dan untuk melakukan penggabungan terakhir (MERGEBLOCKS).

Referensi:

http://nlp.stanford.edu/IR-book/html/htmledition/blocked-sort-based-indexing-1.html