byteshift

We index geospatial data using a learned index in this work (cf. Section 3): http://cidrdb.org/cidr2021/papers/cidr2021_paper19.pdf

Code: https://github.com/learnedsystems/RadixSpline

For a detailed study of learned indexes, see this work: https://vldb.org/pvldb/vol14/p1-marcus.pdf

All code is available in open source: https://github.com/learnedsystems/SOSD

My understanding is that this is even feasible without location information if you use an approximate filter (e.g., a Cuckoo Filter [1]), which they propose in DP-3T (II).

With 20 bits/key such filters yield a false positive rate (FPR) of 0.001%. Meaning for 100,000 new cases per day worldwide, you would only need to download 0.24 MiB.

Note that the FPR applies to each lookup. That is, if you have collected say 100 tokens on a given day, the overall probability of a false positive will be 0.01% (assuming independence). With each extra bit per key you can roughly halve that probability. So in practice size won't be an issue.

[1] https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

For this year's contest, the task is to evaluate batches of database join queries on a set of pre-defined relations. The challenge is to execute the queries as fast as possible without (much) prior indexing. So the time has finally come to unleash your fastest hash table implementations!

The top-5 best-ranking undergrad or grad student teams are invited to the 2018 ACM SIGMOD conference in Houston, TX. The winning team will be awarded a prize of USD $7,000, and there will be an additional prize of USD $3,000 for the runner-up.

Cool stuff! We actually built a similar system to analyze the NYC taxi dataset (or any other geospatial dataset). We use the (PostgreSQL wire protocol compliant) HyPerSpace database in the backend [1]. Let us know if you're ever experiencing performance problems with PostGIS.

[1] https://db.in.tum.de/downloads/publications/hyperspace.pdf