Hey Everyone,

The Practice Final is up!

Chris

Question 4] Team members: Tejas Saoji, Prathiba Nagarajan

L = [ 5, 8, 15, 25 ]

Delta-List = [ 5, 3, 7, 10 ]

Gamma-Code = 001 01 01 1 001 11 0001 010

Q9. Team members: Ekta Khanna, Pragya Rana, Divya Kathiravan, Jayashree Prabunathan, Yashi Kamboj Query processing using term partitioning:

• Suppose a query q contains terms t1,...tq. Then the receptionist will forward the query to node v(t1) responsible for the term t1.
• After creating a set of document score accumulators from t1's posting list, v(t1) forwards the query, along with the accumulator set to the node v(t2) which continues the process and so on.
• Finally, v(tq), sends the final accumulator set to the receptionist where the top m results are selected.

Enhancement

• Each query at a given point in time is processed by only a single node, this scheme does not use intra-query parallelism, so will not reduce the response time.
• This problem can be mitigated to some degree by the receptionist sending pre-fetch instructions to the later v(ti)'s while v(t1) does its calculations.

Team members Anupreet kaur Priyatha, Tina question 10

Team: Nishant Goel and Swapnil Patil

Question 5:

In REBUILD, a new index is built from scratch. When this process is finished, the old index is deleted and replaced with the new one. The time for rebuild is given by, c.d(new) = c.( d(old) – d(delete) + d(insert)) where: c = system specific constant d(new) = new documents d(old) = old documents d(delete) = deleted documents d(insert) = inserted documents

In REMERGE, an index is built from the text found in the newly inserted documents. After this index has been created, it is merged with the previously existing index. The time for remerge is given by, c.d(new) = c.d(insert) + c/4. (d(old)+d(insert))

Now, consider the following example. Let d(old)=100, d(delete)= 70, and d(insert)=20

Using equation for rebuild, c. d(new) = c.(100-70+20) = 50.c

Similarly for remerge, c. d(new) = c.20 + c/4.(100+20) = 50.c

Thus, we can see that both rebuild and remerge have the sane performance for the above mentioned example.

Assumption: It does not take into consideration the REMERGE overhead to garbage collect posting that refer to the deleted documents.

Problem 8. Team Members: Krithika and Kushal

Team Members: Sonal Kabra, Shivika Sodhi, Vikash

Team: Linye Ouyang, Gregory Enriquez

Question 3: Briefly explain the following coding schemes and what they are used for: Canonical Huffman Code, LLRUN.

Canonical Huffman Coding is a symbolwise data compression method that takes in a sequence of symbols and encodes it as a binary representation. The representation of each symbol depends on its frequency, encoding frequent symbols using fewer bits and vice versa. To generate this encoding, a Huffman Tree is generated by creating nodes for each symbol and then merging the two lowest frequency trees until one final tree is generated. For Canonical Huffman Coding, the Huffman tree generated is then sorted lexicographically at each level of the tree. This allows the preamble to contain only the length of the encodings of each symbol and not the encoding.

The LLRUN scheme is a parametric gap compression method used when the gap lists do not follow a geometric distribution. LLRUN groups gap values of similar size into buckets with intervals B_j = [2^j, 2^j+1) and each bucket is encoded to its own code word.

Akshay Bodhke Dhruven Vora Salil Shenoy

Did anybody solve Question 7????