CSCI 1390, Spring 2025: Written HW 2

Due Date: Monday, May 5, 6 PM. You CANNOT use late hours on the written homework.

Read the following paper excerpts, and answer the questions below. Submit your answers as a single PDF on gradescope here. TAs won’t be answering questions about the writeup in office hours; you should be able to answer the questions below merely with reading comprehension.

Reading

• ACORN – All sections. By Liana Patel, Peter Kraft, Carlos Guestrin, Matei Zaharia.

Questions

The total length of your response should be about 600-700 words, with approximate breakdowns specified below. Please adhere to the breakdowns; you will be penalized, for example, if your summarization is too long, and the other answers are too short. Additionally, we expect you to cite specific examples and evidence from the papers when answering the questions.

Summarization (200-300 words total)

1. What problem is this paper solving? (100-150 words).
2. Why is this problem technically hard to solve (100-150 words).

Comprehension (300-400 words)

3. What are the key issues that cause pre and post-filtering, and specialized indices, to fall short of solving this problem? Be specific in your answer (150-200 words).

4. Describe the modifications made to HNSW construction so arbitrary predicate subgraphs emulate normal HNSW subgraphs (150-200 words).

Synthesis (200-300 words)

5. Consider an insert heavy workload. What is the cost of an insert into an or Acorn style graph, versus some of the other indices you’ve studied in project 4? How would you experimentally judge whether this cost is worth it?