Multi-attribute Range Queries on Structured Overlay Networks

Abstract

Resource discovery is an important mechanism in P2P applications. Chord is usually one of the structured overlays applied in the resource discovery mechanism. Chord adopts the finger table to record the connection between the node and its successors in order to support resource discovery in O (log (N)) (N is the number of nodes). However, Chord has some restrictions, e.g., the keyword searching and the scalability problem. This study proposes a multi-attribute range query (MARQ) overlay based on Chord. The MARQ overlay embeds the node attributes into the node ID to form a structured multi-attribute and multi-ring architecture. Due to the hierarchical multi-attribute property of MARQ, this structured overlay could reduce the search radius and provide the attribute search. Because of the multi-ring property of MARQ, the proposed overlay could improve the scalability and reduce the maintaining cost. This study preserves the characteristics of Chord systems, and adopts the double-link approach to reduce the average number of traveled hops in searching. Therefore, the MARQ overlay could support the multi-attribute range query. Experimental results show that our proposed mechanism could efficiently reduce the average number of traveled hops in searching and then decrease the average searching time.