Search and retrieval algorithms for distributed data management systems
Demetrios Zeinalipour-Yazti, Dimitrios Gunopulos, Vana Kalogeraki · 2005
Modern Data Management Systems have to cope with data that is generated automatically and continuously across distributed and potentially geographically diverse locations. Organizing information in centralized repositories is becoming increasingly expensive and in many occasions impractical. This dissertation introduces novel search and retrieval algorithms for Distributed Data Management Systems. In our setting, the information remains in-situ until users request to retrieve it. Our objective is to minimize the utilization of the communication medium and to exploit the inherent parallelism of a distributed environment. Additionally, I consider the challenges of a graph topology between distributed nodes, which is ubiquitous in emerging fields such as Peer-to-Peer Networks, Sensor Networks and Vehicular Networks. Specifically, this dissertation makes the following contributions: (1) Threshold Join Algorithm (TJA), which is a distributed top-K query processing algorithm that operates over a set of exact scores. TJA uses a non-uniform threshold on the queried attribute in order to minimize the number of data objects that have to be transferred towards the querying node. Additionally, TJA resolves queries in the network rather than in a centralized fashion, which minimizes even more the consumption of bandwidth and delay. (2) LB-K and UBLB-K Algorithms , which are specialized distributed top-K query processing algorithms that operate over distributed lower and upper bounds in order to minimize the number of data objects transferred towards the querying engine. (3) Intelligent Search Mechanism (ISM), which is an efficient and scalable technique to route query messages in unstructured Peer-to-Peer systems. ISM is efficient because its performance is bounded by the number of neighbors and scalable because no global knowledge is required to be maintained. ISM also serves as the query routing component in our open source Peerware architecture. (4) Distributed Domain Name Order Algorithm (DDNO), which alleviates the burden incurred by the topology mismatch between the underlying physical network and the overlay network of Peer-to-Peer systems, by clustering topologically close-by nodes together. My dissertation shows that traditional search and retrieval methods can be improved by an order of magnitude by using a combination of local query processing techniques, in-network aggregation and awareness of the underlying network topology.