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.

Continue reading →