查看文章

We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that a query of the following form can be answered quickly: Given a rectangle R and a real value t_q, report all K points of S that lie inside R at time t_q. We first present an indexing structure that, for any given constant ε > 0, uses O(N/B) disk blocks, where B is the block size, and answers a query in O((N/B)^1/2+ε + K/B) I/Os. It can also report all the points of S that lie inside R during a given time interval. A point can be inserted or deleted, or the trajectory of a point can be changed, in O(log²_B N) I/Os. Next, we present a general approach that improves the query time if the queries arrive in chronological order, by allowing the index to evolve over time. We obtain a trade off between the query time and the number of times the index needs to be updated as the points move. We also describe an indexing …