WallBreaker: overcoming the wall effect in similarity search
WallBreaker: overcoming the wall effect in similarity search
复制标题
DOI：
10.1145/2457317.2457385
复制
发表时间：
2013-03
期刊：
影响因子：
--
通讯作者：
Stefan Gerdjikov;S. Mihov;Petar Mitankin;K. Schulz
中科院分区：
文献类型：
--
作者：
Stefan Gerdjikov;S. Mihov;Petar Mitankin;K. Schulz
在本文中，我们介绍了用于相似性搜索的 WallBreaker 系统，该系统在柏林洪堡大学组织的 2013 年字符串相似性搜索/加入竞赛中使用[1]。我们考虑如何针对给定的字符串 P（模式）有效地找到词典中的所有单词 W，使得 P 和 W 之间的距离不超过给定的界限 b 。该问题的经典解决方案尝试从模式的左边界开始，以严格的从左到右的方式将 P 与合适的词典单词对齐。在搜索期间，仅访问词典单词的前缀，其中到模式的前缀P'的距离不超过给定界限b。这个解决方案的主要问题是所谓的“墙效应”：如果我们容忍 b 个错误并开始从左到右在词典中搜索，那么在前 b 个步骤中我们必须考虑词典单词的所有前缀。最终，这些前缀中只有一小部分会产生有用的词典单词，这意味着我们详尽的初始搜索是浪费时间。为了避免“墙效应”，在 WallBreaker 中，我们实现了[3]中首先提出的新方法。为了概括它，我们假设该模式可以与词典单词对齐，并且错误不超过 b。显然，如果我们将模式分为 b + 1 块，那么至少有一块将与答案集中某个词典单词的相应子串完全匹配。在我们的方法中，我们首先找到与给定的模式片段完全匹配的词典子字符串。之后，我们继续扩展这种对齐方式，逐步在左侧或右侧附加新的部件。对于新块的对齐，每一步都可以容忍更多的错误，这保证了最终可能出现b个错误。由于在后面的步骤中，要扩展的有趣子串的集合已经很小，因此避免了墙壁效应，因此我们需要容忍更多错误并没有什么坏处。对于这种搜索策略，需要一种新的词典表示形式，我们可以在单词的任何点开始遍历。在我们的新方法中，词典被表示为对称紧凑有向无环词图（SCDAWG）。该指数结构可以被视为相关指数结构的长期发展的一部分。我们的实现并行执行搜索查询。它是用 ANSI C 实现的，用 GCC 编译，除了 LIBC 和 POSIX 线程之外不使用任何其他库。平均而言，它在大约 0.088 毫秒内对包含 750 000 个条目的词典中的 100 个字符模式执行相似性搜索，其中最多有 16 个错误。
In this paper we present the WallBreaker system for similarity search as used in the String Similarity Search/Join Competition, 2013, organized by the Humboldt University of Berlin [1]. We consider the problem of how to efficiently find for a given string P (pattern) all words W in a lexicon such that the distance between P and W does not exceed a given bound b. Classical solutions to this problem try to align P with suitable lexicon words in a strict left-to-right manner, starting at the left border of the pattern. During the search, only prefixes of lexicon words are visited where the distance to a prefix P' of the pattern does not exceed the given bound b. The main problem with this solution is the so-called "wall effect": if we tolerate b errors and start searching in the lexicon from left to right, then in the first b steps we have to consider all prefixes of lexicon words. Eventually, only a tiny fraction of these prefixes will lead to a useful lexicon word, which means that our exhaustive initial search represents a waste of time. To avoid the "wall effect", in WallBreaker we have implemented our new method presented first in [3]. To sketch it let us assume that the pattern can be aligned with a lexicon word with not more than b errors. Clearly, if we divide the pattern into b + 1 pieces, then at least one piece will exactly match the corresponding substring of a lexicon word in the answer set. In our approach we first find the lexicon substrings that exactly match such a given piece of the pattern. Afterwards we continue by extending this alignment, step-wise attaching new pieces on the left or right side. For the alignment of new pieces, more errors are tolerated at each step, which guarantees that eventually b errors can occur. Since at later steps the set of interesting substrings to be extended is already small the wall effect is avoided, it does not hurt that we need to tolerate more errors. For this kind of search strategy, a new representation of the lexicon is needed where we can start traversal at any point of a word. In our new approach, the lexicon is represented as symmetric compact directed acyclic word graph (SCDAWG). This index structure can be seen as a part of a longer development of related index structures. Our implementation executes the search queries in parallel. It is realized in ANSI C, compiled with GCC and does not use any additional libraries beside LIBC and POSIX threads. In average it performs a similarity search of a 100 character pattern with up to 16 errors in a lexicon with 750 000 entries in about 0.088 ms.