SIGMOD 2024 Programming Contest 일기(1)

ACM Sigmod 프로그래밍 대회

최근 SAP 팀원분의 추천(?)으로 Sigmod라는 데이터베이스 학회에서 진행하는 프로그래밍 대회가 있다는 것을 알게 됐다.

http://sigmodcontest2024.eastus.cloudapp.azure.com/index.shtml

ACM SIGMOD 2024 Programming Contest

대회의 목표는 코드가 특정 시간(20분) 이내에 작동하면서, 정확도를 높여야 한다. 이번 주제는 vector에서 kNN을 빠르고 정확하게 찾아야 한다. Atcoder같은 사이트에서 진행하는 휴리스틱 대회와 비슷하면서 데이터베이스 관련 주제인 느낌이다.

1) 문제

먼저 $N$개의 벡터($D=100$으로 고정)가 주어진다. 벡터에는 2개의 attribute가 더 있는데, 하나는 카테고리 $C$(0 이상 int), 하나는 타임스탬프 $T$(0과 1사이 float)이다.

다음으로 $Q$개의 쿼리가 들어온다. 쿼리는 type(0~3)과 $D=100$인 벡터 1개, 요구하는 $C$의 값 및 $T$의 범위가 주어지고, $N$개 벡터 중 $C, T$조건이 쿼리와 만족하면서 가까운 순서대로 kNN($k=100$으로 고정)을 찾아야 한다.

평가는 Recall Score로, 100NN의 순서까지 맞아야 할 필요는 없다. 실제 Top100과 예상한 Top100이 일치하는가가 점수이다. 중요한 점은 인공지능에서 train중 test data를 사용하면 안되듯, $N$개 벡터를 인덱싱하면서 쿼리 벡터의 정보를 사용하면 안된다.

2) 분석

최대 $N = 10^7, Q=4*10^6$이므로, Naive한 방법으로는 $O(NQD)$, 연산량 약 $4*10^{15}$가 되어 시간 초과가 날 것이다. 20분=1200초이므로, 연산량을 $10^{11}$ 수준까지는 줄여야 한다.

3) Baseline 코드

베이스라인 코드의 아이디어는, 인덱싱 때 어떠한 전처리를 하지 않고 쿼리마다 $0.0001*N$개의 벡터만 탐색해 가까운 100개를 구한다. 이 때 실행시간은 약 293초가 나왔다. 정확도는 예상대로 $0.0001$이 나온다.

4) 제출

bash ./run.sh
reprozip trace bash ./run.sh
reprozip pack submission.rpz

이 순서대로 실행 후 submission.rpz를 제출하면 된다.