nach oben

GeoInformatica

Erschienen in:

01.10.2011

Spatial skyline queries: exact and approximation algorithms

verfasst von: Mu-Woong Lee, Wanbin Son, Hee-Kap Ahn, Seung-won Hwang

Erschienen in: GeoInformatica | Ausgabe 4/2011

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

As more data-intensive applications emerge, advanced retrieval semantics, such as ranking and skylines, have attracted the attention of researchers. Geographic information systems are a good example of an application using a massive amount of spatial data. Our goal is to efficiently support exact and approximate skyline queries over massive spatial datasets. A spatial skyline query, consisting of multiple query points, retrieves data points that are not father than any other data points, from all query points. To achieve this goal, we present a simple and efficient algorithm that computes the correct results, also propose a fast approximation algorithm that returns a desirable subset of the skyline results. In addition, we propose a continuous query algorithm to trace changes of skyline points while a query point moves. To validate the effectiveness and efficiency of our algorithm, we provide an extensive empirical comparison between our algorithms and the best known spatial skyline algorithms from several perspectives.

Vorheriger Artikel Special section on spatial and temporal databases

Nächster Artikel Approximate and exact hybrid algorithms for private nearest-neighbor queries with database protection

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

Available at http://www.cs.fsu.edu/~lifeifei/SpatialDataset.htm

Kung HT, Luccio F, Preparata FP (1975) On finding the maxima of a set of vectors. J ACM 22(4):469–476CrossRef

Börzsönyi S, Kossmann D, Stocker K (2001) The skyline operator. In: ICDE ’01: Proceedings of the 17th international conference on data engineering. Washington, DC, USA. IEEE Computer Society, New York, pp 421–430

Tan K-L, Eng P-K, Ooi BC (2001) Efficient progressive skyline computation. In: VLDB ’01: Proceedings of the 27th international conference on very large data bases. San Francisco, CA, USA. Morgan Kaufmann, San Mateo, pp 301–310

Papadias D, Tao Y, Fu G, Seeger B (2003) An optimal and progressive algorithm for skyline queries. In: SIGMOD ’03: Proceedings of the 2003 ACM SIGMOD international conference on management of data. New York, NY, USA. ACM, New York, pp 467–478

Chomicki J, Godfery P, Gryz J, Liang D (2003) Skyline with presorting. In: ICDE ’03: Proceedings of the 19th international conference on data engineering. IEEE Computer Society, New York, pp 717–816

Sharifzadeh M, Shahabi C (2006) The spatial skyline queries. In: VLDB ’06: Proceedings of the 32nd international conference on very large data bases. VLDB Endowment, pp 751–762

Sharifzadeh M, Shahabi C, Kazemi L (2009) Processing spatial skyline queries in both vector spaces and spatial network databases. ACM Trans Database Syst 34(3):1–45CrossRef

Lin X, Yuan Y, Zhang Q, Zhang Y (2007) Selecting stars: the k most representative skyline operator. In: ICDE ’07: Proceedings of the 23rd international conference on data engineering, pp 86–95

Kossmann D, Ramsak F, Rost S (2002) Shooting stars in the sky: an online algorithm for skyline queries. In: VLDB ’02: Proceedings of the 28th international conference on very large data bases. VLDB Endowment, pp 275–286

10.

Godfrey P, Shipley R, Gryz J (2005) Maximal vector computation in large data sets. In VLDB ’05: Proceedings of the 31st international conference on very large data bases. VLDB Endowment, pp 229–240

11.

Chan CY, Jagadish HV, Tan K-L, Tung AKH, Zhang Z (2006) On high dimensional skylines. In: EDBT ’06: Proceedings of the 10th international conference on extending database technology, pp 478–495

12.

Chan C-Y, Jagadish HV, Tan K-L, Tung AKH, Zhang Z (2006) Finding k-dominant skylines in high dimensional space. In: SIGMOD ’06: Proceedings of the 2006 ACM SIGMOD international conference on management of data. New York, NY, USA. ACM, New York, pp 503–514

13.

Huang Z, Lu H, Ooi BC, Tung AKH (2006) Continuous skyline queries for moving objects. IEEE Trans Knowl Data Eng 18(12):1645–1658CrossRef

14.

Lee M-W, Hwang S-w (2009) Continuous skylining on volatile moving data. In: ICDE ’09: Proceedings of the 2009 IEEE international conference on data engineering. Washington, DC, USA. IEEE Computer Society, New York, pp 1568–1575

15.

Roussopoulos N, Kelley S, Vincent F (1995) Nearest neighbor queries. SIGMOD Rec 24(2):71–79CrossRef

16.

Berchtold S, Böhm C, Keim DA, Kriegel H-P (1997) A cost model for nearest neighbor search in high-dimensional data space. In: PODS ’97: Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems. New York, NY, USA. ACM, New York, pp 78–86

17.

Beyer KS, Goldstein J, Ramakrishnan R, Shaft U (1999) When is “nearest neighbor” meaningful? In: ICDT ’99: Proceedings of the 7th international conference on database theory. London, UK. Springer, Berlin, pp 217–235

18.

Song Z, Roussopoulos N (2001) K-nearest neighbor search for moving query point. In: SSTD ’01: Proceedings of the 7th international symposium on advances in spatial and temporal databases. London, UK. Springer, Berlin, pp 79–96

19.

Benetis R, Jensen CS, Karciauskas G, Saltenis S (2002) Nearest neighbor and reverse nearest neighbor queries for moving objects. In: IDEAS ’02: Proceedings of the 2002 international symposium on database engineering & applications. Washington, DC, USA. IEEE Computer Society, New York, pp 44–53

20.

Tao Y, Papadias D, Shen Q (2002) Continuous nearest neighbor search. In: VLDB ’02: Proceedings of the 28th international conference on very large data bases. VLDB Endowment, pp 287–298

21.

Raptopoulou K, Papadopoulos AN, Manolopoulos Y (2003) Fast nearest-neighbor query processing in moving-object databases. Geoinformatica 7(2):113–137CrossRef

22.

Papadias D, Tao Y, Mouratidis K, Hui CK (2005) Aggregate nearest neighbor queries in spatial databases. ACM Trans Database Syst 30(2):529–576CrossRef

23.

Huang X, Jensen CS (2004) In-route skyline querying for location-based services. In: Proceedings of the international workshop on web and wireless geographical information systems (W2GIS), pp 120–135

24.

de Berg M, Cheong O, van Kreveld M, Overmars M (2008) Computational geometry: algorithms and applications, 3rd edn. Springer, Berlin

25.

Bentley JL, Kung HT, Schkolnick M, Thompson CD (1978) On the average number of maxima in a set of vectors and applications. J ACM 25(4):536–543CrossRef

26.

Rockafellar RT (1996) Convex analysis. Princeton University Press, Princeton

27.

Matoušek J (2002) Lectures on discrete geometry. Springer, Berlin

28.

Barber B (1995) Qhull code for convex hull, delaunay triangulation, voronoi diagram, and halfspace intersection about a point. http://www.qhull.org/

29.

Beckmann N, Kriegel H-P, Schneider R, Seeger B (1990) The r*-tree: an efficient and robust access method for points and rectangles. SIGMOD Rec 19(2):322–331CrossRef

30.

Klee V (1980) On the complexity of d-dimensional Voronoi diagrams. Arch Math 34:75–80CrossRef

31.

Chazelle B (1991) An optimal convex hull algorithm and new results on cuttings (extended abstract). In: SFCS ’91: Proceedings of the 32nd annual symposium on foundations of computer science. Washington, DC, USA. IEEE Computer Society, New York, pp 29–38

32.

Clarkson KL, Shor PW (1989) Applications of random sampling in computational geometry, II. Discrete Comput Geom 4(5):387–421CrossRef

33.

Seidel R (1991) Small-dimensional linear programming and convex hulls made easy. Discrete Comput Geom 6(5):423–434CrossRef

Titel: Spatial skyline queries: exact and approximation algorithms
verfasst von: Mu-Woong Lee
Wanbin Son
Hee-Kap Ahn
Seung-won Hwang
Publikationsdatum: 01.10.2011
Verlag: Springer US
Erschienen in: GeoInformatica / Ausgabe 4/2011
Print ISSN: 1384-6175
Elektronische ISSN: 1573-7624
DOI: https://doi.org/10.1007/s10707-010-0119-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2011

Ontology-driven discovery of geospatial evidence in web pages

Approximate and exact hybrid algorithms for private nearest-neighbor queries with database protection

Representing topological relationships for spatiotemporal objects

MOVIES: indexing moving objects by shooting index images

Editing and versioning for high performance network models in a multiuser environment

Special section on spatial and temporal databases