Enhanced Lookup Queries for Large-Scale Distributed Data Structures

Structured peer-to-peer systems are a class of distributed data structures 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. Unfortunately, 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 parameters 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.