Webarc:PISA - Revision history

Scsong at 23:26, 24 September 2008

2008-09-24T23:26:56Z

← Older revision		Revision as of 23:26, 24 September 2008
Line 3:		Line 3:

	Previous indexing schemes construct a B<sup>+</sup>-Tree in which each key entry consists of the concatenation of a URL and crawl time. Based on the concatenated key, a search through the B<sup>+</sup>-Tree leads to a container ID and an offset where the corresponding content has been stored. Clearly the B<sup>+</sup>-Tree will have separate entries for the same URL with different crawl times, and the corresponding web content will be stored separately for every crawl even though the content may not change over the past several crawls. To avoid storing any duplicate web content and yet maintain the ability to recover the contents corresponding to a URL and a date, we use techniques that are similar to those introduced for persistent or multi-version data structures .		Previous indexing schemes construct a B<sup>+</sup>-Tree in which each key entry consists of the concatenation of a URL and crawl time. Based on the concatenated key, a search through the B<sup>+</sup>-Tree leads to a container ID and an offset where the corresponding content has been stored. Clearly the B<sup>+</sup>-Tree will have separate entries for the same URL with different crawl times, and the corresponding web content will be stored separately for every crawl even though the content may not change over the past several crawls. To avoid storing any duplicate web content and yet maintain the ability to recover the contents corresponding to a URL and a date, we use techniques that are similar to those introduced for persistent or multi-version data structures .

			== Operations ==

	The followings are some of the notable operations that PISA supports.		The followings are some of the notable operations that PISA supports.
Line 12:		Line 14:
	* '''(----, time span) Query''': Given a time span, determine all the URLs and their corresponding locations in the archive, which were valid at the specified time span.		* '''(----, time span) Query''': Given a time span, determine all the URLs and their corresponding locations in the archive, which were valid at the specified time span.

			== Performance ==
	Our PISA indexing structure is somewhat simpler and more practical than those reported in the literature, but achieves the same asymptotic performance for our dynamic operations as the best known schemes.		Our PISA indexing structure is somewhat simpler and more practical than those reported in the literature, but achieves the same asymptotic performance for our dynamic operations as the best known schemes.

Scsong at 22:44, 24 September 2008

2008-09-24T22:44:41Z

← Older revision		Revision as of 22:44, 24 September 2008
Line 99:		Line 99:
	\| align="right" \| 4.444ms		\| align="right" \| 4.444ms
	\|}		\|}

			== Publication ==
			Song, S. and JaJa, J., Archiving Temporal Web Information: Organization of Web Contents for Fast Access and Compact Storage:UMIACS-TR-2008-08. 2008, University of Maryland Institute for Advanced Computer Studies. [[media:temporal-web-archiving-final-umiacs-tr-2008-08.pdf\|pdf]]

Scsong at 22:13, 24 September 2008

2008-09-24T22:13:20Z

← Older revision		Revision as of 22:13, 24 September 2008
Line 16:		Line 16:

	{\| class="wikitable" border="1" align="center"		{\| class="wikitable" border="1" align="center"
	\|+ PISA Performance		\|+ '''PISA Performance'''
	\|-		\|-
	! (URL,time) Insert		! (URL,time) Insert

Scsong at 22:12, 24 September 2008

2008-09-24T22:12:42Z

← Older revision		Revision as of 22:12, 24 September 2008
Line 31:		Line 31:
	\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>
	\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>
	\| align="center" \| <math> \textstyle O( ) </math>		\| align="center" \| <math> \textstyle O(???TBD???) </math>
	\| align="center" \| <math> \textstyle O(\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O(\frac{R}{B}) </math>
	\|}		\|}

Scsong at 22:12, 24 September 2008

2008-09-24T22:12:21Z

← Older revision		Revision as of 22:12, 24 September 2008
Line 31:		Line 31:
	\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>
	\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>
	\| align="center" \| <math> \textstyle O( ) </math>		\| align="center" \| <math> \textstyle O( ) </math>
	\| align="center" \| <math> \textstyle O(\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O(\frac{R}{B}) </math>
	\|}		\|}

Scsong at 22:11, 24 September 2008

2008-09-24T22:11:59Z

← Older revision		Revision as of 22:11, 24 September 2008
Line 18:		Line 18:
	\|+ PISA Performance		\|+ PISA Performance
	\|-		\|-
	! (URL, time) Insert		! (URL,time) Insert
	! (URL, ''now'') Query		! (URL,''now'') Query
	! (URL, time) Query		! (URL,time) Query
	! (URL, time span) Query		! (URL,time span) Query
	! (URL, ---) Query		! (URL,---) Query
	! (---, time span) Query		! (---,time span) Query
	! Space		! Space
	\|-		\|-

Scsong at 22:11, 24 September 2008

2008-09-24T22:11:39Z

← Older revision		Revision as of 22:11, 24 September 2008
Line 80:		Line 80:
	[[Image:dup_nw_size.png\|320px]][[Image:dup_gw_size.png\|320px]]		[[Image:dup_nw_size.png\|320px]][[Image:dup_gw_size.png\|320px]]

	The time ~~overhead~~ to process the two datasets is in the following table.		The time overheads to process the two datasets are in the following table.

	{\| class="wikitable" border="1"		{\| class="wikitable" border="1"

Scsong at 22:11, 24 September 2008

2008-09-24T22:11:27Z

← Older revision		Revision as of 22:11, 24 September 2008
Line 82:		Line 82:
	The time overhead to process the two datasets is in the following table.		The time overhead to process the two datasets is in the following table.

	{\| class="wikitable" border="1~~" align="center~~"		{\| class="wikitable" border="1"
	\|-		\|-
	!		!

Scsong at 22:11, 24 September 2008

2008-09-24T22:11:12Z

← Older revision		Revision as of 22:11, 24 September 2008
Line 87:		Line 87:
	! Total		! Total
	! Per Page (Average)		! Per Page (Average)
			! Per MB(Average)
	\|-		\|-
	! align="left" \| News Websites		! align="left" \| News Websites

Scsong at 22:09, 24 September 2008

2008-09-24T22:09:44Z

@@ Line 4: / Line 4: @@
 Previous indexing schemes construct a B<sup>+</sup>-Tree in which each key entry consists of the concatenation of a URL and crawl time. Based on the concatenated key, a search through the B<sup>+</sup>-Tree leads to a container ID and an offset where the corresponding content has been stored. Clearly the B<sup>+</sup>-Tree will have separate entries for the same URL with different crawl times, and the corresponding web content will be stored separately for every crawl even though the content may not change over the past several crawls. To avoid storing any duplicate web content and yet maintain the ability to recover the contents corresponding to a URL and a date, we use techniques that are similar to those introduced for persistent or multi-version data structures .
-PISA supports the following operations.
+The followings are some of the notable operations that PISA supports.
 * '''(URL, time) Insert''': Given an object defined by a URL and a crawl time, insert the information regarding the object into the indexing structure with a pointer to its container and the offset within the container.
-* '''(URL, time) Query''': Given a URL and a time, determine the location of the content of the URL that was valid at the specified time. The location refers to the container ID and the offset within the container.
+* '''(URL, time) Query''': Given a URL and a time, determine the location of the content of the URL that was valid at the specified time. The location refers to the container ID and the offset within the container. (URL, ''now'') Query is a special case of this type of query, which determines the location of the most-recent content of the URL.
 * '''(URL, time span) Query''': Given a URL and a time span, determine the locations of the contents of the URL that were valid during the specified time span.
 * '''(URL, ---) Query''': Given a URL, determine all the locations and crawl times corresponding to the URL.
@@ Line 19: / Line 19: @@
 |-
 ! (URL, time) Insert
 ! (URL, time) Query
 ! (URL, time span) Query
@@ Line 25: / Line 26: @@
 ! Space
 |-
 | align="center" | <math> \textstyle O(log_B M) </math>
 | align="center" | <math> \textstyle O(log_B N) </math>
@@ Line 38: / Line 40: @@
 '''R''': the number of results
-PISA is essentially a tree-like hierarchical structure. However, it differs from the tree structure, since two different parent nodes can point to the same child node. In PISA, we call internal nodes including the root ''index blocks'', while we call leaf nodes ''data blocks''. Also, we call data items in an index block as ''index entries'', and those in a data block ''data entries''. We use the term ''block'' to mean both index block and data block, and ''entry'' to mean both index entry and data entry, whenever the distinction is not necessary.
+[[Image:dup_nw_pages.png|320px]][[Image:dup_gw_pages.png|320px]]
-Each index block is composed of header entries and index entries. Inside the header entries are the number of all entries in the block, the number of live entries in the block, the pointer to the previous version, and the key with which the upper level block indexes the current block. Each index entry contains an index key, birth time, death time, and a pointer to a block in the child level. We use {key, t_birth, t_death, ptr} to indicate these four fields.
+The following two graphs show the percentage of the byte size of duplicate web sites.
-Similarly, a data block includes the same set of header entries, and data entries. Each data entry is composed of four fields, {key, t_birth, t_death, loc}, that are a data key (URL), birth time, death time, and the location where the actual contents with the data key resides in the archive. Note that the location information typically has a container ID (or filename) and an offset.
+[[Image:dup_nw_size.png|320px]][[Image:dup_gw_size.png|320px]]

← Older revision		Revision as of 22:12, 24 September 2008
Line 31:		Line 31:
	\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>
	\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>
	\| align="center" \| <math> \textstyle O( ) </math>		\| align="center" \| <math> \textstyle O(???TBD???) </math>
	\| align="center" \| <math> \textstyle O(\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O(\frac{R}{B}) </math>
	\|}		\|}

← Older revision		Revision as of 22:12, 24 September 2008
Line 31:		Line 31:
	\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>
	\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O((log_B N)+\frac{R}{B}) </math>
	\| align="center" \| <math> \textstyle O( ) </math>		\| align="center" \| <math> \textstyle O( ) </math>
	\| align="center" \| <math> \textstyle O(\frac{R}{B}) </math>		\| align="center" \| <math> \textstyle O(\frac{R}{B}) </math>
	\|}		\|}