Geri Dön

Efficiency and effectiveness of xml keyword search using full element index

Tam eleman indeksi kullanarak xml anahtar sözcük aramanın verimlilik ve etkililiği

  1. Tez No: 275105
  2. Yazar: DUYGU ATILGAN
  3. Danışmanlar: PROF. DR. ÖZGÜR ULUSOY
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgi ve Belge Yönetimi, Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Information and Records Management, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2010
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 82

Özet

Son yıllarda akademide ve endüstride, XML veritabanları ve belge derlemlerinde anahtar sözcük aramak için çeşitli teknikler önerilmiştir. Bu tekniklerin pek çoğunda kullanılan veri yapısı, dünya çapında ağ (WWW) gibi büyük metin verileri üzerinde anahtar sözcük aramada en gelişmiş teknik olan ters indekstir. Bir tam eleman indeksi her bir XML elemanını, metni, kendisinin doğrudan içeriği ve torunlarının içeriklerinden oluşan ayrı bir belge olarak düşünür ve indeksler. Tam eleman indekse yöneltilen önemli bir eleştiri (XML belgelerinin iç içe yapısından dolayı) yüksek derecede fazlalık içermesidir. Bu durum tam eleman indeksin büyük ölçekli XML erişimi durumlarında kullanımını azaltır.Bu tezde XML anahtar sözcük arama için tam eleman indeksinin kullanımının verimlilik ve etkiliği araştırılmaktadır. Öncelikle, kayıpsız indeks sıkıştırma tekniklerinin tam eleman indeksinin büyüklüğünü önemli ölçüde azaltabileceği, böylece tipik bir arama motorundaki sorgu işleme stratejilerinin böyle bir indeks üzerinde verimli bir şekilde çalışabileceği öne sürülmektedir. Bir tam eleman indeksinin en önemli dezavantajı boyutunun büyüklüğüdür. Bu sorun çözüldüğü takdirde bu tip indeks kullanımının, sonuç kalitesi (etkililik) ve sorgu işleme performansını (verimlilik) son zamanlarda önerilen diğer tekniklere kıyasla geliştirebileceği gösterilmektedir. Ayrıca tam eleman indeksi kullanmak, birleşik bir taslakta sorgu sonuçlarını, sıralı belge listesi (bir arama motorunun kullanıcısının beklediği şekilde) ya da sorgu sözcüklerinin tümünü içeren eleman listesi (bir veritabanı sistemi kullanıcısının beklediği şekilde) gibi farklı formlarda oluşturmaya olanak sağlar.Bu tezin ikinci bir katkısı olarak, tam eleman indeksin büyüklüğünü daha da azaltmak için kayıplı bir yaklaşım olan statik budama tekniğinin kullanılması önerilmektedir. Bu şekilde, bir elemanın sözcüklerinin yukarı seviyelerdeki tekrarının, elemanın metinsel içeriği ve arama motorunun sıralama işlevi dikkate alınarak, uyarlanabilir bir şekilde azaltılması amaçlanmaktadır. Yani indeksteki tekrarlamaların, çıkarılmaları sonuç kalitesini azaltmadığı takdirde, ortadan kaldırılmasına çalışılmaktadır. Deneysel çalışmalarla, budanmış indeks dosyalarının çok yüksek budama seviyelerine kadar, erişim etkililiği açısından, tam eleman indeksiyle karşılaştırılabilir, hatta ondan daha iyi olduğu gösterilmektedir.Son olarak, indeks budama stratejilerinin, bir XML derleminin belge vektörlerinin büyüklüklerinin azaltılarak gruplama performansının geliştirilmesinde kullanılması önerilmektedir. Deneyler, belli durumlar için, koleksiyonun %70 kadarı budanarak, bir grup değerlendirme metriğine göre, orijinal koleksiyonla aynı kaliteyi sağlayan bir gruplama yapısı oluşturulabildiğini göstermektedir.

Özet (Çeviri)

In the last decade, both the academia and industry proposed several techniques to allow keyword search on XML databases and document collections. A common data structure employed in most of these approaches is an inverted index, which is the state-of-the-art for conducting keyword search over large volumes of textual data, such as world wide web. In particular, a full element-index considers (and indexes) each XML element as a separate document, which is formed of the text directly contained in it and the textual content of all of its descendants. A major criticism for a full element-index is the high degree of redundancy in the index (due to the nested structure of XML documents), which diminishes its usage for large-scale XML retrieval scenarios.As the first contribution of this thesis, we investigate the efficiency and effectiveness of using a full element-index for XML keyword search. First, we suggest that lossless index compression methods can significantly reduce the size of a full element-index so that query processing strategies, such as those employed in a typical search engine, can efficiently operate on it. We show that once the most essential problem of a full element-index, i.e., its size, is remedied, using such an index can improve both the result quality (effectiveness) and query execution performance (efficiency) in comparison to other recently proposed techniques in the literature. Moreover, using a full element-index also allows generating query results in different forms, such as a ranked list of documents (as expected by a search engine user) or a complete list of elements that include all of the query terms (as expected by a DBMS user), in a unified framework.As a second contribution of this thesis, we propose to use a lossy approach, static index pruning, to further reduce the size of a full element-index. In this way, we aim to eliminate the repetition of an element's terms at upper levels in an adaptive manner considering the element's textual content and search system's ranking function. That is, we attempt to remove the repetitions in the index only when we expect that removal of them would not reduce the result quality. We conduct a well-crafted set of experiments and show that pruned index files are comparable or even superior to the full element-index up to very high pruning levels for various ad hoc tasks in terms of retrieval effectiveness.As a final contribution of this thesis, we propose to apply index pruning strategies to reduce the size of the document vectors in an XML collection to improve the clustering performance of the collection. Our experiments show that for certain cases, it is possible to prune up to 70% of the collection (or, more specifically, underlying document vectors) and still generate a clustering structure that yields the same quality with that of the original collection, in terms of a set of evaluation metrics.

Benzer Tezler

  1. An XML based content-based image retrieval system with MPEG-7 descriptors

    MPEG-7 tanımlayıcıları ile XML tabanlı içerik-tabanlı görüntü erişim sistemi

    SERDAR ARSLAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2004

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. ADNAN YAZICI

  2. Stroge structures for XML based multi application smart card

    XML bilgiye dayalı çok uygulamalı akıllı kartlar için veri yapıları

    ÖZGÜR ARMAĞAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2004

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Sistem ve Kontrol Mühendisliği Ana Bilim Dalı

    PROF. DR. TAFLAN GÜNDEM

  3. On modeling the single period spare parts distribution system design problem by mixed integer linear optimization

    Tek dönemli yedek parça dağıtım sistemi tasarım probleminin karışık tam sayılı doğrusal optimizasyon ile modellenmesi üzerine

    HAZAL ERCAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Endüstri ve Endüstri MühendisliğiSabancı Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. GÜVENÇ ŞAHİN

    DR. ÖĞR. ÜYESİ FATMA TEVHİDE ALTEKİN

  4. Otizm Spektrum Bozukluğu olan bireylere sosyal beceri öğretiminde sosyal öykü ve bireylerin kendi fotoğraflarının kullanıldığı sosyal öykü uygulamalarının etkililik ve verimliliklerinin karşılaştırılması

    The comparison of efficiency and effectiveness of social story and social story in which individuals own photos are used in social skills teaching to the individuals that have Autism Spectrum Disorder

    ESRA KORKMAZER ÖZDEMİR

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Eğitim ve ÖğretimBiruni Üniversitesi

    Özel Eğitim Ana Bilim Dalı

    PROF. DR. ADEVİYE TUĞBA TUNCER

  5. Otizm spektrum bozukluğu olan bireylere sosyal beceri kazandırmada sosyal öykü ve müzikli sosyal öykü uygulamalarının etkililik ve verimliliklerinin karşılaştırılması

    The comparison of the efficiency and effectiveness of social history and musical social story on social skill development of autism spectrum disordered individual

    BANU GEBOLOĞLU

    Doktora

    Türkçe

    Türkçe

    2016

    Eğitim ve ÖğretimNecmettin Erbakan Üniversitesi

    Güzel Sanatlar Eğitimi Ana Bilim Dalı

    DOÇ. DR. HÜSEYİN SERDAR ÇAKIRER

    YRD. DOÇ. YAHYA ÇIKILI