一种自适应子空间相似性搜索方法

doi:10.11959/j.issn.1000-0801.2015190

摘要/Abstract

摘要：

近年来，在多媒体信息检索、相似性连接和时间序列匹配等数据库领域的相似搜索研究备受关注。绝大部分工作都是在欧式空间条件下，使用度量距离函数计算最近邻（如 kNN、kNNJ）来解决搜索目标集合问题。但已有研究表明，此条件下的搜索结果准确性很容易受到高差异维度的影响，且对应的解决方案尚缺乏灵活性和顽健性。首先提出了单机环境下动态子空间（部分维度）下相似搜索问题及解决方案。随着数据规模的扩大，单机算法不能很好地扩展，随之又提出了Hadoop框架下的分布式算法。实验证实，在不影响准确率的情况下，分布式算法的性能要优于集中式算法。

关键词: 自适应子空间, 相似性搜索, 非度量距离方法, MapReduce分布式计算框架

Abstract:

In recent years，such database fields as multimedia information retrieval，similarity join and time series matching，where similarity search has attracted much attention.Existing researches mostly compute nearest neighbor to solve problems about search target set，such as kNN and kNNJ，by metric distance functions in the Euclidean space.But some studies showed that high dissimilarity dimensions had got great effect on the accuracy of answer and flexibility and robustness still were lacked in corresponding solutions.Thus centralized dynamic subspace or partial dimensions similarity search problem and algorithms were proposed at first.Furthermore，with the emerge of very large dataset，centralized algorithms can，t extend very well.Finally，the distributed ones under hadoop framework were proposed.Experiments prove that distributed algorithms outperform centralized ones in the performance without accuracy loss.

Key words: adaptive subspace, similarity search, non-metric distance method, MapReduce distributed computing framework

任建新,陈华辉. 一种自适应子空间相似性搜索方法[J]. 电信科学, 2015, 31(7): 63-74.

Jianxin Ren,Huahui Chen. An Adaptive Subspace Similarity Search Approach[J]. Telecommunications Science, 2015, 31(7): 63-74.

图/表 16

图1

图2

图3

图4

图5

表1

图6

表2

表3

图7

图8

图9

图10

图11

图12

图13

参考文献 19

1	Lian X ， Chen L . Subspace similarity search under Lp-Norm. IEEE Transactions on Knowledge and Data Engineering， 2012，24（2）： 365～382
2	Hinneburg A ， Aggarwal C ， Keim D A ，et al. What is the nearest neighbor in high dimensional spaces. Proceedings of the 26th VLDB Conference， Cairo，Egypt， 2000： 506～515
3	张慧，郑吉平，韩秋廷 . BTreeU-Topk：基于二叉树的不确定数据上的Top-k查询算法. 计算机研究与发展， 2012（1）： 2095～2105 Zhang H ， Zheng J P ， Han Q T . BTreeU-Topk：binary-tree based Top-k query algorithms on uncertain data. Journal of Computer Research and Development， 2012（1）： 2095～2105
4	Shi Y ， Graham B . Similarity search problem research on multi-dimensional data sets. Proceedings of Tenth International Conference on Information Technology：New Generations（ITNG）， Washington DC，USA， 2013： 573～577
5	张彪，李川，徐洪宇等. 基于特征子图的异构信息网络节点相似性度量. 电信科学， 2014，30（11）： 66～72 Zhang B ， Li C ， Xu H Y ，et al. Heterogeneous information networks node similarity measurement based on feature sub-graph. Telecommunications Science， 2014，30（11）： 66～72
6	Watanabe S ， Sawada H ， Minami Y ，et al. Fast similarity search on a large speech data set with neighborhood graph indexing. Proceedings of 2010 IEEE International Conference on Acoustics Speech and Signal Processing （ICASSP）， Dallas，USA， 2010： 5358～5361
7	Marios ， Yannis . R-trees：a dynamic index structure for spatial searching. Boston，MA，USA， 1984： 993～1002
8	Kriegel H P ， Kroger P ， Schubert M ，et al. Efficient query processing in arbitrary subspaces using vector approximations. Proceedings of the 18th International Conference on Scientific and Statistical Database Management， Washington DC，USA， 2006： 184～190
9	Zhang D X ， Agrawal D ， Chen G ，et al. HashFile：an efficient index structure for multimedia data. Proceedings of the IEEE 27th International Conference on Data Engineering（ICDE）， Washington DC，USA， 2011： 1103～1114
10	Datar M ， Immorlica N ， Indyk P ，et al. Locality-sensitive hashing scheme based on p-stable distributions. Proceedings of the 20th Annual Symposium on Computational Geometry， New York，USA， 2004： 253～262
11	Lv Q ， Josephson W ， Wang Z ，et al. Multi-probe LSH：efficient indexing for high-dimensional similarity search. Proceedings of the 33rd International Conference on Very Large Data Bases， Vienna，Austria， 2007： 950～961
12	林悦 . 基于散列算法的高维数据的最近邻检索（硕士学位论文）. 浙江大学， 2013 Lin Y . Hashing based algorithms for nearest neighbor search in high dimensions（master dissertation）. Zhejiang University， 2013
13	Zhang Z J ， Ooi B C ， Parthasarathy S ，et al. Similarity search on bregman divergence：towards non-metric indexing. Proceedings of the VLDB Endowment， Springer，Geimany， 2009： 13～24
14	Thomas B . Subspace similarity search using the ideas of ranking and top-k retrieval. Proceedings of the IEEE 26th International Conference on Data Engineering Workshops （ICDEW）， California，USA， 2010： 4～9
15	Thomas B . Subspace similarity search using the ideas of ranking and top-k retrieval. Proceedings of Scientific and Statistical Database Management Springer Berlin Heidelberg， Germany， 2010： 555～564
16	He X F . Incremental semi-supervised subspace learning for image retrieval. Proceedings of the 12th Annual ACM International Conference on Multimedia， New York，USA， 2004： 2～8
17	Stupar A ， Michel S ， Schenkel R . Rankreduce-processing k-nearest neighbor queries on top of MapReduce. Proceedings of the 8th Workshop on Large-Scale Distributed Systems for Information Retrieval， Geneva，Switzerland， 2010： 13～18
18	Zhang C ， Li F F ， Jestes J . Efficient parallel kNN joins for large data in MapReduce. Proceedings of the 15th International Conference on Extending Database Technology， New York，NY，USA， 2012： 38～49
19	Kong W H ， Wu J L ， Guo M Y . Manhattan hashing for large-scale image retrieval. Proceedings of the 35th International ACMSIGIR Conference on Research and Development in Information Retrieval， Portland，Oregon，USA， 2012： 45～54

对象	d1	d2	d3
A	3.3	4	7.5
B	2.5	5.2	3
C	6	6.5	6
D	8	9	10
E	0.5	3	4

N取特定值	Top-5 A｛n*｝2S
n*∈ ｛30｝	76，23，90，38，62
n*∈ ｛31，32，37｝	76，23，38，84，69
n*∈ ｛33，34｝	76，23，38，69，67
n*∈ ｛35，36｝	76，23，38，69，27
n*∈ ｛38，39｝	76，23，38，91，27
n*∈ ｛40～44｝	76，23，38，91，69
n*∈ ｛45～53｝	76，23，38，19，100
n*∈ ｛54｝	76，23，19，47，100

算法	32	54	128	256	512
NA3S_MR	1.78	2.83	6.56	12.83	18.67
NA3S	2.67	4.51	10.61	20.06	43.60