The Improved Chord Algorithm Supporting Multiple Keywords Querying

The application of P2P network attracts more and more peoples’ attention. Now,the key problem of P2P network is how to find the shared resources quickly, accuratelyand comprehensively. Different P2P networks adopt different topologies, and theirquery efficiency is different as well. The paper analyzes a completely distributedstructured network topology—Chord model. Chord model uses a consistent hashalgorithm, and its lookup strategy is based on the distributed hash table. In Chord model,each node only needs to maintain O(logN) items in finger table to locate the sharedresources. Chord algorithm has many advantages, such as good load balancing, highreliability and high scalability. However, Chord can’t support multiple keywords querydue to use of hash algorithm. Therefore, it can’t locate the shared resourcescomprehensively.The paper presents an improved Chord algorithm for the standard Chordalgorithm’s disadvantages. In improved Chord model, it abandons the consistentalgorithm to get the shared resources’ unique ID, instead, it adopts Bloom Filteralgorithm to achieve them, and the paper still adopts the consistent hash algorithm to getthe nodes’ unique ID. The nodes and shared resources are arranged on Chord ringclockwise not by their ID completely. Firstly, the paper divides the Chord ring intodifferent segments. Then, by the number of1bit of their ID, map them on the differentChord ring segment. The next is to arrange them in the segment by their ID in ascendingorder. When query the shared resources, jump to the segment firstly. Then find theshared resources by the longest-suffix match.To locate the shared resources quickly, each node stores more routing items. Firstly,the paper supposes all the nodes exist in Chord. If the node doesn’t exist, the paper setthe flag V on the node to show that it is a virtual node. The virtual node doesn’t storeany shared resources, but it is responsible for the message forwarding. Each nodeacquires its routing items by its own node’s ID. The regulation is to swap the high-order0bit and low-order1bit of node’s ID. Not only the improved Chord algorithm supportsmultiple keyword query, but also the paper proves the maximum hops is m-2+1andaverage hops is m/2+1theoretically(m is the length of the binary ID), which is betterthan standard Chord algorithm. Lastly, the paper proves the improved Chord algorithm’s performance bysimulation. The simulation mainly focuses on the following aspects: the average hops,the average time delay, the false positive of bloom filter and recall ratio. The simulationis in accordance with the theoretic analyses. The improved Chord model is better thanthe standard Chord model obviously with ignoring of the false positive of bloom filter.