Towards an Instance-Optimal Z-Index

We present preliminary results on instance-optimal variants of the Z-index, a well-known spatial index that makes use of the Z-order curve. Unlike the base Z-index, the variants we propose aim to adapt to the data and range-query workloads of the given setting. Specifically, we provide an optimal algorithm that builds a Z-index that minimizes the expected number of retrieved data points for the given data and query workload. Moreover, since the optimal algorithm requires supra-linear running time, we additionally propose efficient heuristic algorithms to use in its place. Our experiments evaluate the performance of the resultant Z-indexes.