More Web Proxy on the site http://driver.im/

research-article

Parallel skyline queries

Authors:

Foto N. Afrati,

Paraschos Koutris,

Jeffrey D. UllmanAuthors Info & Claims

ICDT '12: Proceedings of the 15th International Conference on Database Theory

Pages 274 - 284

https://doi.org/10.1145/2274576.2274605

Published: 26 March 2012 Publication History

Abstract

In this paper, we design and analyze parallel algorithms for skyline queries. The skyline of a multidimensional set consists of the points for which no other point exists that is at least as good along every dimension. As a framework for parallel computation, we use both the MP model proposed in (Koutris and Suciu, PODS 2011), which requires that the data is perfectly load-balanced, and a variation of the model in (Afrati and Ullman, EDBT 2010), the GMP model, which demands weaker load balancing constraints. In addition to load balancing, we want to minimize the number of blocking steps, where all processors must wait and synchronize. We propose a 2-step algorithm in the MP model for any dimension of the dataset, as well a 1-step algorithm for the case of 2 and 3 dimensions. Moreover, we present a 1-step algorithm in the GMP model for any number of dimensions.

References

[1]

F. N. Afrati and J. D. Ullman. Optimizing joins in a map-reduce environment. In EDBT, volume 426 of ACM International Conference Proceeding Series, pages 99--110. ACM, 2010.

Digital Library

[2]

P. Berenbrink, T. Friedetzky, Z. Hu, and R. A. Martin. On weighted balls-into-bins games. Theor. Comput. Sci., 409(3):511--520, 2008.

Digital Library

[3]

S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In ICDE, pages 421--430. IEEE Computer Society, 2001.

Digital Library

[4]

J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting. In ICDE, pages 717--816. IEEE Computer Society, 2003.

[5]

A. Cosgaya-Lozano, A. Rau-Chaplin, and N. Zeh. Parallel computation of skyline queries. In HPCS, page 12. IEEE Computer Society, 2007.

Digital Library

[6]

J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. In OSDI, pages 137--150, 2004.

Digital Library

[7]

F. K. H. A. Dehne, A. Fabri, and A. Rau-Chaplin. Scalable parallel geometric algorithms for coarse grained multicomputers. In Symposium on Computational Geometry, pages 298--307, 1993.

Digital Library

[8]

A. Gates, O. Natkovich, S. Chopra, P. Kamath, S. Narayanam, C. Olston, B. Reed, S. Srinivasan, and U. Srivastava. Building a highlevel dataflow system on top of mapreduce: The pig experience. PVLDB, 2(2):1414--1425, 2009.

Digital Library

[9]

P. Godfrey, R. Shipley, and J. Gryz. Maximal vector computation in large data sets. In VLDB, pages 229--240. ACM, 2005.

Digital Library

[10]

J. M. Hellerstein. The declarative imperative: experiences and conjectures in distributed logic. SIGMOD Record, 39(1):5--19, 2010.

Digital Library

[11]

H. J. Karloff, S. Suri, and S. Vassilvitskii. A model of computation for mapreduce. In SODA, pages 938--948. SIAM, 2010.

Digital Library

[12]

H. Köhler, J. Yang, and X. Zhou. Efficient parallel skyline processing using hyperplane projections. In SIGMOD Conference, pages 85--96. ACM, 2011.

Digital Library

[13]

P. Koutris and D. Suciu. Parallel evaluation of conjunctive queries. In PODS, pages 223--234. ACM, 2011.

Digital Library

[14]

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

Digital Library

[15]

K. C. K. Lee, B. Zheng, H. Li, and W.-C. Lee. Approaching the skyline in z order. In VLDB, pages 279--290. ACM, 2007.

Digital Library

[16]

J. Matousek. Computing dominances in Eⁿ. Inf. Process. Lett., 38(5):277--278, 1991.

Digital Library

[17]

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

Digital Library

[18]

S. Park, T. Kim, J. Park, J. Kim, and H. Im. Parallel skyline computation on multicore architectures. In ICDE, pages 760--771. IEEE, 2009.

Digital Library

[19]

M. Raab and A. Steger. "balls into bins" - a simple and tight analysis. In RANDOM, pages 159--170, 1998.

Digital Library

[20]

J. B. Rocha-Junior, A. Vlachou, C. Doulkeridis, and K. Nørvåg. Agids: A grid-based strategy for distributed skyline query processing. In Globe, volume 5697 of Lecture Notes in Computer Science, pages 12--23. Springer, 2009.

Digital Library

[21]

I. Stojmenovic and M. Miyakawa. An optimal parallel algorithm for solving the maximal elements problem in the plane. Parallel Computing, 7(2):249--251, 1988.

[22]

A. Vlachou, C. Doulkeridis, and Y. Kotidis. Angle-based space partitioning for efficient parallel skyline computation. In SIGMOD Conference, pages 227--238. ACM, 2008.

Digital Library

[23]

S. Wang, B. C. Ooi, A. K. H. Tung, and L. Xu. Efficient skyline query processing on peer-to-peer networks. In ICDE, pages 1126--1135. IEEE, 2007.

[24]

P. Wu, C. Zhang, Y. Feng, B. Y. Zhao, D. Agrawal, and A. E. Abbadi. Parallelizing skyline queries for scalable distribution. In EDBT, volume 3896 of Lecture Notes in Computer Science, pages 112--130. Springer, 2006.

Digital Library

Cited By

Zhang YShi YZhou ZXue CXu YXu KDu J(2023)Efficient and Secure Skyline Queries Over Vertical Data FederationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.322241535:9(9269-9280)Online publication date: 1-Sep-2023
https://doi.org/10.1109/TKDE.2022.3222415
Vlachou ADoulkeridis CRocha-Junior JNørvåg K(2023)Decisive skyline queries for truly balancing multiple criteriaData & Knowledge Engineering10.1016/j.datak.2023.102206147(102206)Online publication date: Sep-2023
https://doi.org/10.1016/j.datak.2023.102206
Kuo AChen HTang LKu WQin X(2022)ProbSky: Efficient Computation of Probabilistic Skyline Queries over Distributed DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3151740(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3151740
Show More Cited By

Index Terms

Parallel skyline queries
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Parallel and distributed DBMSs

Recommendations

Parallel Skyline Queries

In this paper, we design and analyze parallel algorithms for skyline queries. The skyline of a multidimensional set consists of the points for which no other point exists that is at least as good along every dimension. As a framework for parallel ...
Combination skyline queries
Transactions on Large-Scale Data- and Knowledge-Centered Systems VI

Given a collection of data objects, the skyline problem is to select the objects which are not dominated by any others. In this paper, we propose a new variation of the skyline problem, called the combination skyline problem. The goal is to find the ...
Spatial skyline queries: exact and approximation algorithms

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICDT '12: Proceedings of the 15th International Conference on Database Theory

March 2012

329 pages

ISBN:9781450307918

DOI:10.1145/2274576

General Chair:
Alin Deutsch
University of California, San Diego

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 March 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICDT '12

ICDT '12: 15th International Conference on Database Theory

March 26 - 29, 2012

Berlin, Germany

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
341
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YShi YZhou ZXue CXu YXu KDu J(2023)Efficient and Secure Skyline Queries Over Vertical Data FederationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.322241535:9(9269-9280)Online publication date: 1-Sep-2023
https://doi.org/10.1109/TKDE.2022.3222415
Vlachou ADoulkeridis CRocha-Junior JNørvåg K(2023)Decisive skyline queries for truly balancing multiple criteriaData & Knowledge Engineering10.1016/j.datak.2023.102206147(102206)Online publication date: Sep-2023
https://doi.org/10.1016/j.datak.2023.102206
Kuo AChen HTang LKu WQin X(2022)ProbSky: Efficient Computation of Probabilistic Skyline Queries over Distributed DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3151740(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3151740
Ding LZhang XZhang HLiu LSong B(2021)CrowdSJ: Skyline-Join Query Processing of Incomplete Datasets With CrowdsourcingIEEE Access10.1109/ACCESS.2021.30793249(73216-73229)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3079324
Tai LWang EChen A(2021)Finding the most profitable candidate product by dynamic skyline and parallel processingDistributed and Parallel Databases10.1007/s10619-021-07323-4Online publication date: 18-Mar-2021
https://doi.org/10.1007/s10619-021-07323-4
Yin BWei XWang JXiong NGu K(2020)An Industrial Dynamic Skyline Based Similarity Joins For Multidimensional Big Data ApplicationsIEEE Transactions on Industrial Informatics10.1109/TII.2019.293353416:4(2520-2532)Online publication date: Apr-2020
https://doi.org/10.1109/TII.2019.2933534
Groz BMallmann-Trenn FMathieu CVerdugo V(2020)Skyline Computation with Noisy ComparisonsCombinatorial Algorithms10.1007/978-3-030-48966-3_22(289-303)Online publication date: 8-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-48966-3_22
Qaosar MZaman ASiddique MAnnisa Morimoto Y(2019)Privacy-Preserving Secure Computation of Skyline Query in Distributed Multi-Party DatabasesInformation10.3390/info1003011910:3(119)Online publication date: 25-Mar-2019
https://doi.org/10.3390/info10030119
Geck GKetsman BNeven FSchwentick T(2019)Parallel-Correctness and Containment for Conjunctive Queries with Union and NegationACM Transactions on Computational Logic10.1145/332912020:3(1-24)Online publication date: 7-Jun-2019
https://dl.acm.org/doi/10.1145/3329120
Dolev SFlorissi PGudes ESharma SSinger I(2019)A Survey on Geographically Distributed Big-Data Processing Using MapReduceIEEE Transactions on Big Data10.1109/TBDATA.2017.27234735:1(60-80)Online publication date: 1-Mar-2019
https://doi.org/10.1109/TBDATA.2017.2723473
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents