Recently, learned indexes are assisting and are being adopted to replace traditional indexes for their low memory usage and high query performance. However, existing learned indexes suffer in query efficiency when dealing with locally skewed data distributions which may be caused or exacerbated by ubiquitous updates. Frequent model retraining and reconstruction is required under this circumstance. To address this issue, we present Chameleon, an adaptive learned index for locally skewed data especially in the context of frequent updates. We propose a metric for measuring local skewness, based on which we employ Multi-Agent Reinforcement Learning to assist in locating locally skewed regions and optimizing index structures. Additionally, to reduce the blocking time caused by index model retraining, we propose a lightweight lock named the Interval Lock to achieve a non-blocking retraining. Extensive experiments demonstrate that, without costing more memory, Chameleon outperforms the state-of-the-art learned indexes by up to 3.75 x and 4.37 x in lookup times for read-only and mixed workloads, respectively, and it accelerates update processing by up to 2.92 x.

Abstract In this paper, we study the Time-Dependent k Nearest Neighbor (TD- k NN) query on moving objects that aims to return k objects arriving at the query location with the least traveling cost departing at a given time t . Although the k NN query on moving objects has been widely studied in the scenario of the static road network, the TD- k NN query tends to be more complicated and challenging because under the time-dependent road network, the cost of each edge is measured by a cost function rather than a fixed distance value. To tackle such difficulty, we adopt the framework of GLAD and develop an advanced index structure to support efficient fastest travel cost query on time-dependent road network. In particular, we propose the Time-Dependent H2H (TD-H2H) index, which pre-computes the aggregated weight functions between each node to some specific nodes in the decomposition tree derived from the road network. Additionally, we establish a grid index on moving objects for candidate object retrieval and location update. To further accelerate the TD- k NN query, two pruning strategies are proposed in our solution. Apart from that, we extend our framework to tackle the time-dependent approachable k NN (TD-A k NN) query on moving objects targeting for the application of taxi-hailing service, where the moving object might have been occupied. Extensive experiments with different parameter settings on real-world road network show that our solutions for both TD- k NN and TD-A k NN queries are superior to the competitors in orders of magnitude.