Effective and efficient similarity search in databases

Given a large set of records in a database and a query record, similarity search aims to find all records sufficiently similar to the query record. To solve this problem, two main aspects need to be considered: First, to perform effective search, the set of relevant records is defined using a similarity measure. Second, an efficient access method is to be found that performs only few database accesses and comparisons using the similarity measure. This thesis solves both aspects with an emphasis on the latter. In the first part of this thesis, a frequency-aware similarity measure is introduced. Compared record pairs are partitioned according to frequencies of attribute values. For each partition, a different similarity measure is created: machine learning techniques combine a set of base similarity measures into an overall similarity measure. After that, a similarity index for string attributes is proposed, the State Set Index (SSI), which is based on a trie (prefix tree) that is interpreted as a nondeterministic finite automaton. For processing range queries, the notion of query plans is introduced in this thesis to describe which similarity indexes to access and which thresholds to apply. The query result should be as complete as possible under some cost threshold. Two query planning variants are introduced: (1) Static planning selects a plan at compile time that is used for all queries. (2) Query-specific planning selects a different plan for each query. For answering top-k queries, the Bulk Sorted Access Algorithm (BSA) is introduced, which retrieves large chunks of records from the similarity indexes using fixed thresholds, and which focuses its efforts on records that are ranked high in more than one attribute and thus promising candidates. The described components form a complete similarity search system. Based on prototypical implementations, this thesis shows comparative evaluation results for all proposed approaches on different real-world data sets, one of which is a large person data set from a German credit rating agency.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Potsdam

Year

2013

Author dc:creator

• Lange, Dustin

Contributors dc:contributor

• Naumann, Felix

• Datenbanken
• Ähnlichkeitssuche
• Suchverfahren
• Ähnlichkeitsmaße
• Indexstrukturen
• Databases
• Similarity Search
• Search Algorithms
• Similarity Measures
• Index Structures

Statement dc:rights

• Creative Commons - Namensnennung, Nicht kommerziell, Weitergabe zu gleichen Bedingungen 3.0 Deutschland

Repository record source_url

https://publishup.uni-potsdam.de/frontdoor/index/index/docId/6386

OAI identifier oai:identifier

oai:kobv.de-opus4-uni-potsdam:6386