Computer Science ›› 2017, Vol. 44 ›› Issue (Z11): 494-497.doi: 10.11896/j.issn.1002-137X.2017.11A.105

Previous Articles     Next Articles

CS-Chord:Distributed High Dimensional Vector Index Based on Clustering Separation

YUAN Xin-pan, WANG Can-fei, LONG Jun and PENG Cheng   

  • Online:2018-12-01 Published:2018-12-01

Abstract: M-Chord is a high dimensional vector index based on the P2P network,and the sparse vector of the clustering edge is easy to intersect with the query circle,which makes the area of the query increased,and the efficiency of M-Chord is reduced.Based on the idea of M-Chord,this paper proposed a distributed high dimensional vector index (CS-Chord) based on clustering,which separates the edge vectors from the dense vectors.The vector of the central region is still stored in the Chord loop,which saves a lot of resources locating time and improves the efficiency of retrieval.Experimental results show that when the query radius is 0.2,the number of CS-Chord distance computation 2000,reducing about 2500 times compared with M-Chord.The message forwarding times of CS-Chord decreases about 150 times,only 50% of M-Chord.

Key words: High-dimensional vector,Cluster,Chord,Distributed index

[1] SCHUH M A,WYLIE T,BANDA J M,et al.A comprehensive study of iDistance partitioning strategies for knn queries and high-dimensional data indexing[M]∥Big Data.Springer Berlin Heidelberg,2013:238-252.
[2] ZHOU K,HOU Q,WANG R,et al.Real-time KD-tree con-struction on graphics hardware[J].ACM Transactions on Graphics,2008,27(5):126.
[3] ARGE L,BERG M D,HAVERKORT H.The priority R-tree:A practically efficient and worst-case optimal R-tree[J].Acm Transactions on Algorithms,2008,4(1):1-30.
[4] LIU X.The Dirac Operator on Regular Metric Trees[J].Phy-sics,2015,226:165-178.
[5] NOVAK D,ZEZULA P.M-Chord:a scalable distributed similarity search structure[C]∥International Conference on Scalable Information Systems(Infoscale 2006).Hong Kong,2006:1-10.
[6] ALY M,MUNICH M,PERONA P.Distributed Kd-Trees for Ultra Large Scale Object Recognition[C]∥British Machine Vision Conference.2011:1-11.
[7] YIN W,ZHU M,JIANG L.R-Chord:A distributed similarityretrieval system with RPCID[C]∥IEEE International Confe-rence on Network Infrastructure and Digital Content,2009.IcNidc,2009:393-399.
[8] 吴纯青,任沛阁,王小峰.基于语义的网络大数据组织与搜索[J].计算机学报,2015,38(1):1-17.
[9] STOICA I,MORRIS R,KARGER D,et al.Chord:A scalablepeer-to-peer lookup service for internet applications[J].IEEE/ACM Transactions on Networking,2003,11(4):149-160.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!