Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2018 | Supplement | Buchkapitel

Nearest Neighborhood Determination Methods with Regard to Mobile Location-Based Application

share
TEILEN

Abstract

The paper concerns nearest neighborhood determination issues. The main goal is to investigate and compare characteristics of popular solutions with regard to applying them to location-based services for mobile devices. Mainly the impact of number of objects and object’s mobility on performance is considered. Also the accuracy dependent on search range was tested. The paper takes into account three groups of approaches: brute-force based solutions, spatial tree structures, and solutions that use Geohash for location encoding. Described simulation experiments was performed for eight popular algorithms and one own approach. The results show very diverse properties of all algorithms and its usefulness for considered area of application.
Literatur
1.
Zurück zum Zitat Malm, A.: Mobile Location-Based Services, 9th edn. Berg Insight AB (2015) Malm, A.: Mobile Location-Based Services, 9th edn. Berg Insight AB (2015)
2.
Zurück zum Zitat Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proceedings of ACM Management of Data (SIGMOD), pp. 47–57 (1984) Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proceedings of ACM Management of Data (SIGMOD), pp. 47–57 (1984)
3.
Zurück zum Zitat Vincenty, T.: Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations (1975) Vincenty, T.: Direct and inverse solutions of geodesics on the ellipsoid with application of nested equations (1975)
4.
Zurück zum Zitat Great Britain: Ministry of Defence, Admiralty Manual of Navigation, vol. 1. Stationery Office, London (1997) Great Britain: Ministry of Defence, Admiralty Manual of Navigation, vol. 1. Stationery Office, London (1997)
6.
Zurück zum Zitat Finkel, R.A., Bentley, J.L.: Quad trees a data structure for retrieval on composite keys. Acta Informatica 4(1), 1–9 (1974). Springer, New York CrossRefMATH Finkel, R.A., Bentley, J.L.: Quad trees a data structure for retrieval on composite keys. Acta Informatica 4(1), 1–9 (1974). Springer, New York CrossRefMATH
7.
Zurück zum Zitat Hjaltason, G.R., Samet, H.: Speeding up construction of PMR quadtree-based spatial indexes. VLDB J. 11(2), 109–137 (2002) CrossRef Hjaltason, G.R., Samet, H.: Speeding up construction of PMR quadtree-based spatial indexes. VLDB J. 11(2), 109–137 (2002) CrossRef
8.
Zurück zum Zitat Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings, SODA 1997. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, pp. 360–369 (1997) Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings, SODA 1997. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, pp. 360–369 (1997)
9.
Zurück zum Zitat Sedgewick, R., Wayne, K.: Algorithms, 4th edn. Addison-Wesley, Boston (2011) Sedgewick, R., Wayne, K.: Algorithms, 4th edn. Addison-Wesley, Boston (2011)
Metadaten
Titel
Nearest Neighborhood Determination Methods with Regard to Mobile Location-Based Application
verfasst von
Mariusz Fraś
Piotr Frącek
Krzysztof Waśko
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-67220-5_32

Premium Partner