Dimensional testing for reverse k-nearest neighbor search

Guillaume Casanova, Elias Englmeier, Michael E. Houle, Peer Kröger, Michael Nett, Erich Schubert, Arthur Zimek

Publikation: Bidrag til tidsskriftKonferenceartikelForskningpeer review

94 Downloads (Pure)

Resumé

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.
OriginalsprogEngelsk
TidsskriftProceedings of the VLDB Endowment
Vol/bind10
Udgave nummer7
Sider (fra-til)769-780
ISSN2150-8097
DOI
StatusUdgivet - 2017
Begivenhed43rd International Conference on Very Large Data Bases - Technical University of Munich, Munich, Tyskland
Varighed: 28. aug. 20171. sep. 2017
Konferencens nummer: 43

Konference

Konference43rd International Conference on Very Large Data Bases
Nummer43
LokationTechnical University of Munich
LandTyskland
ByMunich
Periode28/08/201701/09/2017

Fingeraftryk

Testing
Data mining
Scalability
Costs
Nearest neighbor search

Citer dette

Casanova, G., Englmeier, E., Houle, M. E., Kröger, P., Nett, M., Schubert, E., & Zimek, A. (2017). Dimensional testing for reverse k-nearest neighbor search. Proceedings of the VLDB Endowment, 10(7), 769-780. https://doi.org/10.14778/3067421.3067426
Casanova, Guillaume ; Englmeier, Elias ; Houle, Michael E. ; Kröger, Peer ; Nett, Michael ; Schubert, Erich ; Zimek, Arthur. / Dimensional testing for reverse k-nearest neighbor search. I: Proceedings of the VLDB Endowment. 2017 ; Bind 10, Nr. 7. s. 769-780.
@inproceedings{d3089f072d774e859389f3960f955248,
title = "Dimensional testing for reverse k-nearest neighbor search",
abstract = "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.",
author = "Guillaume Casanova and Elias Englmeier and Houle, {Michael E.} and Peer Kr{\"o}ger and Michael Nett and Erich Schubert and Arthur Zimek",
year = "2017",
doi = "10.14778/3067421.3067426",
language = "English",
volume = "10",
pages = "769--780",
journal = "Proceedings of the VLDB Endowment",
issn = "2150-8097",
publisher = "VLDB Endowment",
number = "7",

}

Casanova, G, Englmeier, E, Houle, ME, Kröger, P, Nett, M, Schubert, E & Zimek, A 2017, 'Dimensional testing for reverse k-nearest neighbor search', Proceedings of the VLDB Endowment, bind 10, nr. 7, s. 769-780. https://doi.org/10.14778/3067421.3067426

Dimensional testing for reverse k-nearest neighbor search. / Casanova, Guillaume; Englmeier, Elias; Houle, Michael E.; Kröger, Peer; Nett, Michael; Schubert, Erich; Zimek, Arthur.

I: Proceedings of the VLDB Endowment, Bind 10, Nr. 7, 2017, s. 769-780.

Publikation: Bidrag til tidsskriftKonferenceartikelForskningpeer 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 -

Casanova G, Englmeier E, Houle ME, Kröger P, Nett M, Schubert E et al. Dimensional testing for reverse k-nearest neighbor search. Proceedings of the VLDB Endowment. 2017;10(7):769-780. https://doi.org/10.14778/3067421.3067426