High-dimensional similarity search on a structured P2P network

An important problem that confronts Peer-to-Peer (P2P) based data management is efficient support for similarity search over a high-dimensional data space. This paper addresses this problem based on the Chord system by means of an efficient space partitioning strategy. The whole data space is first partitioned based on a set of pre-generated reference points. Each reference point has an associated subspace and the union of all subspaces spans the whole data space. Then, all reference points are mapped into a single-dimensional range, and each reference point is identified with a unique number. Thus, a suitably modified Chord system is formed by treating the identifier of each reference point as the node hash value for Chord system. As such, similarity queries could be accomplished by using the reference points as search key, and nodes corresponding to subspaces that intersect the search region could be reached as in Chord. Finally, the proposed approach is compared with the MUCK via simulation. Extensive experiments show that the approach proposed by the authors has advantages for query processing cost and load balancing.