An Index structure for moving objects in video databases

Abstract

IV ÖZET VİDEO VERİ TABANLARINDA HAREKET EDEN NESNELER İÇİN BİR İNDEKS YAPISI Tuba Yavuz Bilgisayar ve Enformatik Mühendisliği, Yüksek Lisans Tez Yöneticisi: Doç. Dr. Özgür Ulusoy Ağustos, 1999 Video veri tabanı alanında, hareketli nesnelerin modellenmesi ve çeşitli hareket sorgularının cevaplanması oldukça ilgi çeken bir araştırma konusu olmuştur. Hareket sorgularının bir çeşidinde birden fazla nesnenin hareketleri birbirlerine göre olan yerlerindeki değişiklikle ifade edilmektedir. Birbirlerine göre uzay- sal ilişkileri belirtilmiş fakat kimlikleri belirtilmemiş nesnelerden oluşan bu tip sorguların cevaplanması özel bir indeks yapısının kullanılmasını gerektirir. Bunun nedeni, böyle bir sorgunun herhangi bir indeks yapısı kullanılmaksızın cevaplanmasının hesaplama karmaşıklığı 0(N//(N - n)/) olmasıdır. Burada N veri tabanındaki nesne sayısını, n ise sorguda bulunan nesne sayısını gösterir. Biz bu çalışmada SMIST-indeks diye isimlendirdiğimiz uzaysal ve zamansal bir indeks yapısı geliştirdik. Bu indeks yapısının performansını incelediğimiz sorgu çeşidinin cevaplanması için önerilmiş bir yöntemle ([18]) karşılaştırdık. Deney sonuçları SMIST-indeks yapısının karşılaştırdığımız yöntemden daha iyi bir performans sergilediğini gösterdi. Ayrıca, yapılan deneylerde önerdiğimiz indeks yapısının artan çerçeve ve nesne sayısı karşısında disk ulaşım sayısında keskin artışlar göstermediği saptanmıştır. Anahtar kelimeler: Hareket, sorgu, video, veri tabanı, çoklu ortam, uzaysal, zamansal, uzaysal-zamansal indeksleme.

Ill ABSTRACT AN INDEX STRUCTURE FOR MOVING OBJECTS IN VIDEO DATABASES Tuba Yavuz M.S. in Computer Engineering and Information Science Supervisor: Assoc. Prof. Dr. Özgür Ulusoy August, 1999 Modeling moving objects and handling various types of motion queries are interesting topics to investigate in the area of video databases. In one type of motion queries, motion of multiple objects is specified by the changes in relative spatial positions of objects. Answering such kind of queries, that involve motion of multiple objects whose identifications are not specified, requires some type of indexing because the time complexity of processing such a query in the absence of an index structure is 0(N//(N - n)!), where N is the number of objects in the database and n is the number of objects in the query. In this work, we propose a spatio-temporal index structure, which we call.SMZST-index, and compare its performance against a similar scheme proposed in [18]. The scheme presented in [18] consists of a constraint satisfaction algorithm, which is called Join Window Reduction (JWR), combined with a spatial index structure (R*- tree). Experimental results indicate that SMIST-index outperforms the JWR algorithm. Also, SMIST-'index is shown to be scalable to increasing number of frames and objects. Key words: Motion, query, video, database, multimedia, spatial, temporal, spatio-temporal indexing.