Download Efficient k-Nearest Neighbor Search on Moving Object Trajectories

7.1.4
Using the Three Algorithms CTkNN, HCNN, and HCkNN
Each of the three main algorithms compared in the experiments is available as an operator. They
are called knearestfilter and knearest , greeceknearest , and chinaknearest for CTkNN, HCNN, and
HCTkNN, respectively.
As a query object we use train742, which is the first train of line 7 within the field (4, 2) of the 5 x 5
pattern. The dataset considered now can be visualized by translating the underlying UBahn network in
the same way (see Appendix C for an explanation).
1. Create UBahn25 and visualize it:
let UBahn25 = UBahn feed five feed {f1} five feed {f2} product product
projectextend[Name, Typ;
geoData: .geoData translate[30000.0 * .no_f1, 30000.0 * .no_f2],
FieldX: .no_f1,
FieldY: .no_f2]
consume;
query UBahn25
As discussed in Section 6, the Trains25 dataset has about 1.3 million units. It is too large to load
it entirely into the viewer. To be able to interpret the answer of the query, we visualize the trains
moving in field (4, 2) together with the query object, train742.
2. Load trains from field (4, 2) and the query object.
query Trains25 feed filter[(.FieldX = 4) and (.FieldY = 2)] consume;
query train742
3. Find the 5 closest trains to train742 within data set Trains25, using TCkNN. We proceed in two
steps to display first the candidates found in the filter step, using operator knearestfilter , and then
the complete solution.
query UnitTrains25_UTrip UnitTrains25
UnitTrains25Cover_RecId UnitTrains25Cover
knearestfilter[UTrip, train742, 5] consume;
query UnitTrains25_UTrip UnitTrains25
UnitTrains25Cover_RecId UnitTrains25Cover
knearestfilter[UTrip, train742, 5]
knearest[UTrip, train742, 5] consume;
The arguments to knearestfilter are the R-tree index and the indexed relation, then the B-tree index
on the relation with coverage numbers and this relation, finally (in the square brackets) the attribute
name, the query trajectory, an the number k.
4. Find the 5 closest trains to train742 within data set Trains25, using HCNN.
query UTOrdered_RTreeBulk25 UTOrdered25
greeceknearest[UTrip, train742, 5] consume;
Arguments are the R-tree and the unit relation, clustered in the same way.
5. Find the 5 closest trains to train742 within data set Trains25, using HCkNN.
query UnitTrains_UTrip_tbtree25 UnitTrains25C
chinaknearest[UTrip, train742, 5] consume;
Arguments are the TB-tree and the unit relation. Here units are ordered by train objects.
30