This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.
WWW graph benchmark
A variation of the random graph example using web graph data.
The zip file contains a set of SQL scripts intended for use with Postgres (small
modifications might be necessary to run them on a different DBMS).
The scripts create a U-relational representations of a random
graph, and of the answers to queries on the random graph, where each world in
the the database corresponds to one particular instance of the random graph, and
has a corresponding probability.
The graph structure is taken from the web graph data set available at
http://www.nd.edu/~networks/resources/www/www.dat.gz
We assign probabilities to the edges relative to the degree of the end nodes, thus the graph has
few edges with high probability, with the majority of edges having low
probability. The dataset contains an example query showing how to construct
the answer to a query looking for the occurrence of a pattern in the random graph,
such as for example a triangle etc.
* import-www-data.sql - imports the data into relational tables
* init-www-nodes.sql - select a subset of the nodes of the whole graph
* init-www-graph.sql - assign weights to the edges of the graph, giving higher weights to edges whose end nodes have high degree.
* triangle-query.sql - execute the triangle query on the graph (without the conf part).
See the comments inside the SQL source files for a more detailed description.
To use the benchmark run the following sequence of steps:
* unzip the WWW graph file and make sure it is called www.dat
* psql -f import-www-data.sql
* psql -f init-www-nodes.sql
* psql -c "select * from init_www_nodes(0.1);"
* psql -f init-www-graph.sql
* psql -f triangle-query.sql
(Node: see psql options for specifiying database name etc)
Oliver Kennedy
ca20d8e9b6