Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Kinetic Reverse k-Nearest Neighbor Problem

Authors : Zahed Rahmati, Valerie King, Sue Whitesides

Published in: Combinatorial Algorithms

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper provides the first solution to the kinetic reverse k-nearest neighbor (R\(k\)NN) problem in \(\mathbb {R}^d\), which is defined as follows: Given a set P of n moving points in arbitrary but fixed dimension d, an integer k, and a query point \(q\notin P\) at any time t, report all the points \(p\in P\) for which q is one of the k-nearest neighbors of p.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Embedding Circulant Networks into Butterfly and Benes Networks
next chapter Efficiently Listing Bounded Length st-Paths
Literature
1.
2.
Agarwal, P.K., Kaplan, H., Sharir, M.: Kinetic and dynamic data structures for closest pair and all nearest neighbors. ACM Trans. Algorithms 5(4), 1–37 (2008)MathSciNet
3.
Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J. ACM 45(6), 891–923 (1998)MATHMathSciNetCrossRef
4.
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer-Verlag TELOS, Santa Clara (2008)CrossRef
5.
Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to \(k\)-nearest-neighbors and \(n\)-body potential fields. J. ACM 42(1), 67–90 (1995)MATHMathSciNetCrossRef
6.
Chan, T.M.: On levels in arrangements of curves, ii: A simple inequality and its consequences. Discrete Comput. Geom. 34(1), 11–24 (2005)MATHMathSciNetCrossRef
7.
Chan, T.M.: On levels in arrangements of curves, iii: further improvements. In: Proceedings of the 24th annual Symposium on Computational Geometry (SoCG 2008), pp. 85–93. ACM, New York (2008)
8.
Cheema, M.A., Zhang, W., Lin, X., Zhang, Y., Li, X.: Continuous reverse k nearest neighbors queries in euclidean space and in spatial networks. VLDB J. 21(1), 69–95 (2012)CrossRef
9.
Cheong, O., Vigneron, A., Yon, J.: Reverse nearest neighbor queries in fixed dimension. Int. J. Comput. Geom. Appl. 21(02), 179–188 (2011)MATHMathSciNetCrossRef
10.
Clarkson, K.L.: Fast algorithms for the all nearest neighbors problem. In: Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983), pp. 226–232. IEEE Computer Society, Washington, DC (1983)
11.
Connor, M., Kumar, P.: Fast construction of \(k\)-nearest neighbor graphs for point clouds. IEEE Trans. Vis. Comput. Graph. 16(4), 599–608 (2010)CrossRef
12.
Dickerson, M.T., Eppstein, D.: Algorithms for proximity problems in higher dimensions. Int. J. Comput. Geom. Appl. 5(5), 277–291 (1996)MATHMathSciNetCrossRef
13.
Korn, F., Muthukrishnan, S.: Influence sets based on reverse nearest neighbor queries. In: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (SIGMOD 2000), pp. 201–212. ACM, New York (2000)
14.
Maheshwari, A., Vahrenhold, J., Zeh, N.: On reverse nearest neighbor queries. In: Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), pp. 128–132 (2002)
15.
16.
Rahmati, Z., Abam, M.A., King, V., Whitesides, S.: Kinetic data structures for the Semi-Yao graph and all nearest neighbors in \(\mathbb{R}^d\). In: Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG 2014) (2014)
17.
Rahmati, Z., Abam, M.A., King, V., Whitesides, S., Zarei, A.: A simple, faster method for kinetic proximity problems. Comput. Geom. 48(4), 342–359 (2015)MathSciNetCrossRef
18.
Metadata
Title
Kinetic Reverse k-Nearest Neighbor Problem
Authors
Zahed Rahmati
Valerie King
Sue Whitesides
Copyright Year
2015
Book
Combinatorial Algorithms

Print ISBN: 978-3-319-19314-4

Electronic ISBN: 978-3-319-19315-1

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-19315-1_27

Premium Partner

    Image Credits