Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Kinetic Reverse k-Nearest Neighbor Problem

verfasst von : Zahed Rahmati, Valerie King, Sue Whitesides

Erschienen in: Combinatorial Algorithms

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Embedding Circulant Networks into Butterfly and Benes Networks
Nächstes Kapitel Efficiently Listing Bounded Length st-Paths
Literatur
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.
Vaidya, P.M.: An O(\(n\log n\)) algorithm for the all-nearest-neighbors problem. Discrete Comput. Geom. 4(2), 101–115 (1989)MATHMathSciNetCrossRef
Metadaten
Titel
Kinetic Reverse k-Nearest Neighbor Problem
verfasst von
Zahed Rahmati
Valerie King
Sue Whitesides
Copyright-Jahr
2015
Buch
Combinatorial Algorithms

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

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

Copyright-Jahr: 2015

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

Premium Partner

    Bildnachweise