Pruning Algorithm Sample Clauses

Pruning Algorithm. The cells that need to be retrieved from the server after pruning consists of 1) can- didate cells which may include the RkNN answers, and 2) influence cells for each candidate cell in order to verify if the points in the candidate cells are indeed the RkNN answers. We describe in detail below how to compute the candidate cells and influence cells for each candidate cell. As illustrated in Figure 4.8, our pruning phase accesses the cells around the query in clockwise order and checks each cell against a set of candidate cells to see whether (a) (b) Figure 4.9: Computing influence cells for the candidate cell < 5, 4 > they are pruned (line 7-25 of the Algorithm 3). At the beginning, the candidate set CNDc is empty or includes the query cell Q if it is non-empty. As pruning phase continues, any cell which is not pruned k times by candidate cells is added to the set. We keep track of the number of times a cell is pruned by incorporating the number of data points in pruning cells. It means, if a candidate cell cnd which has 3 points prunes c with regard to the query q, we record c is pruned 3 times (c.pruned = 3). If all of the cells in a layer around the query are pruned k times, the search stops, otherwise, pruning phase continues to assess upper layers. After retrieving all of candidate cells, the pruning phase is continued by computing influence cells. We compute a set of influence cells INFc for every candidate cell cnd as follows. First, we probe the cells around cnd and retrieve every cell c that does not prune the candidate cell, but satisfies the following condition [65]. 1) We add c to a set called INF1. This means, c may include points which are closer to q compared to cnd. Figure 4.9a illustrates the cells in INF1 for the candidate cell cnd =< 5, 4 > when k = 1. It can be easily computed as the area surrounding the cell < 5, 4 > with distance Maxdist1 from every possible point in the cell where Maxdist1 = MaxDist(q, cnd). While INF1 assures the inclusion of all possible influence cells [65], it might be redundant in certain situations. To further refine the influence cells, we can remove any influence cell that does not belong to the possible set of kNN neighbors of the cell cnd. In other words, any cell c that doesn’t satisfy the following condition cannot be an influence cell for cnd. max(MaxDist(r, cnd)) < MinDist(c, cnd) (4.2) X r2R and r.count ≥ k r2R which means there are a subset of cells R which are all closer to the candidate cell cnd comp...