Improving posting lists intersection with skip pointers

Abstract

Dijital belge sayısındaki hızlı artış dijital dünyayı birçok zorlukla karşı karşıya bırakmaktadır. Bu artışın yarattığı ana zorluklardan birisi makul bir süre içerisinde bir arama sorgusuyla ilgili belgeleri bulmaktır. Tüm belgelerde belirli bir kelimeyi bulmak için gereken süreyi kısaltma amacıyla ters indeksleme kullanılmaktadır. Burada indeksleme belgeler yerine sözcüklere dayalıdır, bu nedenle her kelime bu kelimeyi içeren bir belge kimlik numarası listesi ile indekslenir. Her belge numarası gönderi olarak adlandırılmakta ve bu gönderiler gönderi listeleri olarak bilinen listelerde sıralı bir şekilde saklanmaktadır. Bir arama sorgusu yürütüldüğünde, arama sorgusunun sonucu olarak bütün gönderi listelerinde mevcut olan belgeleri bulmak için ilgili gönderi listeleri arasında kesişimler bulunarak bu kelimeler ile ilgili gönderi listeleri getirilir. Gönderi listeleri sıralı bir şekilde saklandığı için, kesişme işleminin yapıldığı algoritma tarafından atılacak bir sonraki adıma karar vermek ve kesişim sürecini hızlandırmak için gerekli değeri uzak bir konumdaki değer ile karşılaştırarak arama sırasında atlama işaretçileri kullanılarak belirli pozisyonlar atlanmaktadır. Bu atlama işaretçilerinin gönderi listelerine dağılımı kesiştirme işlemini hızlandırmak için önemli bir faktördür ve bir yöntemden diğerine farklılık arz etmektedir. Bir yandan makul yürütme süresi korunurken diğer yandan daha uzun gönderi listelerinin işlenebilmesi için mevcut yöntemlerin uygulamalarının geliştirilmesi gerekmektedir.Bu çalışmada, gittikçe artan doküman sayısını karşılamak için, kesiştirme süreci için daha hızlı sonuç elde etmek amacıyla atlama işaretçilerine dayanan yeni bir yöntem önerilmiştir. Önerilen yöntem, farklı senaryolar kullanılarak test edilmiş ve mevcut yöntemlerle karşılaştırılm. Yürütülen deneylerin sonuçları, farklı boyutlardaki gönderi listeleri arasındaki kesişimleri bulmak için gereken karşılaştırma sayısında, dolayısıyla yürütme süresinde önemli oranda bir gelişme göstermiştir.Anahtar Kelimeler: Bilgi alımı ; Atlama işaretçileri; Atlama listeleri; Ters indeksleme.

The rapid accumulative growth in the number of digital documents imposes many challenges to the digital world. One of the main challenges created by this growth is to find documents related to a search query in a reasonable execution time. To reduce the time required to search for a certain word in all documents, inverted indexing is used, where the indexing is based on words instead of documents, so that, each word is indexed with a list of documents identification numbers that contain this word. Each document number is known as postings and these postings are stored in an ordered manner in lists known as postings lists. When a search query is executed, the postings lists related to these words are retrieved in order to find documents that exist in all postings lists, as results of the search query, by finding intersections between related postings lists. As postings lists are stored in an ordered manner, certain positions are skipped during search using skip pointers, to accelerate the intersection process, by comparing the required value to a value in a remote position in order to decide the next step taken by the intersecting algorithm. The distribution of these skip pointers over the postings lists is a key factor to accelerate the intersecting process and is different from one method to another. The performance of the existing methods needs to be improved in order to process longer postings lists while maintaining reasonable execution time.In this study, a novel method based on skip pointer is proposed to provide faster results for the intersecting process, in order to meet up the growing number of documents. The proposed method is tested using different scenarios, and compared to the existing methods. The results of the conducted experiments show significant improvement in the number of comparisons, hence execution time, required to find intersections between postings lists of different sizes.Keywords: Information retrieval; Skip pointers; Skip lists; Inverted indexing.