Paper Info

Title | ||
---|---|---|

Compact distance histogram: a novel structure to boost k-nearest neighbor queries |

Abstract | ||
---|---|---|

The k-Nearest Neighbor query (k-NNq) is one of the most useful similarity queries. Elaborated k-NNq algorithms depend on an initial radius to prune regions of the search space that cannot contribute to the answer. Therefore, estimating a suitable starting radius is of major importance to accelerate k-NNq execution. This paper presents a new technique to estimate a tight initial radius. Our approach, named CDH-kNN, relies on Compact Distance Histograms (CDHs), which are pivot-based histograms defined as piecewise linear functions. Such structures approximate the distance distribution and are compressed according to a given constraint, which can be a desired number of buckets and/or a maximum allowed error. The covering radius of a k-NNq is estimated based on the relationship between the query element and the CDHs' joint frequencies. The paper presents a complete specification of CDH-kNN, including CDH's construction and radii estimation. Extensive experiments on both real and synthetic datasets highlighted the efficiency of our approach, showing that it was up to 72% faster than existing algorithms, outperforming every competitor in all the setups evaluated. In fact, the experiments showed that our proposal was just 20% slower than the theoretical lower bound. |

Year | DOI | Venue |
---|---|---|

2015 | 10.1145/2791347.2791359 | International Conference on Scientific and Statistical DB Management |

Keywords | Field | DocType |

k-Nearest Neighbor Query, Query Optimization, Selectivity Estimation, Histograms | k-nearest neighbors algorithm,Query optimization,Data mining,Histogram,Upper and lower bounds,Computer science,Theoretical computer science,Radius,Piecewise linear function,Database | Conference |

Citations | PageRank | References |

1 | 0.34 | 7 |

Authors | ||

4 |

Authors (4 rows)

Cited by (1 rows)

References (7 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Marcos Vinicius Naves Bedo | 1 | 36 | 7.37 |

Daniel S. Kasterz | 2 | 8 | 3.22 |

Agma J. M. Traina | 3 | 1024 | 153.61 |

Caetano Traina Jr. | 4 | 1052 | 137.26 |