Index Structures for Fast Similarity Search for Symbol Strings

被引：0
作者：
D. A. Rachkovskij
机构：
[1] NAS of Ukraine and MES of Ukraine,International Research and Training Center for Information Technologies and Systems
来源：
Cybernetics and Systems Analysis | 2019年 / 55卷
关键词：
similarity search; edit distance; nearest neighbor; near neighbor; index structure; inverted indexing; n-gram; locality-sensitive hashing; treelike structure;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This article surveys index structures for fast similarity search for objects represented by symbol strings. Index structures both for exact and approximate searches by edit distance are considered. Index structures based on inverted indexing, similarity preserving hashing, and treelike structures are mainly presented. Ideas of well-known and recently proposed algorithms are described.
引用
收藏
页码：860 / 878
页数：18
相关论文
共 104 条
[41]  
Mitzenmacher M(2016)Model selection criteria for a linear model to solve discrete ill-posed problems on the basis of singular decomposition and random projection Cybernetics and Systems Analysis 52 647-664
[42]  
Chan H(undefined)undefined undefined undefined undefined-undefined
[43]  
Lam TW(undefined)undefined undefined undefined undefined-undefined
[44]  
Sung W(undefined)undefined undefined undefined undefined-undefined
[45]  
Tam S(undefined)undefined undefined undefined undefined-undefined
[46]  
Wong S(undefined)undefined undefined undefined undefined-undefined
[47]  
Sokolov AM(undefined)undefined undefined undefined undefined-undefined
[48]  
Sokolov AM(undefined)undefined undefined undefined undefined-undefined
[49]  
Li G(undefined)undefined undefined undefined undefined-undefined
[50]  
Deng D(undefined)undefined undefined undefined undefined-undefined
12345678910