skip to main content
10.1145/1516360.1516462acmotherconferencesArticle/Chapter ViewAbstractPublication PagesedbtConference Proceedingsconference-collections
research-article
Free access

Reverse k-nearest neighbor search in dynamic and general metric databases

Published: 24 March 2009 Publication History

Abstract

In this paper, we propose an original solution for the general reverse k-nearest neighbor (RkNN) search problem. Compared to the limitations of existing methods for the RkNN search, our approach works on top of any hierarchically organized tree-like index structure and, thus, is applicable to any type of data as long as a metric distance function is defined on the data objects. We will exemplarily show how our approach works on top of the most prevalent index structures for Euclidean and metric data, the R-Tree and the M-Tree, respectively. Our solution is applicable for arbitrary values of k and can also be applied in dynamic environments where updates of the database frequently occur. Although being the most general solution for the RkNN problem, our solution outperforms existing methods in terms of query execution times because it exploits different strategies for pruning false drops and identifying true hits as soon as possible.

References

[1]
E. Achtert, C. Böhm, P. Kröger, P. Kunath, A. Pryakhin, and M. Renz. Approximate reverse k-nearest neighbor search in general metric spaces. In Proc. CIKM, 2006.
[2]
E. Achtert, C. Böhm, P. Kröger, P. Kunath, A. Pryakhin, and M. Renz. Efficient reverse k-nearest neighbor search in arbitrary metric spaces. In Proc. SIGMOD, 2006.
[3]
E. Achtert, C. Böhm, P. Kröger, P. Kunath, A. Pryakhin, and M. Renz. Efficient reverse k-nearest neighbor estimation. In Proc. BTW, 2007.
[4]
N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-Tree: An efficient and robust access method for points and rectangles. In Proc. SIGMOD, pages 322--331, 1990.
[5]
P. Ciaccia, M. Patella, and P. Zezula. M-Tree: an efficient access method for similarity search in metric spaces. In Proc. VLDB, 1997.
[6]
A. Guttman. R-Trees: A dynamic index structure for spatial searching. In Proc. SIGMOD, pages 47--57, 1984.
[7]
F. Korn and S. Muthukrishnan. Influenced sets based on reverse nearest neighbor queries. In Proc. SIGMOD, 2000.
[8]
I. Lazaridis and S. Mehrotra. Progressive approximate aggregate queries with a multi-resolution tree structure. In Proc. SIGMOD, 2001.
[9]
D. Papadias, P. Kalnis, J. Zhang, and Y. Tao. Efficient olap operations in spatial data warehouses. In Proc. SSTD, 2001.
[10]
N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data, San Jose, California, United States, pages 71--79, 1995.
[11]
A. Singh, H. Ferhatosmanoglu, and A. S. Tosun. High dimensional reverse nearest neighbor queries. In Proc. CIKM, 2003.
[12]
I. Stanoi, D. Agrawal, and A. E. Abbadi. Reverse nearest neighbor queries for dynamic databases. In Proc. DMKD, 2000.
[13]
Y. Tao, D. Papadias, and X. Lian. Reverse kNN search in arbitrary dimensionality. In Proc. VLDB, 2004.
[14]
Y. Tao, M. L. Yiu, and N. Mamoulis. Reverse nearest neighbor search in metric spaces. IEEE TKDE, 18(9):1239--1252, 2006.
[15]
C. Yang and K.-I. Lin. An index structure for efficient reverse nearest neighbor queries. In Proc. ICDE, 2001.

Cited By

View all
  • (2023)Distance, Origin and Category Constrained PathsACM Transactions on Spatial Algorithms and Systems10.1145/35966019:3(1-27)Online publication date: 23-Jun-2023
  • (2023)Network Monitoring on Multi-Pipe SwitchesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35793217:1(1-31)Online publication date: 2-Mar-2023
  • (2021)Optimal school site selection in Urban areas using deep neural networksJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-021-02903-913:1(313-327)Online publication date: 6-Feb-2021
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
EDBT '09: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology
March 2009
1180 pages
ISBN:9781605584225
DOI:10.1145/1516360
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 March 2009

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Conference

EDBT/ICDT '09
EDBT/ICDT '09: EDBT/ICDT '09 joint conference
March 24 - 26, 2009
Saint Petersburg, Russia

Acceptance Rates

Overall Acceptance Rate 7 of 10 submissions, 70%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)76
  • Downloads (Last 6 weeks)23
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Distance, Origin and Category Constrained PathsACM Transactions on Spatial Algorithms and Systems10.1145/35966019:3(1-27)Online publication date: 23-Jun-2023
  • (2023)Network Monitoring on Multi-Pipe SwitchesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35793217:1(1-31)Online publication date: 2-Mar-2023
  • (2021)Optimal school site selection in Urban areas using deep neural networksJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-021-02903-913:1(313-327)Online publication date: 6-Feb-2021
  • (2021)Computing reverse nearest neighbourhood on road mapsWorld Wide Web10.1007/s11280-021-00969-1Online publication date: 23-Nov-2021
  • (2020)Approval Voting and Incentives in CrowdsourcingACM Transactions on Economics and Computation10.1145/33968638:3(1-40)Online publication date: 22-Jun-2020
  • (2020)Safe Regions for Moving Reverse Neighbourhood Queries in a Peer-to-Peer EnvironmentIEEE Access10.1109/ACCESS.2020.29794328(50285-50298)Online publication date: 2020
  • (2020)Reverse Spatial Visual Top-$k$ QueryIEEE Access10.1109/ACCESS.2020.29689828(21770-21787)Online publication date: 2020
  • (2019)k-Distance Approximation for Memory-Efficient RkNN RetrievalSimilarity Search and Applications10.1007/978-3-030-32047-8_6(57-71)Online publication date: 23-Sep-2019
  • (2018)Reverse Approximate Nearest Neighbor QueriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2017.276606530:2(339-352)Online publication date: 1-Feb-2018
  • (2018)Density-based reverse nearest neighbourhood search in spatial databasesJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-018-1103-xOnline publication date: 30-Oct-2018
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media