# MEMOCODE 2015 Design Contest: Continuous Skyline Computation

## Results

Congratulations to our winners:

• First Place: Kenichi Koizumi, Mary Inaba, Kei Hiraki, University of Tokyo
• Second Place: Armin Ahmadzadeh, Ehsan Montahaie, Milad Ghafouri, Reza Mirzaei, Saied Rahmani, Farzad Sharif Bakhtiar, Mohsen Gavahi, Rashid Zamanshoar, Hanie Ghasemi, Kianoush Jafari, Saeid Gorgin, Inst. for Research in Fundamental Sciences (IPM), Iran

The 2015 MEMOCODE Design Contest is sponsored by Microsoft and Xilinx. We thank both sponsors for their support.

## Overview

The skyline query operation [1] (also called the "maximum vector problem") is used to identify potentially interesting or useful data points in large multi-dimensional datasets. When the dataset changes over time (through addition and subtraction of points), this is called the "continuous skyline" query [2]. The 2015 MEMOCODE Design Contest problem is to implement a system to efficiently compute the continuous skyline of a large dynamic dataset.

Below you will find descriptions of: the problem, example datasets, and a functional reference implementation. For instructions to download the code and datasets, please sign up by e-mailing Peter Milder at peter.milder@stonybrook.edu with your team information.

## Submission Instructions

Before 11:59PM US Eastern Time on July 1, 2015, submit your design solution in a tar or zip file to peter.milder@stonybrook.edu

Your submission should contain the following items in a single zip or tar file:

1. The names and contact information for all members of your team.
2. Design source files.
3. The runtime of your system processing the "large" dataset based on the timing specified in the testbench supplied with the design challenge.
4. The output of your system for the "large" dataset.
5. Cost (US\$) of your solution. (Actual number, or best estimate).
6. Design documentation describing your submitted solution (implementation platform, design methodology, the organization of your design, and its theory of operation, and a brief analysis of its performance and bottlenecks).

Documentation in the form of PowerPoint slides is perfectly acceptable. The quality and conciseness of the documentation will help in judging. The judges will make a best effort to treat the design source files as confidential. The information in other items is considered public.

## Questions and Answers (Updated June 16, 2015)

May we pre-process the dataset?
No. The timestamps represents a scenario where your database receives a series of dynamic data updates over time. So any pre-processing you do on this data must be done within the timed portion of your design.

Which dataset will be used to evaluate the runtime of the design? What can we assume about it?
The final evaluation will be performed on a new dataset that has the same size $$n$$ and dimensions $$m$$ as the "large" dataset. We will also guarantee that the number of timesteps and the maximum number of skyline elements per timestep will be the same or smaller than in the large dataset.

Can we compute the skylines for different timesteps in parallel or overlapped (as opposed to serially computing them one at a time)?
Yes.

## References

[1] Börzsöny, S., Kossmann, D., & Stocker, K. The Skyline operator. Proceedings 17th International Conference on Data Engineering, 2001.
[2] Morse, M., Patel, J. M., & Grosky, W. I. Efficient continuous skyline computation. Information Sciences, 177(17), 3411–3437, 2007.

## Contact

Peter Milder, peter.milder@stonybrook.edu

This page uses MathJax for displaying mathematical formulas. If your browser has Javascript disabled, formulas will not display correctly.

Previously: 2014 MEMOCODE Design Contest.