Metrik uzaylarda indeksleme için dinamik ve adaptif yeni bir yöntem

ABSTRACTA NEW DYNAMIC AND ADAPTIVE SCHEME FORINDEXING IN METRIC SPACESUmut TOSUNM.S. in Computer EngineeringSupervisor: Dr. Cengiz Celikşü ur UlusoyCo-Supervisor: Prof. Dr. OzgüAugust, 2007Computer Science applications are often concerned with efficient storage andretrieval of data. Well defined structure of traditional databases help to accessrequired query objects effectively using the Relational Database paradigm. How-ever, in recent times, we are faced with the challenges of dealing with unstruc-tured and complex data such as images, video, sound clips and text documents.Multimedia Information Retrieval, Data Mining, Pattern Recognition, MachineLearning, Computer Vision and Biomedical Databases are examples of the fieldsthat require efficient management of complex data. Complex, unstructured typeof data often cannot be broken down into well-defined components, and exactmatching cannot be applied for defining queries. Instead, the notion of similaritysearch is used where a query or prototype object is provided by the user and thedatabase retrieves the objects that are similar.One popular approach for similarity searching is to approximate the relation-ship between database objects by mapping them into a vector space. There arewell-known indexing methods in literature that support similarity queries in vec-tor spaces, however, it has been shown that these methods are ineffective for highdimensional data. Another approach is to use Metric Spaces model for indexing.Metric spaces are defined by a distance function that has the triangular inequalityproperty. Since there are no assumptions about the structure of the data itself,they constitute a higher level abstraction and thus have more applicability. Theyhave also been shown to perform better in higher dimensions.A lot of the previous work in metric spaces have concentrated on static meth-ods that do not allow new insertions once the index structure has been initialized.ivvM-Tree, Slim-Tree, DF-Tree, Omni are some of the popular dynamic structures.These methods can grow incrementally by splitting overflowed nodes and addingnew levels to the tree very much like the B-tree variants. Unfortunately, they havebeen shown to perform very poorly compared to flat structures such as AESA,LAESA, Spaghettis and Kvp that use a fixed set of global pivots. The distancesbetween the query object and the pivots are computed to eliminate some portionof the database from consideration. The number of pivots can be easily increasedto provide more selectivity, thus better query performance. However, there is anoptimum number of pivots for a given query radius, and using too many pivotsincreases the costs of queries and the initialization of the index. Recently, SparseSpatial Selection(SSS) was introduced as a LAESA variant that allows insertionsof new database objects and dynamically promotes some of the new objects aspivots.In this thesis, we argue that SSS has fundamental problems that results inpoor query performance for clustered or otherwise skewed distributions. Realdatasets have often been observed to show such characteristics. We show thatSSS has been optimized to work for a symmetrical, balanced distribution andfor a specific radius value. Our first main contribution is offering a new pivotpromotion scheme that can perform robustly for clustered or skewed distributions.Our second contribution is proposing new methods that solve the problem ofdetermining the right number of pivots for different query radius values. Weshow that our new indexing scheme performs significantly better than tree-baseddynamic structures while having lower insertion costs. We also show that ourstructure adapts to changes in the database population in a superior way.Keywords: Metric Space, Metric Access Methods, Kvp, Hkvp, EcKvp, M-Tree,Slim-Tree, DF-Tree, Pivot, Distance Computation.