SPB-Tree

Overview

The SPB-tree utilizes the two-stage mapping, i.e., the pivot mapping and the space-filling curve (SFC) mapping, to map objects into SFC values (i.e., integers) while (to some extent) maintaining spatial proximity. Then, a B+-tree is used to store the SFC values. Fig. 1 depicts an example of SPB-tree, where Fig. 1(b) illustrates the pivot mapping and Hilbert curve mapping. Each non-leaf entry e stores the SFC values min and max for ⟨ a1, a2, …, an⟩ and ⟨b1, b2, …, bn⟩ to represent the left-bottom and right-top points of its minimum bounding box e.MBB = {[ai,bi]| 1≤i≤n}.

SPBTree-a.jpg

(a) SPB-tree Structure
SPBTree-b.jpg

(b) Pivot mapping and Hilbert curve mapping

Fig. 1 Example of SPB-tree

Code Usage

Usage: [dataFile] [pname] [indexFile] [costFile] [maxDistance] [pivotNumber] [blockSize] [queryFile]

Example: LA.txt pivot_all_LA.txt spb-index-file spb-cost.txt 25000 5 4096 LA_query.txt

  • dataFile: the path of source data file
  • pname: the path of pivot file
  • indexFile: the path to store the generated index file
  • costFile: the path to store the running cost
  • maxDistance: the max distance between objects in source data
  • pivotNumber: the number of pivots
  • blockSize: the size of block that stores the node of B+-Tree and the unit of size is KB
  • queryFile: the path of input query data file
Download source code