Improving posting lists intersection with skip pointers
Atlama işaretçileriyle kesişen mesaj gönderi listelerini iyileştirme
- Tez No: 483793
- Danışmanlar: YRD. DOÇ. DR. SHADI ALSHEHABI, YRD. DOÇ. DR. ABDÜL KADİR GÖRÜR
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Bilgi alımı, Atlama işaretçileri, Atlama listeleri, Ters indeksleme, Information retrieval, Skip pointers, Skip lists, Inverted indexing
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Türk Hava Kurumu Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 54
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- VTAM'in incelenmesi ve bir VTAM uygulaması
VTAM application programming
AHMET TEKELİOĞLU
Yüksek Lisans
Türkçe
1994
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiPROF.DR. EMRE HARMANCI
- Konut mutfaklarının mekansal performansını etkileyen etmenler ve iç ortam hava kalitesi
Factors affecting the spatial performance of residential kitchens and indoor air quality
MELTEM EREN
Yüksek Lisans
Türkçe
2023
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. HÜLYA KUŞ
- Sinop, Samsun ve Trabzon'da kolera salgınları, Karantina Teşkilatı ve kamu sağlığı hizmetleri (1876-1914)
Cholera epidemics, Quarantine Organisation and public health services in Sinop, Samsun and Trabzon (1876-1914)
İSMAİL YAŞAYANLAR
- Learners' reflections on experiencing augmented reality in the English classroom at tertiary level
Yükseköğrenim düzeyinde İngilizce sınıfında artırılmış gerçeklik deneyimlerine yönelik öğrenci yansıtmaları
OZAN VARLI
Doktora
İngilizce
2022
Eğitim ve Öğretimİstanbul Üniversitesi-CerrahpaşaYabancı Diller Eğitimi Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ÖZLEM ETUŞ
- Yaşlı bakım merkezinde uygulanan birey merkezli demans bakım programının çalışanların bakım yaklaşımları ve bireylerin psikolojik iyilik hali üzerine etkisi
Implementation of person-centered dementia care program in nursing homes and its effects on health care staff's care approaches and psychological well-being of residents
SEDA GÜNEY