Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

Approximate Searching in Metric Spaces

 

Merve Sağlam
MSc. Student
Computer Engineering Department
Bilkent University

Many types of data in variety of fields such as bioinformatics, internet, multimedia objects, medicine, signal processing etc. are growing rapidly both in size and complexity. Query response time becomes one of the major problems coming with this growth. Searching is an important issue that traditional DBMS provides efficiently for structured records by using exact match pattern. In similarity search, similar objects to a given query objects are searched from the dataset. As computational cost of determining similarity between objects is noticeable part of total query time, people are motivated to offer algorithms which reduce the number of comparison among objects. In order to reduce the total running time of a query, quality/time trade-off is used, which is what has given rise to approximate similarity search. There are some approximation techniques which are able to reduce the cost of similarity search on metric space. In this study techniques in literature will be reviewed firstly. Besides these approximations, some other techniques such as "Conditional Probability Based Elimination", "Radius Shrinking based on Conditional Probability", "Lower Bound Guided Elimination" and "Hybrid Elimination" will be proposed and evaluated based on experimental results.

 

DATE: 29 March, 2010, Monday @ 16:40
PLACE: EA 409