Boon Thau Loo

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1332
2004

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1332.pdf

This paper describes a distributed infrastructure for querying network graphs with recursive queries. We argue that recursive queries have great practical value as a declarative interface to multi-hop networks. To query these networks in a distributed fashion, we describe the processing of recursive queries using PIER, a P2P relational query processor that utilizes distributed hash tables (DHTs). We focus on studying a set of commonly-used recursive queries based on the transitive closure query. We demonstrate that different query processing techniques will lead to tradeoffs in latency, work sharing and communication overheads. Our experimental results also show that selecting the best execution strategy based on the query workload and graph topology can lead to significant reduction in communication overhead and latency.

BibTeX citation:

@techreport{Loo:CSD-04-1332,
    Author = {Loo, Boon Thau},
    Title = {Querying Network Graphs with Recursive Queries},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2004},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5539.html},
    Number = {UCB/CSD-04-1332},
    Abstract = {This paper describes a distributed infrastructure for querying network graphs with recursive queries. We argue that recursive queries have great practical value as a declarative interface to multi-hop networks. To query these networks in a distributed fashion, we describe the processing of recursive queries using PIER, a P2P relational query processor that utilizes distributed hash tables (DHTs). We focus on studying a set of commonly-used recursive queries based on the transitive closure query. We demonstrate that different query processing techniques will lead to tradeoffs in latency, work sharing and communication overheads. Our experimental results also show that selecting the best execution strategy based on the query workload and graph topology can lead to significant reduction in communication overhead and latency.}
}

EndNote citation:

%0 Report
%A Loo, Boon Thau
%T Querying Network Graphs with Recursive Queries
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1332
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5539.html
%F Loo:CSD-04-1332