Assignment query and its implementation in moving object databases
Hareketli nesne veritabanı sistemleri için atama operatörü ve uygulaması
- Tez No: 181292
- Danışmanlar: PROF. DR. TAFLAN İMRE GÜNDEM
- 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: 2006
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET COŞAR
- 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
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Sabahattin Zaim ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ AKHTAR JAMIL
- 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
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. TAFLAN İ. GÜNDEM
- Searching a website via spoken questions
Sesli sorular aracılığıyla web sitesinde arama
MESUT DURUKAL
Yüksek Lisans
İngilizce
2011
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. MURAT SARAÇLAR
- 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
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ADİL ALPKOÇAK