label timestamp of partition 0 is (1,5). Using Z-curve with order = 3, the Z-value of O, i.e., xrep is (010011)2. Concatenating indexpartition and xrep, Bxvalue (00010011)2=19. Example O ((0,6), (0.2, -0.3 ),10) and tmu=120 then O's position at the label timestamp of partition: ??? Insertion, update and deletion Given a new object, its index key is computed and then the object is inserted into the Bx-tree as in the B+ tree. An update consists of a deletion followed by an insertion. An auxiliary structure is employed to keep the latest key of each index so that an object can be deleted by searching for the key. The indexing key is computed before affecting the tree. In this way, the Bx-tree directly inherits the good properties of the B+ tree, and achieves efficient update performance. Queries Range query A range query retrieves all objects whose location falls within the rectangular range at time not prior to the current time. The Bx-tree uses query-window enlargement technique to answer queries. Since the Bx-tree stores an object's location as of sometime after its update time, the enlargement involves two cases: a location must either be brought back to an earlier time or forward to a later time. The main idea is to enlarge the query window so that it encloses all objects whose positions are not within query window at its label timestamp but will enter the query window at the query timestamp. After the enlargement, the partitions of the Bx-tree need to be traversed to find objects falling in the enlarged query window. In each partition, the use of a space-filling curve means that a range query in the native, two-dimensional space becomes a set of range queries in the transformed, one-dimensional space. To avoid excessively large query region after expansion in skewed datasets, an optimization of the query algorithm exists, which improves the query efficiency by avoiding unnecessary query enlargement. K nearest neighbor query K nearest neighbor query is computed by iteratively performing range queries with an incrementally enlarged search region until k answers are obtained. Another possibility is to employ similar querying ideas in The iDistance Technique. Other queries The range query and K Nearest Neighbor query algorithms can be easily extended to support interval queries, continuous queries, etc. Adapting relational database engines to accommodate moving objects Since the Bx-tree is an index built on top of a B+ tree