Approximate Nearest Neighbor under edit distance via product metrics
Approximate Nearest Neighbor under edit distance via product metrics
复制标题
通过产品指标编辑距离下的近似最近邻
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
P. Indyk
中科院分区：
文献类型：
--
作者：
P. Indyk
我们提出了一种基于编辑度量（定义为将一个字符串转换为另一个字符串所需的插入、删除和字符替换的最小数量）的近似最近邻问题的数据结构。对于任何<i>l</i>≥1和长度<i>d</i>的<i>n</i>字符串集，对于任何给定的查询字符串<i>q</i> in <i>O</i>(<i>d</i>)，该数据结构报告一个3<sup><i>l</i></sup>-近似最近邻。该数据结构的空间需求大致为<i> 0 </i>(<i>n</i><sup><i>d</i><sup>1/(<i> 1 </i>+1)</sup></sup>)，即强次指数。据我们所知，这是该问题的第一个查询时间<i> 0 </i>(<i>n</i>)和存储时间<i>d</i>的次指数的数据结构。
We present a data structure for the approximate nearest neighbor problem under edit metric (which is defined as the minimum number of insertions, deletions and character substitutions needed to transform one string into another). For any <i>l</i> ≥ 1 and a set of <i>n</i> strings of length <i>d</i>, the data structure reports a 3<sup><i>l</i></sup>-approximate Nearest Neighbor for any given query string <i>q</i> in <i>O</i>(<i>d</i>) time. The space requirement of this data structure is roughly <i>O</i>(<i>n</i><sup><i>d</i><sup>1/(<i>l</i>+1)</sup></sup>), i.e., strongly subexponential. To our knowledge, this is the first data structure for this problem with both <i>o</i>(<i>n</i>) query time and storage subexponential in <i>d</i>.