Langkah-langkah dasar dalam membangun sebuah non-positional index antara lain sebagai berikut. Pertama, kita membuat sebuah pass melewati document collection dengan membangun semua pasangan term-docID. Kemudian pasangan-pasangan tersebut diurutkan dengan term sebagai key yang dominan dan docID sebagai secondary key. Terakhir, docID untuk setiap term diatur ke dalam sebuah daftar postings dan dilakukan perhitungan statistik term dan document frequency. Untuk document collection yang ukurannya kecil, langkah-langkah tadi bisa dilakukan di memori. Pada pembahasan ini akan dijelaskan metode-metode untuk document collection berukuran besar yang membutuhkan penggunaan secondary storage.

Untuk membuat pembangunan index lebih efisien, term direpresentasikan sebagai termID yang mana masing-masing termID adalah sebuah nomor seri yang unik. Pemetaan dari term ke termID bisa dibangun secara on the fly sementara dilakukan pemrosesan terhadap document collection, dalam sebuah pendekatan pemrosesan dengan 2 kali pass, dimana pada pass pertama dikompilasi vocabulary-nya dan kemudian pada pass kedua dibangun inverted index. Algoritma pembangunan index yang akan dibahas pada tugas ini semua melakukan single pass pada data.

Kita akan menggunakan dokumen Reuters-RCV1 yang data-datanya ada pada table di atas sebagai model collection, dokumen ini merupakan dokumen teks yang ukuran kasarnya 1 GB. Dokumen Reuters-RCV1 mempunyai 100 juta token. Proses pengumpulan pasangan termID-docID menggunakan masing-masing 4 byte untuk termID dan docID akan membutuhkan storage sebesar 0.8 GB. Bisa dilihat bahwa bagaimana document collection tersebut akan memepengaruhi memori, bahkan untuk komputer dalam skala besar, jika kita mencoba untuk mengurutkan pasangan termID-docID di memori.

Dengan adanya keterbatasan memori, perlu digunakan suatu algoritma pengurutan secara eksternal (di luar memori utama), contohnya menggunakan disk. Untuk kecepatan yang dapat diterima, pusat kebutuhan untuk algoritma tersebut adalah meminimalkan jumlah random disk seek selama proses pengurutan. Salah satu solusinya adalah blocked sort-based indexing algorithm (BSBI). Langkah-langkah BSBI :

1. segmentasi koleksi menjadi bagian-bagian dengan ukuran yang sama
2. urutkan pasangan termID-docID dari tiap-tiap bagian di memori
3. simpan hasil pengurutan intermediate pada disk
4. gabung semua hasil pengurutan intermediate ke final index

Algoritma ini menguraikan dokumen-dokumen menjadi pasangan termID-docID dan mengakumulasikan pasangan-pasangan tersebut di memori hingga sebuah blok berukuran tetap penuh. Ukuran blok dipilih untuk menyesuaikan ke memori untuk mengizinkan pengurutan cepat di dalam memori. Blok kemudian di-invert dan ditulis ke disk. Proses pembalikan (inversion) terdiri atas dua langkah. Pertama, mengurutkan pasangan termID-docID. Kemudian mengumpulkan semua pasangan termID-docID dengan termID yang sama ke dalam sebuah daftar postings, dimana sebuah posting adalah sebuah docID. Hasilnya, sebuah inverted index untuk blok yang baru saja dibaca, kemudian ditulis ke disk. Jika diaplikasikan pada contoh dokumen Reuters-RCV1 dan diasumsikan kita bisa mencocokkan 10 juta pasangan termID-docID ke memori, hasilnya digunakan 10 blok, masing-masing sebuah inverted index dari satu bagian dari koleksi.

Pada langkah terakhir, algoritma ini secara bersamaan menggabungkan kesepuluh blok menjadi sebuah index gabungan yang besar. Untuk melakukan penggabungan, semua file blok dibuka secara bersamaan dan mempertahankan read buffers berukuran kecil untuk 10 blok yang dibaca dan sebuah write buffer untuk final index gabungan yang ditulis. Pada setiap iterasi, dipilih termID terendah yang belum diproses menggunakan antrian prioritas atau struktur data yang serupa. Seluruh daftar postings untuk termID ini dibaca, digabung dan daftar gabungan ditulis kembali ke disk. Setiap read buffer diisi ulang dari file-nya jika diperlukan.

Kompleksitas waktu BSBI adalah ?(T log T) karena langkah dengan kompleksitas waktu tertinggi adalah pengurutan dan T adalah batas atas jumlah item yang harus diurutkan (jumlah pasangan termID-docID). Namun, waktu peng-index-an aktual biasanya didominasi oleh waktu yang diperlukan untuk mengurai dokumen dan untuk melakukan penggabungan akhir final index.

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