Abstract
| Original language | English |
|---|---|
| Journal | Proceedings of the VLDB Endowment |
| Volume | 10 |
| Issue number | 7 |
| Pages (from-to) | 769-780 |
| ISSN | 2150-8097 |
| DOIs | |
| Publication status | Published - 2017 |
| Event | 43rd International Conference on Very Large Data Bases - Technical University of Munich, Munich, Germany Duration: 28. Aug 2017 → 1. Sep 2017 Conference number: 43 |
Conference
| Conference | 43rd International Conference on Very Large Data Bases |
|---|---|
| Number | 43 |
| Location | Technical University of Munich |
| Country | Germany |
| City | Munich |
| Period | 28/08/2017 → 01/09/2017 |
Fingerprint
Cite this
}
Dimensional testing for reverse k-nearest neighbor search. / Casanova, Guillaume; Englmeier, Elias; Houle, Michael E.; Kröger, Peer; Nett, Michael; Schubert, Erich; Zimek, Arthur.
In: Proceedings of the VLDB Endowment, Vol. 10, No. 7, 2017, p. 769-780.Research output: Contribution to journal › Conference article › Research › peer-review
TY - GEN
T1 - Dimensional testing for reverse k-nearest neighbor search
AU - Casanova, Guillaume
AU - Englmeier, Elias
AU - Houle, Michael E.
AU - Kröger, Peer
AU - Nett, Michael
AU - Schubert, Erich
AU - Zimek, Arthur
PY - 2017
Y1 - 2017
N2 - Given a query object q, reverse k-nearest neighbor (RkNN) search aims to locate those objects of the database that have q among their k-nearest neighbors. In this paper, we propose an approximation method for solving RkNN queries, where the pruning operations and termination tests are guided by a characterization of the intrinsic dimensionality of the data. The method can accommodate any index structure supporting incremental (forward) nearest-neighbor search for the generation and verification of candidates, while avoiding impractically-high preprocessing costs. We also provide experimental evidence that our method significantly outperforms its competitors in terms of the tradeoff between execution time and the quality of the approximation. Our approach thus addresses many of the scalability issues surrounding the use of previous methods in data mining.
AB - Given a query object q, reverse k-nearest neighbor (RkNN) search aims to locate those objects of the database that have q among their k-nearest neighbors. In this paper, we propose an approximation method for solving RkNN queries, where the pruning operations and termination tests are guided by a characterization of the intrinsic dimensionality of the data. The method can accommodate any index structure supporting incremental (forward) nearest-neighbor search for the generation and verification of candidates, while avoiding impractically-high preprocessing costs. We also provide experimental evidence that our method significantly outperforms its competitors in terms of the tradeoff between execution time and the quality of the approximation. Our approach thus addresses many of the scalability issues surrounding the use of previous methods in data mining.
U2 - 10.14778/3067421.3067426
DO - 10.14778/3067421.3067426
M3 - Conference article
VL - 10
SP - 769
EP - 780
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
SN - 2150-8097
IS - 7
ER -