Databases Reference
In-Depth Information
Hash−table
index of
bids
(d) Look up
bids with
(e) Copy to
hash−key
w
output if
w
is the only word
(f) Copy with
status 1 if more
Word
w
than one word
Hash on second word
(a) Look up
List of
Partially
matched
bids with
matched
(b) Move to
output if
is the last word
bids
hash−key
w
bids
w
(c) Rehash
with one higher
w
status if
is not last
w
Figure 8.5: Managing large numbers of bids and large numbers of documents
(vi) If b consists of more than one word, add it, with status 1, to the
table of partially matched bids, using the second word of b as the
hash-key.
3. Produce the list of matched bids as the output.
The benefit of the rarest-first order should now be visible. A bid is only
copied to the second hash table if its rarest word appears in the document. In
comparison, if lexicographic order was used, more bids would be copied to the
second hash table. By minimizing the size of that table, we not only reduce the
amount of work in steps 2(i)-2(iii), but we make it more likely that this entire
table can be kept in main memory.
8.6
Summary of Chapter 8
F
Targeted Advertising: The big advantage that Web-based advertising has
over advertising in conventional media such as newspapers is that Web
advertising can be selected according to the interests of each individual
user. This advantage has enabled many Web services to be supported
entirely by advertising revenue.
F
On- and Off-Line Algorithms: Conventional algorithms that are allowed
to see all their data before producing an answer are called off-line. An on-
