Query Hash Tables - Revision history

Dcat: Reverted edits by Straightener (talk) to last revision by Dcat

2022-10-18T19:18:05Z

Reverted edits by Straightener (talk) to last revision by Dcat

← Older revision		Revision as of 19:18, 18 October 2022
Line 70:		Line 70:
	== URNs - A Special Case ==		== URNs - A Special Case ==

	URNs are treated as a special case: rather than dividing them up into word tokens of [http://tireswheels.org/tires/hankook/optimo_h727 <span style="color:black;font-weight:normal; text-decoration:none!important; background:none!important; text-decoration:none;">Hankook Optimo h727</span>],		URNs are treated as a special case: rather than dividing them up into word tokens,
	they are hashed as a complete fixed length string. For example:		they are hashed as a complete fixed length string. For example:

Straightener: /* URNs - A Special Case */

2012-04-02T19:23:31Z

URNs - A Special Case

← Older revision		Revision as of 19:23, 2 April 2012
Line 70:		Line 70:
	== URNs - A Special Case ==		== URNs - A Special Case ==

	URNs are treated as a special case: rather than dividing them up into word tokens,		URNs are treated as a special case: rather than dividing them up into word tokens of [http://tireswheels.org/tires/hankook/optimo_h727 <span style="color:black;font-weight:normal; text-decoration:none!important; background:none!important; text-decoration:none;">Hankook Optimo h727</span>],
	they are hashed as a complete fixed length string. For example:		they are hashed as a complete fixed length string. For example:

Dcat: /* Introduction */

2009-01-18T02:04:38Z

Introduction

← Older revision		Revision as of 02:04, 18 January 2009
Line 8:		Line 8:

	The concept of filtering hash tables in file sharing was pioneered by Limegroup for		The concept of filtering hash tables in file sharing was pioneered by Limegroup for
	the LimeWire~~? Gnutella1~~ application.		the LimeWire Gnutella application.

	== Table Properties ==		== Table Properties ==

Dcat: /* Query Filtering */

2009-01-01T03:57:24Z

Query Filtering

← Older revision		Revision as of 03:57, 1 January 2009
Line 193:		Line 193:
	* Remember to apply exclusion to every word in an excluded phrase		* Remember to apply exclusion to every word in an excluded phrase

	See the section on the simple query language for more information.		See the section on the [[Simple Query Language and Metadata\|simple query language]] for more information.

Kath: /* Table Exchange */

2005-03-28T11:55:55Z

Table Exchange

← Older revision		Revision as of 11:55, 28 March 2005
Line 111:		Line 111:
	== Table Exchange ==		== Table Exchange ==

	Nodes must keep their neighbouring hubs up to date with their latest local query		Nodes must keep their neighbouring hubs up-to-date with their latest local query
	hash table at all times. Rather than sending the whole table whenever it changes,		hash table at all times. Rather than sending the whole table whenever it changes,
	nodes may opt to send a "table patch", which includes only the difference between		nodes may opt to send a "table patch", which includes only the difference between
Line 118:		Line 118:
	The /[[QHT]] packet is used to supply a query hash table update to a neighbouring hub.		The /[[QHT]] packet is used to supply a query hash table update to a neighbouring hub.
	Its format is compatible with the Gnutella1 "query routing protocol", except that		Its format is compatible with the Gnutella1 "query routing protocol", except that
	Gnutella2 requires a 1-bit per value table while Gnutella1 requires a 4 or 8 bit per		Gnutella2 requires a 1-bit per value table, while Gnutella1 requires a 4 or 8 bit per
	value table. Gnutella2 supports patch compression using the deflate algorithm,		value table. Gnutella2 supports patch compression using the deflate algorithm,
	however this should not be applied if the TCP link itself is compressed.		however, this should not be applied if the TCP link itself is compressed.

	== Table Access ==		== Table Access ==

Kath: /* Word Prefix Extensions */

2005-03-28T11:54:40Z

Word Prefix Extensions

← Older revision		Revision as of 11:54, 28 March 2005
Line 96:		Line 96:

	For words consisting of at least five characters, it is often useful to be able to match		For words consisting of at least five characters, it is often useful to be able to match
	substrings within the word. Unfortunately adding every possible substring of each		substrings within the word. Unfortunately, adding every possible substring of each
	word would increase the density of the QHT, however a simple and effective		word would increase the density of the QHT, however, a simple and effective
	compromise is available:		compromise is available:

Kath: /* Table Properties */

2005-03-28T11:52:43Z

Table Properties

← Older revision		Revision as of 11:52, 28 March 2005
Line 14:		Line 14:
	Query hash tables or QHTs provide enough information to know with certainty that a		Query hash tables or QHTs provide enough information to know with certainty that a
	particular node (and possibly its descendants) will not be able to provide any		particular node (and possibly its descendants) will not be able to provide any
	matching objects for a given query. Conversely the QHT may reveal that a node or		matching objects for a given query. Conversely, the QHT may reveal that a node or
	its descendants may be able to provide matching objects.		its descendants may be able to provide matching objects.

	This property means that queries can be discarded confidently when a transmission		This property means that queries can be discarded confidently when a transmission
	is known to be unnecessary, while not providing the filtering or forwarding node any		is known to be unnecessary, while not providing the filtering or forwarding node, any
	actual information about the searchable content. Neighbours know what their		actual information about the searchable content. Neighbours know what their
	neighbours do not have, but cannot say for sure what they do have. QHTs are also		neighbours do not have, but cannot say for sure what they do have. QHTs are also
	very efficient both in terms of exchange and maintenance and lookup cost.		very efficient, both in terms of exchange and maintenance and lookup cost.

	== Table Content ==		== Table Content ==

Kath: /* Introduction */

2005-03-28T11:51:25Z

Introduction

← Older revision		Revision as of 11:51, 28 March 2005
Line 3:		Line 3:
	Building an efficient network topology is not viable without means to restrict the flow		Building an efficient network topology is not viable without means to restrict the flow
	of information appropriately. In the Gnutella2 network architecture, neighbouring		of information appropriately. In the Gnutella2 network architecture, neighbouring
	nodes exchange compressed hash filter tables describing the content which can be		nodes exchange compressed hash filter tables describing the content, which can be
	reached by communicating with them. These tables are updated dynamically as		reached by communicating with them. These tables are updated dynamically as
	necessary.		necessary.

Dcat at 05:00, 20 March 2005

2005-03-20T05:00:46Z

← Older revision		Revision as of 05:00, 20 March 2005
Line 150:		Line 150:
	</nowiki>		</nowiki>
	</pre>		</pre>

			== The Aggregate or Superset Table ==

			Nodes operating in hub mode must maintain an aggregate or superset query hash
			table, consisting of their own searchable content combined with the QHTs supplied
			by all connected leaves. This aggregate table is supplied to neighbouring hubs,
			allowing them to completely filter traffic for the local hub and its leaves.

			This has two important implications:
			* When a change is detected in either the local content or a connected leaf node's QHT, the aggregate table must be rebuilt and patches dispatched to neighbouring hubs. This will happen often, so an appropriate minimum time between updates should be used. One minute is effective.
			* An aggregate table representing 400 leaves will be much denser than a table representing one node. This means that all tables must be large enough that the aggregate table remains productively sparse.

			To create an aggregate table, start with an empty table of fixed size containing all
			1's. For each contributing table, copy any zero (full) bits to the aggregate table. This
			is effectively an AND operation. If a source table is smaller than the aggregate table,
			a single 0 bit in the source will equate to several zero bits in the aggregate. If the
			source table is larger than the aggregate table, a single zero bit will map to a single
			bit with some loss of accuracy.

			It is of great importance that all QHTs in the system be sufficiently large to allow an
			aggregate table to remain suitably sparse. Ideally each leaf node should provide a
			table less than 1% dense.

			== Query Filtering ==

			Before transmitting a query packet to a connection that has provided a query hash
			table, match the words and URNs in the query against the QHT.

			* If any of the lookups based on URNs found a hit, send the query packet
			* If at least two thirds of lookups based on words found a hit, send
			* Otherwise, drop the packet

			It is important to apply the "two thirds" rule only for words. URNs must provide an
			automatic match.

			Consider all text content in the query, including generic search text and metadata
			search text if it is present. When dealing with simple query language that involves
			quoted phrases and exclusions, apply the following rules:

			* Tokenize quoted phrases into words, ignoring the phrase at this level
			* Ignore excluded words - these do not count as table hits or misses
			* Remember to apply exclusion to every word in an excluded phrase

			See the section on the simple query language for more information.

Dcat at 04:55, 20 March 2005

2005-03-20T04:55:36Z

@@ Line 25: / Line 25: @@
 == Table Content ==
-A QHT is a table of 2^N bits, where each bit represents a unique word-hash value.
+A QHT is a table of 2<sup>N</sup> bits, where each bit represents a unique word-hash value.
-For example a table of 20 bits has 2^20 = 1048576 possible word-hash values. If
+For example a table of 20 bits has 2<sup>20</sup> = 1048576 possible word-hash values. If
 stored uncompressed this table would be 128 KB in size.
@@ Line 33: / Line 33: @@
 * Locate every plain-text word and URN which could be searched for and produce a match/hit
-* Hash the word with a simple hash function to produce a word-hash value which is 0 <= value < (2^N).
+* Hash the word with a simple hash function to produce a word-hash value which is 0 <= value < 2<sup>N</sup>.
 * Set the appropriate bit in the table to zero, representing "full".
@@ Line 121: / Line 121: @@
 value table. Gnutella2 supports patch compression using the deflate algorithm,
 however this should not be applied if the TCP link itself is compressed.