Solving Range Queries in a Distributed System
Praveen Yalagandula · 2003
The goal of the project is to design and build a scalable distributed discovery system for documents that (i) supports both simple queries and range queries on document names, (ii) supports efficient insertion and deletion of documents, (iii) distributes both storage and access loads uniformly among all the participants, and (iv) is efficient in terms of the communication cost incurred for responding to queries. The ultimate goal of the project is to support a full-fledged keyword search. A full-fledged keyword search system will support the search based on regular expressions. On the other extreme, a very simple system will just support single keyword based lookups. Distributed Hash Tables (DHT) based systems typically support only simple keyword searches. Several intermediate schemes are possible – that support range queries on single dimension (e.g., [1]) and that support multidimensional sequence of keywords and ranges (e.g., [5]). In this project, we focus on supporting range queries on single dimension. Our approach is to combine ideas from Extendible Hashing [2] and Distributed Hash Tables.