Enhanced Lookup Queries for Large-Scale Distributed Data Structures

Abstract. Structured peer-to-peer systems are a class of distributed data struc-tures that provided initially only exact-match queries in a scalable way. Exact-match queries consist of retrieving single values from the network (i.e., put(key, value)/value←get(key)), in such a way that if the data exists, it is returned. Unfor-tunately, this service is not enough for modern distributed and parallel applications. Thereafter richer queries have been the focus on the field of distributed systems based on peer-to-peer networks. Range queries, k-nearest neighbour queries and spatial queries belong to the family of similarity queries. This sort of queries are used by a wide range of applications. This chapter performs a comparison of the last and most remarkable works in this field. To do so, a set of evaluation parame-ters are defined with which all systems are compared to. Examples of the analysed parameters are: overlay network topology, application domain, query correctness, completeness, storage and time efficiency and load balancing, to say the least. The goal, thus, is to provide an insight on peer-to-peer-enabled distributed and parallel algorithms that support similarity queries in the large scale