Advance Data Structure Research Paper

Overview

For this assignment, you are to get into the mindset of a reviewer, and to practice the skills of hunting down references to find clarifications and explanations.

● Find a research paper from the list below; let’s call this Paper 1. ● Now imagine that you were assigned Paper 1 as a reviewer. The first part of any

paper review is a succinct summary (at most two short paragraphs) of the major contributions of the paper. Write that summary. Your summary should be objective; keep your opinions about the paper limited. (An actual paper review would also include your opinions about the paper after the summary, but they will not be a part of this assignment.) Your summary should also be easy for a program committee member / editor to read. Remember that even if they have more general expertise, they know less about the paper than you do!

● Identify and explain the major components of the paper , using up to one full page. Again, your summary should be objective and easy for an inexpert editor / program committee member to read. (Imagine you six months ago.)

● Skim the rest of the paper to get a general idea of what is going on, and then read as much detail as you can. Describe where you got lost , using up to one full page. (This is not normally part of a review.) Include enough context that your point of confusion is clear to someone who is not familiar with the paper. If you can’t figure out the major contributions of the paper, start over with a different Paper 1. If you never get lost, start over with a different Paper 1.

● Identify another paper that would help enhance your understanding of Paper 1; let’s call this Paper 2. This could be a paper that Paper 1 cites, a paper that cites Paper 1, or just a result of your mad googling skills. Read Paper 2, first skimming to get a general idea of its content, and then trying to read as much detail as you can. Briefly summarize paper 2, describe its connection to where you got lost in paper 1, and describe where you got lost in Paper 2. Use up to one full page.

● Repeat the previous step one more time. Identify yet another paper that would help your understanding of Paper 2; let’s call this Paper 3. Read Paper 3. Briefly summarize Paper 3, describe its connection to where you got lost in previous papers, and describe where you got lost in Paper 3. Use up to one full page. Altogether, your writeup should be roughly 3–5 pages long. Don’t forget to properly cite the papers you read (and any other papers that you reference in your writeup).

Acknowledgment

The description of this assignment is largely based upon a similar assignment from Jeff Erickson.

Great Data Structures Papers

● Lowest Common Ancestors in Trees and Directed Acyclic Graphs, by Michael Bender, Martín Farach-Colton, Giridhar Pemmasani, Steven Skiena, and Pavel Sumazin, JALG 2005. (download here (Links to an external site.))

The first part of this paper provides a very nice presentation of the connection between LCAs and RMQs that we studied. What is new in this paper is the extension from the notion of lowest common ancestors in trees to lowest common ancestors in Directed Acyclic Graphics (DAGs).

● Log-logarithmic worst-case range queries are possible in space Θ(𝑁)Θ(N), by Dan Willard, IPL 17:2, 1983. (download here download) download here

van Emde Boas trees support ● 𝑂(loglog𝑈) ● O(log log U)-time ordered dictionary operations for keys that are integers in range

[0..U-1]. However, that structure also requires ● Θ(𝑈) ● Θ(U) space, even if the actual number of entries is ● 𝑜(𝑈) ● o(U). Willard's y-fast tries provide the same time bounds as vEB trees (though

only in expected sense, as randomization is used) while using only O(n) space for a dictionary with n entries.

● Amortized Efficiency of List Update and Paging Rules, by Daniel Sleator and Robert Tarjan, CACM 28:2, 1985.(download here

● download ● )

A few years prior to the development of splay trees, Sleator and Tarjan produced this first example analyzing a self-adjusting data structure (in this case, a simple list), and a new analysis technique that would become known as competitive analysis.

● A Data Structure for Dynamic Trees, by Daniel Sleator and Robert Tarjan, JCSS 26(3), 1983. (download here

● (Links to an external site.) ● ).

Another classic result of Sleator/Tarjan, this time introducing the link-cut tree. This is somewhat akin to our disjoint set structures that supported union and find, but this time it maintains a forest of trees and allows not only linking operations that merge trees, but also a cut operation that disconnects a portion of a tree.

● Dynamic Optimality --- Almost, by Erik Demaine, Dion Harmon, John Iacono, and Mihai Pǎtraşcu, SICOMP 37(1), 2007. (download here

● (Links to an external site.) ● )

The original splay tree presentation by Sleator/Tarjan came with a bold conjecture known as dynamic optimality. While this paper doesn't directly address splay trees, it defines a new tree named Tango Trees that makes partial progress toward meeting the dynamic optimality property.

● Fractional Cascading: I. A Data Structuring Technique, by Bernard Chazelle and Leonidas Guibas, Algorithmica, 1(1-4), 1986. (download here

● (Links to an external site.) ● )

We all know that binary search for a query q within a set n items can be performed in

● 𝑂(log𝑛) ● O(log n)-time. But what if you were maintaining k different collections and wanted

to search for the same value q within all k of those. Clearly, ● 𝑂(𝑘⋅log𝑛) ● O(k⋅log n)-time is achievable by simply doing an independent search in each

collection. This paper defines a representation that allows for those batched queries to execute in a total of

● 𝑂(𝑘+log𝑛) ● O(k+log n)-time

● Surpassing the Information-Theoretic Bound with Fusion Trees, by Michael Freeman and Dan Willard, JCSS 47(3), 1993. (download here

● download ● )

This paper shows how to beat the commonly stated ● Ω(𝑛log𝑛) ● Ω(nlog n) lower bound for sorting arbitrary elements, though based on a set of

standard operations that are supported by computers on integers. Gotta love when the paper itself includes the disclaimer "Our algorithms have theoretical interest only; the constant factors involved in the execution times preclude practicality."