İnterpolasyonlu ikili arama algoritmasının yeni varyantları
New variants of interpolated binary search algorithm
- Tez No: 1022303
- Danışmanlar: DR. ÖĞR. ÜYESİ AYŞE NUR ALTINTAŞ TANKÜL, DOÇ. DR. BURHAN SELÇUK
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2026
- Dil: Türkçe
- Üniversite: Karabük Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Sıralı veri kümeleri üzerinde arama, veri tabanı sistemleri, gömülü sistemler ve daha pek çok alanda uygulama performansını doğrudan belirlemektedir. İkili arama (BS) dağılımdan bağımsız O(log n) garantisi sunarken, enterpolasyon araması (IS) düzgün dağılımlarda O(log log n)'ye ulaşmakta, ancak düzgün olmayan dağılımlarda O(n)'e kadar performansı gerilemektedir. Bu çalışmada, mevcut hibrit algoritmaların pivot seçim kırılganlıklarını gidermek amacıyla dört yeni algoritma önerilmiştir: RIS, RIBS₁, RIBS₂ ve NIBS. Algoritmalar; normal, üstel ve düzgün dağılımlar altında 180 farklı veri seti üzerinde Python-C-Python karma mimarisiyle, 1000×1000 tekrarlı ölçüm protokolüyle değerlendirilmiştir. NIBS, normal dağılımında ortalama 12.5 iterasyonla BS'nin yarısı kadar döngü gerektirmiş; üstel dağılımda 4.8 iterasyonla IBS'nin üçte biri kadar iterasyonla hedefe ulaşmıştır. RIBS₂ ise düzgün dağılımda 2.7 iterasyonla tüm algoritmalar arasında en düşük döngü sayısına ulaşmıştır. Elde edilen bulgular, algoritma tercihinin veri dağılımının yapısal özelliklerine dayandırılması gerekliliğini gözler önüne sermektedir.
Özet (Çeviri)
Searching over ordered datasets directly determines application performance in database systems, embedded systems, and numerous other domains. Binary search (BS) provides a distribution-independent guarantee of O(log n), while interpolation search (IS) achieves O(log log n) on uniform distributions but degrades to O(n) on non-uniform ones. In this study, four novel algorithms; RIS, RIBS₁, RIBS₂, and NIBS are proposed to address the pivot selection vulnerabilities of existing hybrid algorithms. The algorithms were evaluated on 180 distinct datasets under normal, exponential, and uniform distributions using a Python-C-Python hybrid architecture with a 1000×1000 repeated measurement protocol. NIBS required an average of 12.5 iterations under the normal distribution, demanding half the number of iterations compared to BS, and dropped to 4.8 iterations under the exponential distribution reducing to one-third of IBS. RIBS₂ achieved the lowest iteration count among all algorithms under the uniform distribution, completing searches in an average of 2.7 iterations. The findings demonstrate that algorithm selection must be grounded in the structural characteristics of the underlying data distribution.
Benzer Tezler
- Fast face detection and recognition on graphics processing units
Grafik işlemciler üzerinde hızlı yüz saptama ve tanıma
SALİH CİHAN TEK
Yüksek Lisans
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. MUHİTTİN GÖKMEN
- An investigation on coastal sea level changes of Blacksea using tide-gauge and satellite altimetry data
Karadeniz'de mareograf istasyonu ve uydu altimetre verileri ile kıyı deniz seviyesi değişimlerinin araştırılması üzerine bir inceleme
MOHSEN FEIZABADI
Yüksek Lisans
İngilizce
2016
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiGeomatik Mühendisliği Ana Bilim Dalı
DOÇ. DR. BİHTER EROL
- Gerçek zaman uygulamaları için görüntü bölütleme yöntemlerinin geliştirilmesi
Improvement of image segmentation methods for real time applications
YUNUS KOÇ
Yüksek Lisans
Türkçe
2019
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. TAMER ÖLMEZ
- Near-infrared image based face recognition
Yakın kızılötesi görüntü tabanlı yüz tanıma
NİL SERİ
Yüksek Lisans
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. MUHİTTİN GÖKMEN
- Super resolution methods for remote sensing images
Uzaktan algılama görüntüleri için süper çözünürlük metotları
ÇAĞLAYAN TUNA
Yüksek Lisans
İngilizce
2017
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesiİletişim Sistemleri Ana Bilim Dalı
PROF. DR. ELİF SERTEL