nach oben

World Wide Web

Erschienen in:

01.11.2016

Efficient group-by reverse skyline computation

verfasst von: Zonghui Wang, Yunjun Gao, Qing Liu, Xiaoye Miao, Qing Li, Chuan Li

Erschienen in: World Wide Web | Ausgabe 6/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The reverse skyline query is very useful in many decision making applications. Given a multi-dimensional dataset P and a query point q, the reverse skyline query returns all the points in P whose dynamic skyline contains q. Although the reverse skyline retrieval has been well-studied in the literature, there is, to the best of our knowledge, no prior work on one of the most intuitive and practical types of reverse skyline queries, namely, group-by reverse skyline (GRS) query, which retrieves the reverse skyline for each group in a specified dataset. We formalize the GRS query including monochromatic and bichromatic versions, and identify its properties, and then propose a set of efficient algorithms for computing the group-by reverse skyline. Extensive experimental evaluation using both real and synthetic datasets demonstrates the performance of our proposed algorithms in terms of effectiveness and efficiency under a variety of experimental settings.

Vorheriger Artikel RMACO :a randomly matched parallel ant colony optimization

Nächster Artikel Scalable and efficient processing of top-k multiple-type integrated queries

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

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

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

Bartolini, I., Ciaccia, P., Patella, M.: Efficient sort-based skyline evaluation. ACM Trans. Database Syst. 33(4), 1–45 (2008)CrossRef

Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The R*-tree: An efficient and robust access method for points and rectangles. In: SIGMOD, pp. 322–331 (1990)

Borzsonyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: ICDE, pp. 421–430 (2001)

Chen, L., Lian, X.: Dynamic skyline queries in metric spaces. In: EDBT, pp. 333–343 (2008)

Chomicki, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with presorting. In: ICDE, pp. 717–719 (2003)

Dellis, E., Seeger, B.: Efficient computation of reverse skyline queries. In: VLDB, pp. 291–302 (2007)

Dellis, E., Vlachou, A., Vladimirskiy, I., Seeger, B., Theodoridis, Y.: Constrained subspace skyline computation. In: CIKM, pp. 415–424 (2006)

Fuhry, D., Jin, R., Zhang, D.: Efficient skyline computation in metric space. In: EDBT, pp. 1042–1051 (2009)

Gao, Y., Liu, Q., Zheng, B., Chen, G.: On efficient reverse skyline query processing. Expert Syst. Appl. 41(7), 3237–3249 (2014)CrossRef

10.

Godfrey, P., Shipley, R., Gryz, J.: Maximal vector computation in large data sets. In: VLDB, pp. 229–240 (2005)

11.

Huang, Z., Lu, H., Ooi, B.C., Tung, A.K.H.: Continuous skyline queries for moving objects. TKDE 18(12), 1645–1658 (2006)

12.

Huang, Z., Wang, W.: A novel incremental maintenance algorithm of skycube. In: DEXA, pp. 781–790 (2006)

13.

Huang, Z., Xiang, Y., Zhang, B., Liu, X.: A clustering based approach for skyline diversity. Expert Syst. Appl. 38, 7984–7993 (2011)CrossRef

14.

Im, H., Park, S.: Group skyline computation. Inform. Sci. 188, 151–169 (2012)MathSciNetCrossRefMATH

15.

Jiang, T., Gao, Y., Zhang, B., Lin, D., Li, Q.: Monochromatic and bichromatic mutual skyline queries. Expert Syst. Appl. 41(4), 1885–1900 (2014)CrossRef

16.

Kossmann, D., Ramsak, F., Rost, S.: Shooting stars in the sky: An online algorithm for skyline queries. In: VLDB, pp. 275–286 (2002)

17.

Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. ACM 22(4), 469–476 (1975)MathSciNetCrossRefMATH

18.

Lee, J., Hwang, S. Qskycube: Efficient skycube computation using point-based space partitioning. In: VLDB, 185–196 (2010)

19.

Lee, M.-W., Hwang, S.-W.: Continuous skylining on volatile moving data. In: ICDE, pp. 1568–1575 (2009)

20.

Lee, K.C.K., Zheng, B., Li, H., Lee, W.-C.: Approaching the skyline in z order. In: VLDB, pp. 279–290 (2007)

21.

Lian, X., Chen, L.: Reverse skyline search in uncertain databases. ACM Trans. Database Syst. 35(1), 3 (2010)CrossRef

22.

Lin, X., Yuan, Y., Wang, W., Lu, H.: Stabbing the sky: Efficient skyline computation over sliding windows. In: ICDE, pp. 502–513 (2005)

23.

Liu, Q., Gao, Y., Chen, G., Li, Q., Jiang, T.: On efficient reverse k-skyband query processing. In: DASFAA, pp. 544–559 (2012)

24.

Lu, Y., Zhao, J., Chen, L., Cui, B., Yang, D.: Effective skyline cardinality estimation on data streams. In: DEXA, pp. 241–254 (2008)

25.

Luk, M., Yiu, M., Lo, E.: Group-by skyline query processing in relational engines. In: CIKM, pp. 1433–1436 (2009)

26.

Morse, M., Patel, J.M., Grosky, W.I.: Efficient continuous skyline computation. Inform. Sci. 177(17), 3411–3437 (2007)MathSciNetCrossRef

27.

Papadias, D., Tao, Y., Fu, G., Seeger, B.: Progressive skyline computation in database systems. ACM Trans. Database Syst. 30(1), 41–82 (2005)CrossRef

28.

Pei, J., Jiang, B., Lin, X., Yuan, Y.: Probabilistic skylines on uncertain data. In: VLDB, pp. 15–26 (2007)

29.

Pei, J., Jin, W., Ester, M., Tao, Y.: Catching the best views of skyline: A semantic approach based on decisive subspaces. In: VLDB, pp. 253–264 (2005)

30.

Pei, J., Yuan, Y., Lin, X., Jin, W., Ester, M., Liu, Q.: Towards multidimensional subspace skyline analysis. ACM Trans. Database Syst. 31(4), 1335–1381 (2006)CrossRef

31.

Prasad, M.D., Deepak, P.: Efficient reverse skyline retrieval with arbitrary non-metric similarity measures. In: EDBT, pp. 319–330 (2011)

32.

Raissi, C., Pei, J., Kister, T.: Computing closed skycubes. In: VLDB, pp. 838–847 (2010)

33.

Sarkas, N., Das, G., Koudas, N., Tung, A.K.H.: Categorical skylines for streaming data. In: SIGMOD, pp. 239–250 (2008)

34.

Tan, K.-L., Eng, P.-K., Ooi, B.C.: Efficient progressive skyline computation. In: VLDB, pp. 301–310 (2001)

35.

Tao, Y., Papadias, D.: Maintaining sliding window skylines data streams. IEEE Trans. Knowl. Data Eng. 18(3), 377–391 (2006)CrossRef

36.

Tao, Y., Xiao, X., Pei, J.: Subsky: efficient computation of skylines in subspaces. In: ICDE, pp. 65 (2006)

37.

Vlachou, A., Doulkeridis, C., Kotidis, Y., Vazirgiannis, M.: SKYPEER: efficient subspace skyline computation over distributed data. In: ICDE, pp. 416–425 (2007)

38.

Wang, G., Xin, J., Chen, L., Liu, Y.: Energy-efficient reverse skyline queries processing over wireless sensor networks. IEEE Trans. Knowl. Data Eng. 24(7), 1259–1275 (2012)CrossRef

39.

Wu, X., Tao, Y., Wong, R.C.-W., Ding, L., Yu, J.X.: Finding the influence set through skylines. In: EDBT, pp. 1030–1041 (2009)

40.

Xia, T., Zhang, D.: Refreshing the sky: the compressed skycube with efficient support for frequent updates. In: SIGMOD, pp. 491–502 (2006)

41.

Yiu, M., Lo, E., Yung, D.: Measuring the sky: on computing data cubes via skylining the measures. IEEE Trans. Knowl. Data Eng. 24(3), 492–505 (2012)CrossRef

42.

Yong, H., Kim, J., Hwang, S.: Skyline ranking for uncertain data with maybe confidence. In: ICDE, pp. 572–579 (2008)

43.

Yuan, Y., Lin, X., Liu, Q., Wang, W., Yu, J.X., Zhang, Q.: Efficient computation of the skyline cube. In: VLDB, pp. 241–252 (2005)

44.

Zhang, Z., Cheng, R., Papadias, D., Tung, A.K.H.: Minimizing the communication cost for continuous skyline maintenance. In: SIGMOD, pp. 495–508 (2009)

45.

Zhang, W., Lin, X., Zhang, Y., Wang, W., Yu, J.X.: Probabilistic skyline operator over sliding windows. In: ICDE, pp. 1060–1071 (2009)

46.

Zhang, S., Mamoulis, N., Cheung, D.W.: Scalable skyline computation using object-based space partitioning. In: SIGMOD, pp. 483–494 (2009)

47.

Zhu, L., Li, C., Chen, H.: Efficient computation of reverse skyline on data stream. In: CSO, pp. 735–739 (2009)

Titel: Efficient group-by reverse skyline computation
verfasst von: Zonghui Wang
Yunjun Gao
Qing Liu
Xiaoye Miao
Qing Li
Chuan Li
Publikationsdatum: 01.11.2016
Verlag: Springer US
Erschienen in: World Wide Web / Ausgabe 6/2016
Print ISSN: 1386-145X
Elektronische ISSN: 1573-1413
DOI: https://doi.org/10.1007/s11280-015-0372-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"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 6/2016

RMACO :a randomly matched parallel ant colony optimization

Multi-label classification via learning a unified object-label graph with sparse representation

Integrating a case-based reasoning shell and Web 2.0: design recommendations and insights

Bottleneck-aware arrangement over event-based social networks: the max-min approach

Distinguishing re-sharing behaviors from re-creating behaviors in information diffusion

Following the dynamic block on the Web

Premium Partner