Skip to main content

2016 | OriginalPaper | Buchkapitel

SkyCube-Tree Based Group-by Query Processing in OLAP Skyline Cubes

verfasst von : Hideki Sato, Takayuki Usami

Erschienen in: Intelligent Interactive Multimedia Systems and Services 2016

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

SkyCube-tree has been developed to realize efficient range query processing for Skyline Cube (SC). Apart from range queries, this paper demonstrates that SkyCube-tree can be made use of efficient group-by query processing, though it is originally designed to realize efficient range query processing. Since a group-by query for SC includes the entire dataset as its processing range, the query processing time is potentially large. From the experimental evaluation, the followings are clarified:
  • The size of SkyCube-trees is sufficiently allowable, since it is at most 2.5 times as large as that of materialized view.
  • The time of SkyCube-tree based sequential processing is nearly equal to that of materialized view based one, regardless of its dedication to range query processing.
  • The time of SkyCube-tree based parallel processing is comparatively small and stable. Even though cell-granularity is over 80 \(\%\), its processing time is around 10 \(\%\) of that of materialized view based one.

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!

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!

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!

Fußnoten
1
It is possible to impose a range condition on a categorical dimension attribute by converting its domain into a numerical one.
 
2
The size of address data is 8 bytes.
 
3
Z-curve [10] is employed for the work.
 
4
Block Nested Loop (BNL) algorithm [11] is employed for the work.
 
5
Note that it includes the time to transfer data between main memory of CPU and RAM memory of GPU.
 
Literatur
1.
Zurück zum Zitat Codd, E.F.: Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate, Technical report. E.F.Codd and Associates (1993) Codd, E.F.: Providing OLAP (On-Line Analytical Processing) to User-Analysts: An IT Mandate, Technical report. E.F.Codd and Associates (1993)
2.
Zurück zum Zitat Gray, J., Bosworth, A., Layman, A., Pirahesh, H.: A relational aggregation operator generalizing group-by, cross-tabs and subtotals. In: Proceedings of the 12th Int’l Conference on Data Engineering, pp. 152–159 (1996) Gray, J., Bosworth, A., Layman, A., Pirahesh, H.: A relational aggregation operator generalizing group-by, cross-tabs and subtotals. In: Proceedings of the 12th Int’l Conference on Data Engineering, pp. 152–159 (1996)
3.
Zurück zum Zitat Agrawal, R., Gupta, A., Sarawagi, S.: Modeling multidimensional databases, In: Proceedings of the 13th Int’l Conference on Data Engineering (1997) Agrawal, R., Gupta, A., Sarawagi, S.: Modeling multidimensional databases, In: Proceedings of the 13th Int’l Conference on Data Engineering (1997)
4.
Zurück zum Zitat Yiu, M.L., Lo, E., Yung, D.: Measuring the sky: on computing data cubes via skylining the measure. IEEE Trans. Knowl. Data Eng. 24(3), 492–505 (2012)CrossRef Yiu, M.L., Lo, E., Yung, D.: Measuring the sky: on computing data cubes via skylining the measure. IEEE Trans. Knowl. Data Eng. 24(3), 492–505 (2012)CrossRef
5.
Zurück zum Zitat Luk, M.N., Yiu, M.L., Megiddo, N., Lo, E.: Group-by skyline query processing in relational engines. In: Proceedingsc of the 18th ACM Conference on Information and Knowledge Management, pp. 1433–1436 (2009) Luk, M.N., Yiu, M.L., Megiddo, N., Lo, E.: Group-by skyline query processing in relational engines. In: Proceedingsc of the 18th ACM Conference on Information and Knowledge Management, pp. 1433–1436 (2009)
6.
Zurück zum Zitat Borzsonyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proceedings of the 17th Int’l Conference on Data Engineering, pp. 421–430 (2001) Borzsonyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proceedings of the 17th Int’l Conference on Data Engineering, pp. 421–430 (2001)
7.
Zurück zum Zitat Sato, H., Usami, T.: Range query processing in OLAP skyline cubes. IEEJ Trans. Electron. Inf. Syst. 136(4) (2016). (in Japanese, to be published) Sato, H., Usami, T.: Range query processing in OLAP skyline cubes. IEEJ Trans. Electron. Inf. Syst. 136(4) (2016). (in Japanese, to be published)
8.
Zurück zum Zitat Guttman, A.: R-Trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD Int’l Conference on Management of Data, pp. 45–57 (1984) Guttman, A.: R-Trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD Int’l Conference on Management of Data, pp. 45–57 (1984)
9.
Zurück zum Zitat Vlachou, A., Doulkeridis, C., Kotidis, Y., Vazirgiannis, M.: SKYPEER: efficient subspace skyline computation over distributed data. In: Proceedings of the 23rd Int’l Conference on Data Engineering, pp. 416–425 (2007) Vlachou, A., Doulkeridis, C., Kotidis, Y., Vazirgiannis, M.: SKYPEER: efficient subspace skyline computation over distributed data. In: Proceedings of the 23rd Int’l Conference on Data Engineering, pp. 416–425 (2007)
10.
Zurück zum Zitat Orenstein, J., Merrett, T.H.: A class of data structures for associative searching. In: Proceedings of the 3rd ACM SIGACT-SIGMOD Symposium on Principles of Data Base Systems, pp. 181–190 (1984) Orenstein, J., Merrett, T.H.: A class of data structures for associative searching. In: Proceedings of the 3rd ACM SIGACT-SIGMOD Symposium on Principles of Data Base Systems, pp. 181–190 (1984)
11.
Zurück zum Zitat Papadias, D., Tao, Y., Fu, G., Seeger, B.: Progressive skyline computation in database systems. ACM Trans. Database Syst. 30(1), 41–82 (2005)CrossRef Papadias, D., Tao, Y., Fu, G., Seeger, B.: Progressive skyline computation in database systems. ACM Trans. Database Syst. 30(1), 41–82 (2005)CrossRef
12.
Zurück zum Zitat Sanders, J., Kandrot, E.: CUDA by example: an introduction to general-purpose GPU programming, Addison-Wesley Professional (2010) Sanders, J., Kandrot, E.: CUDA by example: an introduction to general-purpose GPU programming, Addison-Wesley Professional (2010)
13.
Zurück zum Zitat Yuan, Y., Lin, X., Liu, Q., Wang, W., Yu, J.X., Zhang, Q.: Efficient computation of the skyline cube. In: Proceedings the 2005 Int’l Conference on Very Large Data Bases, pp. 241–252 (2005) Yuan, Y., Lin, X., Liu, Q., Wang, W., Yu, J.X., Zhang, Q.: Efficient computation of the skyline cube. In: Proceedings the 2005 Int’l Conference on Very Large Data Bases, pp. 241–252 (2005)
14.
Zurück zum Zitat Ho, C.T., Agrawal, R., Megiddo, N., Srikant, R.: Range queries in OLAP data cubes. In: Proceedings of the 1997 ACM SIGMOD Int’l Conference on Management of Data, pp. 73–88 (1997) Ho, C.T., Agrawal, R., Megiddo, N., Srikant, R.: Range queries in OLAP data cubes. In: Proceedings of the 1997 ACM SIGMOD Int’l Conference on Management of Data, pp. 73–88 (1997)
15.
Zurück zum Zitat Feng, Y., Makinouchi, A.: Indexing for range-aggregation queries on large relational datasets. Int’l J. Database Theory Appl. 3(4), 1–14 (2010) Feng, Y., Makinouchi, A.: Indexing for range-aggregation queries on large relational datasets. Int’l J. Database Theory Appl. 3(4), 1–14 (2010)
16.
Zurück zum Zitat Feng, Y., Makinouchi, A.: Ag+-tree: an index structure for range-aggregation queries in data warehouse environments. Int’l J. Database Theory Appl. 4(2), 51–64 (2011) Feng, Y., Makinouchi, A.: Ag+-tree: an index structure for range-aggregation queries in data warehouse environments. Int’l J. Database Theory Appl. 4(2), 51–64 (2011)
17.
Zurück zum Zitat Chan, C-Y., Jagadish, H.V., Tan, K-L., Tung, A.K.H., Zhang, Z.: Finding k-dominant skylines in high dimensional space. In: Proceedings of the 2006 ACM SIGMOD Int’l Conference on Management of Data, pp. 503–514 (2006) Chan, C-Y., Jagadish, H.V., Tan, K-L., Tung, A.K.H., Zhang, Z.: Finding k-dominant skylines in high dimensional space. In: Proceedings of the 2006 ACM SIGMOD Int’l Conference on Management of Data, pp. 503–514 (2006)
18.
Zurück zum Zitat IIyas, H.F., Beskales, G., Soliman, M.A.: A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. 40(4) (2008). Article 11 IIyas, H.F., Beskales, G., Soliman, M.A.: A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. 40(4) (2008). Article 11
Metadaten
Titel
SkyCube-Tree Based Group-by Query Processing in OLAP Skyline Cubes
verfasst von
Hideki Sato
Takayuki Usami
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-39345-2_26