RAQ: A Range-Queriable Distributed Data Structure
Abstract
Different structures are used in peer-to-peer networks to represent their inherently distributed, self-organized, and decentralized memory structure. In this paper, a simple range-queriable distributed data structure, called RAQ, is proposed to efficiently support exact match and range queries over multi-dimensional data. In RAQ, the key space is partitioned among the network with n nodes, in which each element has links to O n(log ) other elements. We will show that the look-up query for a specified key can be done via O n(log )message passing. Also, RAQ handles range-queries in at most O n(log ) communication steps.
Keywords
P2P Networks, Range-Query, Distributed Data Structure
