GHT Family

GHT

Overview

Generalized Hyperplane tree (GHT) is a binary tree built recursively by using generalized partitioning technique. An example of GHT is illustrated in Fig. 1. Each node contain two objects, where only leaf nodes can contain one object. Objects c1 and c2 in the node denote the centers of two subtrees. More specifically, if an object o is closer to c1, then o is distributed to the sub node whose center is c1, and vice versa.

GHT.jpg

Fig. 1 Examle of GHT

Code Usage

Usage: [dataFile] [queryFile] [costFile]

Example: synthetic.txt synthetic_query_id.txt GHT-synthetic-cost.txt

  • dataFile: the path of source data file
  • queryFile: the path of input query data file
  • costFile: the path to store the running cost
Download source code
GNAT

Overview

GHT can be generalized to m-ary trees, yielding Generalized Near-Neighbor Access Tree (GNAT). An example of GNAT is depicted in Fig. 2. Each time, m centers ci (1 ≤ i ≤ m) are selected, and objects are distributed to the nearest center, resulting in m sub partitions/nodes Pi (1 ≤ i ≤ m), i.e., for any o ∈ Pi satisfying d(o, ci) ≤ d(o, cj). In addition, GNAT stores the minimum bounding box MBBij = [mindist(o, cj), maxdist(o, cj)] (o ∈ Pi) of each partition Pi with respect to m centers cj, which can help pruning during the search. The MBB information of GNAT is shown in Fig 2(b), where red circles denote the MBB information w.r.t. the center o1, the purple circles denote the MBB information w.r.t. the center o6, while the blue circle denotes the MBB information w.r.t. the center o9. In this example, the second partition P2 only contains data o7, and thus, the MBB information is omitted in the figure.

GNAT-a.jpg

(a) Index Structure

 GNAT-b.jpg

(b) MBB information

Fig. 2 Example of GNAT

Code Usage

Usage: [dataFile] [queryFile] [costFile] [height]

Example: synthetic.txt synthetic_query_id.txt GNAT-synthetic-cost.txt 9

  • dataFile: the path of source data file
  • queryFile: the path of input query data file
  • costFile: the path to store the running cost
  • height: the height of the tree (we limit the tree-height for fair comparison, which is not necessary for normal use.)
Download source code
EGNAT

Overview

Evolutionary Geometric Near-neighbor Access Tree (EGNAT) is a dynamic version of GNAT, with an example shown in Fig. 3. It provides the insertion and deletion operations, as well as extends the main-memory index to the external index. In addition, to further improve the pruning ability, different GNAT, each entry in the leaf nodes of EGNAT stores the distance to the parent entry (i.e., the center) of the corresponding leaf node.

EGNAT.jpg

Fig. 3 Example of EGNAT

Code Usage

Usage: [dataFile] [queryFile] [costFile] [blockSize]

Example: LA.txt LA_query.txt EGNAT-LA-cost.txt 4096

  • dataFile: the path of source data file
  • queryFile: the path of input query data file
  • costFile: the path to store the running cost
  • blockSize: the size of block to store the EGNAT node and the unit of size is KB
Download source code