Webarc:Packaging - Revision history

Scsong at 22:43, 24 September 2008

2008-09-24T22:43:38Z

← Older revision		Revision as of 22:43, 24 September 2008
Line 139:		Line 139:

	[[Image:avg_ih.png\|320px]][[Image:avg_dc.png\|320px]]		[[Image:avg_ih.png\|320px]][[Image:avg_dc.png\|320px]]

			== Publication ==
			Song, S. and JaJa, J. Fast Browsing of Archived Web Contents. in 8th International Web Archiving Workshop. 2008. Aarhus, Denmark. [[media:iwaw08_Song_JaJa_Final.pdf\|pdf]]

Scsong at 18:37, 24 September 2008

2008-09-24T18:37:27Z

← Older revision		Revision as of 18:37, 24 September 2008
Line 133:		Line 133:

	[[Image:stanford_dc.png\|640px]]		[[Image:stanford_dc.png\|640px]]



	The following two graphs show the average number of inter-container hops and distinct containers, respectively.		The following two graphs show the average number of inter-container hops and distinct containers, respectively.

	[[Image:avg_ih.png\|320px]][[Image:avg_dc.png\|320px]]		[[Image:avg_ih.png\|320px]][[Image:avg_dc.png\|320px]]

Scsong at 18:37, 24 September 2008

2008-09-24T18:37:13Z

← Older revision		Revision as of 18:37, 24 September 2008
Line 137:		Line 137:

	[[Image:avg_ih.png\|320px]][[Image:avg_dc.png\|320px]]		[[Image:avg_ih.png\|320px]][[Image:avg_dc.png\|320px]]


	~~In each of 1000 random walks we run, we count the number of inter~~

Scsong at 18:37, 24 September 2008

2008-09-24T18:37:01Z

← Older revision		Revision as of 18:37, 24 September 2008
Line 136:		Line 136:
	The following two graphs show the average number of inter-container hops and distinct containers, respectively.		The following two graphs show the average number of inter-container hops and distinct containers, respectively.

	[[Image:avg_ih.png\|~~640px~~]]		[[Image:avg_ih.png\|320px]][[Image:avg_dc.png\|320px]]

	[[Image:avg_dc.png\|~~640px~~]]


	In each of 1000 random walks we run, we count the number of inter		In each of 1000 random walks we run, we count the number of inter

Scsong at 18:36, 24 September 2008

2008-09-24T18:36:13Z

← Older revision		Revision as of 18:36, 24 September 2008
Line 126:		Line 126:
	We run 1000 random walks. In each random walk, we let a user hop 10 times randomly in the web graph. The following histograms show the number of random walks (out of 1000) in the y-axis for the number of inter-container hops and distinct containers, respectively. The first two histograms are for the UMIACS web graph, and the next two histograms are for the Stanford web graph. In any case, it is clear that GP and ER+GP techniques required fewer number of inter-container hops as well as distinct containers. For example, the first histogram shows that more than 600 random walks (out of 1000) needed only a single container when ER+GP was applied in the UMIACS web graph.		We run 1000 random walks. In each random walk, we let a user hop 10 times randomly in the web graph. The following histograms show the number of random walks (out of 1000) in the y-axis for the number of inter-container hops and distinct containers, respectively. The first two histograms are for the UMIACS web graph, and the next two histograms are for the Stanford web graph. In any case, it is clear that GP and ER+GP techniques required fewer number of inter-container hops as well as distinct containers. For example, the first histogram shows that more than 600 random walks (out of 1000) needed only a single container when ER+GP was applied in the UMIACS web graph.

	[[Image:umiacs_ih.png]]		[[Image:umiacs_ih.png\|640px]]

	[[Image:umiacs_dc.png]]		[[Image:umiacs_dc.png\|640px]]

	[[Image:stanford_ih.png]]		[[Image:stanford_ih.png\|640px]]

	[[Image:stanford_dc.png]]		[[Image:stanford_dc.png\|640px]]

	The following two graphs show the average number of inter-container hops and distinct containers, respectively.		The following two graphs show the average number of inter-container hops and distinct containers, respectively.

	[[Image:avg_ih.png]]		[[Image:avg_ih.png\|640px]]

	[[Image:avg_dc.png]]		[[Image:avg_dc.png\|640px]]


	In each of 1000 random walks we run, we count the number of inter		In each of 1000 random walks we run, we count the number of inter

Scsong at 18:34, 24 September 2008

2008-09-24T18:34:42Z

← Older revision		Revision as of 18:34, 24 September 2008
Line 127:		Line 127:

	[[Image:umiacs_ih.png]]		[[Image:umiacs_ih.png]]

	[[Image:umiacs_dc.png]]		[[Image:umiacs_dc.png]]

	[[Image:stanford_ih.png]]		[[Image:stanford_ih.png]]

	[[Image:stanford_dc.png]]		[[Image:stanford_dc.png]]

Line 134:		Line 137:

	[[Image:avg_ih.png]]		[[Image:avg_ih.png]]

	[[Image:avg_dc.png]]		[[Image:avg_dc.png]]


	In each of 1000 random walks we run, we count the number of inter		In each of 1000 random walks we run, we count the number of inter

Scsong at 18:34, 24 September 2008

2008-09-24T18:34:27Z

@@ Line 108: / Line 108: @@
 |-
 ! align="center" | Number of Random Walks
 ! align="center" | Number of Hops in Each Walk
 ! align="center" | Probability of Going Back
 ! align="center" | Out-degree of Starting Vertex
 |-
-! align="center" | UMIACS Web Graph
+! align="center" | Policy at Dangling Vertex
-| align="center" | 73.87
+| align="center" | Go Back
 |}

Scsong at 18:03, 24 September 2008

2008-09-24T18:03:19Z

@@ Line 28: / Line 28: @@
 Based on PageRank, we compute EdgeRank for each edge that represents the global probability of the edge to be taken.
-<math> EdgeRank(u) =  \frac{ \displaystyle \frac{1-d}{N} + d  \sum_{v \in I_u} p_{vu} PR(v)}{outdegree(v)}</math>
+<center><math> EdgeRank(u) =  \frac{ \displaystyle \frac{1-d}{N} + d  \sum_{v \in I_u} p_{vu} PR(v)}{outdegree(v)}</math></center>
 , where <math>N</math> is the number of pages, <math>d</math> is a damping factor (=0.15), <math>I_u</math> is a set of pages that have hyperlinks to Page <math>u</math>, <math>p_{vu}</math> is the probability of the hyperlink from Page <math>v</math> to Page <math>u</math> to be taken, and <math>PR(v)</math> is the PageRank of Page <math>v</math>
@@ Line 65: / Line 65: @@
 | align="right" | 2312497
 | align="right" | 215.82GB
 |}

Scsong at 16:01, 24 September 2008

2008-09-24T16:01:47Z

← Older revision		Revision as of 16:01, 24 September 2008
Line 43:		Line 43:
	# Compute minimum edge-cut bisection.		# Compute minimum edge-cut bisection.
	# Refine and uncoarsen the partitioned graph.		# Refine and uncoarsen the partitioned graph.

			== Experiments ==
			* Datasets
			** UMIACS: Web Graph built from our crawls of http://umiacs.umd.edu in 2007
			** Stanford: Web Graph built from a crawl of http://stanford.edu in 2002 by the Stanford WebBase project

			{\| class="wikitable" border="1" align="center"
			\|-
			! Datasets
			! # Vertices
			! # Edges
			! Total Vertex Weight
			\|-
			! UMIACS Web Graph
			\| align="right" \| 4579
			\| align="right" \| 9732
			\| align="right" \| 2.49GB
			\|-
			! Stanford Web Graph
			\| align="right" \| 281903
			\| align="right" \| 2312497
			\| align="right" \| 215.82GB
			\|}

Scsong at 15:52, 24 September 2008

2008-09-24T15:52:22Z

← Older revision		Revision as of 15:52, 24 September 2008
Line 17:		Line 17:
	Although simple and straightforward, one problem with this simple packaging approach appears at access time. That is, tightly related pages can end up in different containers, and more number of containers will be necessary in a random browsing session.		Although simple and straightforward, one problem with this simple packaging approach appears at access time. That is, tightly related pages can end up in different containers, and more number of containers will be necessary in a random browsing session.

	[[Image:conv_container_packaging.png\|~~640px~~]]		[[Image:conv_container_packaging.png\|480px]]

	== Our Goal ==		== Our Goal ==
	We aim to develop a methodology to minimize the probability that a user jumps often between containers when accessing the web archive.		We aim to develop a methodology to minimize the probability that a user jumps often between containers when accessing the web archive.

	[[Image:ideal_container_packaging.png\|~~640px~~]]		[[Image:ideal_container_packaging.png\|480px]]

	== Our Approach ==		== Our Approach ==