page_title: Bx-tree
section_title: Utilizing the B+ tree for moving objects
hierarchical_section_title: Bx-tree / Utilizing the B+ tree for moving objects
caption_attribution_description: English: The structure of the Bx-tree
context_page_description: In computer science, the Bˣ tree is basically a query that is used to update efficient B+ tree-based index structures for moving objects.
context_section_description: 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 Bˣ-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 Bˣ-tree stores their locations at a given time which are estimated by linear interpolation. By doing so, the Bˣ-tree keeps a consistent view of all objects within the same partition without storing the update time of an objects.
  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 Bˣ-tree with a one-dimensional index key Bˣvalue:
  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.
  Given an object O ((7, 2), (-0.1,0.05), 10), tmu = 120, the Bˣvalue for O can be computed as follows.
  O is indexed in partition 0 as mentioned. Therefore, indexpartition = (00)₂.
  O’s position at the label timestamp of partition 0 is (1,5).
  Using Z-curve with order = 3, the Z-value of O, i.e., xrep is (010011)₂.
  Concatenating indexpartition and xrep, Bˣvalue (00010011)₂=19.
  Example O ((0,6), (0.2, -0.3 ),10) and tmu=120 then O's position at the label timestamp of partition: ???
caption: An example of the Bx-tree with the number of index partitions equal to 2 within one maximum update interval tmu. In this example, there are maximum three partitions existing at the same time. After linearization, object locations inserted at time 0 are indexed in partition 0 with label timestamp 0.5 tmu, object locations updated during time 0 to 0.5 tmu are indexed in partition 1 with label timestamp tmu, and so on (as indicated by arrows). As time elapses, repeatedly the first range expires (shaded area), and a new range is appended (dashed line).
exif: {}