Bx-tree

DISPLAYTITLE:Bx-tree In computer science, the Bx tree is a query that is used to update efficient B+ tree-based index structures for moving objects. The base structure of the Bx-tree is a B+ tree in which the internal nodes serve as a directory, each containing a pointer to its right sibling. In the earlier version of the Bx-tree, the leaf nodes contained the moving-object locations being indexed and corresponding index time. In the optimized version, each leaf node entry contains the id, velocity, single-dimensional mapping value and the latest update time of the object. The fanout is increased by not storing the locations of moving objects, as these can be derived from the mapping values. As for many other moving objects indexes, a two-dimensional moving object is modeled as a linear function as O = ((x, y), (vx, vy), t ), where (x, y) and (vx, vy) are location and velocity of the object at a given time instance t, i.e., the time of last update. The B+ tree is a structure for indexing single-dimensional data. In order to adopt the B+ tree as a moving object index, the Bx-tree uses a linearization technique which helps to integrate objects' location at time t into single dimensional value. Specifically, objects are first partitioned according to their update time. For objects within the same partition, the Bx-tree stores their locations at a given time which are estimated by linear interpolation. By doing so, the Bx-tree keeps a consistent view of all objects within the same partition without storing the update time of each object. Secondly, the space is partitioned by a grid and the location of an object is linearized within the partitions according to a space-filling curve, e.g., the Peano or Hilbert curves. Finally, with the combination of the partition number (time information) and the linear order (location information), an object is indexed in Bx-tree with a one-dimensional index key Bxvalue: Here index-partition is an index partition determined by the update time and xrep is the space-filling curve value of the object position at the indexed time, denotes the binary value of x, and “+” means concatenation.