Geri Dön

Assignment query and its implementation in moving object databases

Hareketli nesne veritabanı sistemleri için atama operatörü ve uygulaması

  1. Tez No: 181292
  2. Yazar: ALİ RIZA KONAN
  3. Danışmanlar: PROF. DR. TAFLAN İMRE GÜNDEM
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2006
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 69

Özet

Kablosuz iletişim alanında olduğu kadar konum bulma teknolojilerinde de yaşananhızlı gelişmeler sayesinde, hareketli nesneler kavramı gittikçe önem kazanmaktadır.Hareketli Nesne Veritabanı (Moving Object Databases - MOD) sistemleri, birçok alandagiderek artan bir ilgiye sahip olan konum tabanlı hizmetlerde yaygın olarak kullanılmayabaşlanmıştır. Literatürde, hareketli nesne veritabanı sistemlerine ilişkin en yakın komşuyubulma, karşıt en yakın komşuyu bulma, k - en yakın komşuyu bulma gibi birçok sorgulamaçeşidi mevcuttur. Bunlardan farklı olarak, bu tez çalışmasında, hareketli nesne veritabanısistemleri için bir sorgulama tipi olarak yeni bir operatör önerilmiş ve olası bir uygulamasıüzerinde durulmuştur. Önerilen atama operatörünün amacı, literatürde ağırlıklı iki parçalıeşleştirme olarak da bilinen atama problemini çözmektir. Özetle, amaç, iki nesne kümesiarasında maliyeti en aza indirecek olan kusursuz atamayı bulabilmektir. Örneğin, bir grupmüşterinin bir grup taksiye en az maliyetli olacak şekilde atanması gibi.Hareketli nesne veritabanı sistemi üzerinde çalışıyor olmamız dolayısıyla, problemeverimli bir çözüm üretebilmek için kullanıcı sorgularına gerçek zamana yakın şekildecevap verilmesi gerekmektedir. Ancak, en az maliyetli genel iki parçalı eşleştirmeprobleminin zaman karmaşıklığının O(N^3) olduğu bilinmektedir. Bu yüzden, problemeilişkin bilinen klasik çözüm yöntemlerinin hareketli nesne veritabanı sistemlerindekullanılması mantıksız olacaktır. Bu çalışmada, mantıklı bir zaman dilimi içerisinde yanıtverebilecek bir atama operatörü önerilmiştir. Ayrıca, hareketli nesne veritabanısistemlerindeki yoğun güncelleme yükünü karşılayabilecek bir Q+R ağaç indekslemeyapısından yararlanılmıştır. Son olarak, önerdiğimiz çözümün verimini artırabilecekperformans konuları üzerinde durularak uygulamamızın hareketli ortamdaki birkullanıcının isteklerini karşılayabilecek zaman karmaşıklığına sahip olduğunu gösterdik.

Özet (Çeviri)

With the rapid development of wireless communications as well as positioningtechnologies, the concept of moving objects has become more and more important.Moving Objects Databases (MOD) are being used in a wide range of location basedservices that are of growing interest in many application areas. In the literature, severalqueries such as nearest neighbor, reverse nearest neighbor, k-nearest neighbor, proximityqueries etc. have been considered in moving object databases. Differently from these, inthis thesis, a novel operator is proposed as a query type for moving object databases, andalso a possible implementation is presented. The aim of the proposed assignment query isto solve the assignment problem, which is also known as weighted bipartite matching. Inshort, our objective is to find a perfect matching between two set of objects in a mannerthat minimizes the total cost. For instance, a set of people is to be assigned to a set of taxi-cabs with minimal total travel time.On the other hand, working with moving object databases, we have to give near real-time responses to user queries to provide an efficient solution for the problem.Unfortunately, the problem of finding a minimal-cost matching for a general bipartitegraph is known to have an O(N^3) time algorithm. Thus, we realized that classicalsolutions having a time complexity of O(N^3) become infeasible for this type of movingobject database application. In this thesis, we propose an assignment query that responds ina reasonable time period for MOD. Furthermore, we employ a Q+Rtree index structure tocope with the high update and querying overhead of MOD. At the end, we discussed theperformance issues to improve efficiency and showed that the time complexity of ourapplication meets the needs of users in mobile environment.

Benzer Tezler

  1. Multiobjective relational data warehouse design for the cloud

    Bulut için çok amaçlı ilişkisel veri ambarı tasarımı

    TANSEL DÖKEROĞLU

    Doktora

    İngilizce

    İngilizce

    2014

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET COŞAR

  2. Deep learning based Turkish video indexing and retrieval system

    Derin öğrenmeye dayalı Türkçe video indeksleme ve bilgi getirimi sistemi

    JAWAD RASHEED

    Doktora

    İngilizce

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Sabahattin Zaim Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ AKHTAR JAMIL

  3. Optimal assignment as a location based service in outsourced databases

    Dış kaynaklı veri tabanlarında konum tabanlı servis olarak optimum atama

    AHMET SALİH BÜYÜKKAYHAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2011

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. TAFLAN İ. GÜNDEM

  4. Searching a website via spoken questions

    Sesli sorular aracılığıyla web sitesinde arama

    MESUT DURUKAL

    Yüksek Lisans

    İngilizce

    İngilizce

    2011

    Elektrik ve Elektronik MühendisliğiBoğaziçi Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. MURAT SARAÇLAR

  5. Automatic assignment of mesh keywords for articles using information retrieval system for PubMed

    PubMed bilgi geri getirim sistemini kullanarak makalelere otomatik anahtar kelime atama

    FATİH DİLMAÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ADİL ALPKOÇAK