508 - 533: Inverted Index, Top-k and Skyline Queries

Question 1

In an inverted index, what does the posting list store?

a) Hash values of terms
b) Document IDs containing the term
c) Scores of terms in documents
d) Aggregated top-k scores

Answer 1

b) Document IDs containing the term

Question 2

What is the goal of a Top-k Query?

a) Retrieve all documents with the highest scores
b) Compute the k objects with the highest aggregated scores
c) Find the k smallest indexed objects
d) List all objects in sorted order

Answer 2

b) Compute the k objects with the highest aggregated scores

Question 3

What does Fagin’s Algorithm do first during query processing?

a) Perform random access to all lists
b) Aggregate scores directly
c) Read sequentially from each list to find k distinct objects in all lists
d) Skip lists with low scores

Answer 3

c) Read sequentially from each list to find k distinct objects in all lists

Question 4

What defines a Skyline in a dataset?

a) The most frequent data points
b) Points dominated by all others
c) Points not dominated by any other point
d) The first k highest-scoring points

Answer 4

c) Points not dominated by any other point

Question 5

What is the key difference between Fagin’s Algorithm and the Threshold Algorithm?

Answer 5

Fagin’s Algorithm processes until k objects are found in all lists, while the Threshold Algorithm uses a threshold (τ) to terminate earlier when no unseen objects can exceed the current scores.

Question 6

Explain Dominance in Skyline Queries.

Answer 6

A point p dominates another point q if p is at least as good as q in all dimensions and strictly better in at least one dimension.

Question 7

How does an inverted index improve search efficiency?

Answer 7

By mapping terms to a list of documents containing those terms, enabling efficient query retrieval.

Question 8

What is the purpose of the k-skyband in Skyline Queries?

Answer 8

It consists of points dominated at most k−1 times, generalizing the concept of Skyline Queries.

Question 9

Why is monotonicity important in Top-k Query processing?

Answer 9

It ensures that if an object has lower individual scores than another in all lists, its aggregated score cannot exceed the other’s.

Question 10

Describe the role of aggregation functions in Top-k Queries.

Answer 10

They combine individual scores from index lists to compute an overall score for each object, used to rank results.