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. Candidate cells are all non-empty cells that may include the answer to a RkNN query if the actual coordinate of points in them become available. 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) (c) 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. Influence cells for every candidate cell is the set of all non-empty cells that do not prune candidate cells, however, if the actual coordinate of points in them are realized, they may prune the points in the candidate cell. 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].