相似資料的尋取一直都是影像資料庫及影片資料庫兩個領域裡相當重要的議題。影片資料庫延伸了影像資料庫中擷取特徵的概念，依照不同的尋取方式可以分為兩類。第一類為低階的視覺特徵(Low-level visual features)，例如物件的顏色、紋理、或是形狀等。第二類為高階的關係特徵(High-level relationship features)，例如兩兩物件間的相對距離、位置、及拓撲(topology)關係。在本篇論文中，我們以空間關係運算子描述兩兩物件在影片當中所產生的空間關係，並且將其記錄在空間關係畫面表裡，將影片尋取簡化為子字串搜尋，並且透過建立suffix trie的方式以增進影片尋取的效率，其時間複雜度僅取決於查詢影片的物件個數與長度。 Similarity retrieval is a very popular issue in both fields of image databases and video databases. Video databases extend the concept of image database by extracting features. These features can be classified as low-level visual features such as color, texture or shape and high-level relationship features such as distance, direction or topology. In this thesis, we use operators to describe spatial relationship which is formed between objects and record them in spatial relationship frame tables of x-axis and y-axis. Finally, the suffix trie is used to create an efficient index structure for each spatial relationship frame tables. The time complexity is determined by the number of objects and the length of query video only.
