Title :
RippleLog: A Path Search Algorithm for a Distributed Query Processing
Author :
Zhang, Junhu ; Wang, Jinlong ; Yang, Dongqing
Author_Institution :
Sch. of Comput. Sci. & Eng., Qingdao Technol. Univ., Qingdao, China
Abstract :
Distributed query processing (DQP) requires data or decomposed sub-queries be routed to different destination nodes for execution, thus a path search algorithm is needed to find best paths for data/query transmissions. When a node doesn´t know how to route a data/query to a specified destination node, the path search algorithm on the node has to initiate a message passing procedure around its neighbors to find the best path to the destination. To accomplish the path search with low message passing traffic for distributed query processing, the paper propose a distinctive path search algorithm, RippleLog, which is composed of the following two mechanisms: 1)the incremental message passing mechanism, which limits the number of nodes involved for the path search so as to reduce the message passing traffic; 2)the logging mechanism, which maintains a message-log on each node for the best path evaluation and further reduce the message passing traffic.
Keywords :
distributed processing; query processing; search problems; RippleLog; decomposed sub-queries; distributed query processing; logging mechanism; message passing procedure; path search algorithm; Algorithm design and analysis; Computer science; Cost function; Data engineering; Design optimization; Distributed computing; Message passing; Query processing; Routing protocols; Search methods; data/query transmission; distributed query processing; incremental path search; logging; ripple; routing;
Conference_Titel :
Natural Computation, 2009. ICNC '09. Fifth International Conference on
Conference_Location :
Tianjin
Print_ISBN :
978-0-7695-3736-8
DOI :
10.1109/ICNC.2009.350