research-article

A generic flow algorithm for shared filter ordering problems

Authors:

Srinivasan Parthasarathy,

Anand Ranganathan,

Hao YangAuthors Info & Claims

PODS '08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pages 79 - 88

https://doi.org/10.1145/1376916.1376929

Published: 09 June 2008 Publication History

Abstract

We consider a fundamental flow maximization problem that arises during the evaluation of multiple overlapping queries defined on a data stream, in a heterogenous parallel environment. Each query is a conjunction of boolean filters, and each filter could be shared across multiple queries. We are required to design an evaluation plan that evaluates filters against stream items in order to determine the set of queries satisfied by each item. The evaluation plan specifies for each item: (i) the subset of filters evaluated for this item and the order of their evaluations, and (ii) the processor on which each filter evaluation occurs. Our goal is to design an evaluation plan which maximizes the total throughput (flow) of the stream handled by the plan, without violating the processor capacities.

Filter ordering has received extensive attention in single-processor settings, with the objective of minimizing the total cost of filter evaluations: in particular, efficient (approximation) algorithms are known for various important versions of min-cost filter ordering. Min-cost filter ordering problem for a single processor is a special case of our flow maximization for parallel processors. Our main contribution in this work is a generic flow-maximization algorithm, which assumes the availability of a min-cost filter ordering algorithm for a single processor, and uses this to iteratively construct a solution to the flow-maximization problem for heterogenous parallel processors. We show that the approximation ratio of our flow-maximization strategy is essentially the same as that of the underlying min-cost filter ordering algorithm. Our result, along with existing results on min-cost filter ordering, enables the optimization of several important versions of filter ordering in parallel environments.

References

[1]

Ron Avnur and Joseph M. Hellerstein. Eddies: continuously adaptive query processing. SIGMOD Rec., 29(2):261--272, 2000.]]

Digital Library

[2]

Shivnath Babu, Rajeev Motwani, Kamesh Munagala, Itaru Nishizawa, and Jennifer Widom. Adaptive ordering of pipelined stream filters. In SIGMOD, pages 407--418, New York, NY, USA, 2004. ACM Press.]]

Digital Library

[3]

Amotz Bar-Noy, Mihir Bellare, Magn´us M. Halld´orsson, Hadas Shachnai, and Tami Tamir. On chromatic sums and distributed resource allocation. Inf. Comput, 140(2):183--202, 1998.]]

Digital Library

[4]

Surajit Chaudhuri, Umeshwar Dayal, and Tak W. Yan. Join queries with external text sources: execution and optimization techniques. In SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data, pages 410--422, New York, NY, USA, 1995. ACM.]]

Digital Library

[5]

H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493--509, 1952.]]

[6]

Edith Cohen, Amos Fiat, and Haim Kaplan. Efficient sequences of trials. In SODA, pages 737--746, 2003.]]

Digital Library

[7]

Anne Condon, Amol Deshpande, Lisa Hellerstein, and Ning Wu. Flow algorithms for two pipelined filter ordering problems. In PODS, pages 193--202, New York, NY, USA, 2006. ACM Press.]]

Digital Library

[8]

Amol Deshpande, Carlos Guestrin, Wei Hong, and Samuel Madden. Exploiting correlated attributes in acquisitional query processing. In ICDE '05: Proceedings of the 21st International Conference on Data Engineering, pages 143--154, Washington, DC, USA, 2005. IEEE Computer Society.]]

Digital Library

[9]

Oren Etzioni, Steve Hanks, Tao Jiang, Richard M. Karp, Omid Madani, and Orli Waarts. Efficient information gathering on the internet (extended abstract). In FOCS, pages 234--243, 1996.]]

Digital Library

[10]

Uriel Feige and Prasad Tetali. Approximating min sum set cover. Algorithmica, 40(4):219--234, 2004.]]

Digital Library

[11]

N. Garg and J. Koenemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, page 300. IEEE Computer Science Society, 1998.]]

Digital Library

[12]

Roy Goldman and Jennifer Widom. Wsq/dsq: a practical approach for combined querying of databases and the web. In SIGMOD '00: Proceedings of the 2000 ACM SIGMOD international conference on Management of data, pages 285--296, New York, NY, USA, 2000. ACM.]]

Digital Library

[13]

J. Hellerstein and M. Stonebraker. Predicate migration: Optimizing queries with expensive predicates. In Proc. SIGMOD, 1993.]]

Digital Library

[14]

W. Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, 58:13--30, 1963.]]

[15]

T. Ibaraki and T. Kameda. On the optimal nesting order for computing n-relational joins. ACM Trans. on Database Systems, 9(3):482--502, 1984.]]

Digital Library

[16]

Haim Kaplan, Eyal Kushilevitz, and Yishay Mansour. Learning with attribute costs. In STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 356--365, New York, NY, USA, 2005. ACM.]]

Digital Library

[17]

Murali S. Kodialam. The throughput of sequential testing. In Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, pages 280--292, London, UK, 2001. Springer-Verlag.]]

Digital Library

[18]

Ravi Krishnamurthy, Haran Boral, and Carlo Zaniolo. Optimization of nonrecursive queries. In Proc. VLDB, pages 128--137, 1986.]]

Digital Library

[19]

Zhen Liu, Srinivasan Parthasarathy, Anand Ranganathan, and Hao Yang. Near-optimal algorithms for shared filter evaluation in data stream systems. In Proc. of ACM SIGMOD (to appear), 2008.]]

Digital Library

[20]

Kamesh Munagala, Shivnath Babu, Rajeev Motwani, and Jennifer Widom. The pipelined set cover problem. In 10th International Conference on Database Theory - ICDT, pages 83--98, 2005.]]

Digital Library

[21]

Kamesh Munagala, Utkarsh Srivastava, and Jennifer Widom. Optimization of continuous queries with shared expensive filters. In PODS '07: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 215--224, New York, NY, USA, 2007. ACM.]]

Digital Library

[22]

Serge A. Plotkin, David B. Shmoys, and Éva Tardos. Fast approximation algorithms for fractional packing and covering problems. In Proceedings of the 32nd annual symposium on Foundations of computer science, pages 495--504, Los Alamitos, CA, USA, 1991. IEEE Computer Society Press.]]

Digital Library

[23]

H. Simon and J. Kadane. Optimal problem-solving search: All-or-none solutions. Artificial Intelligence, 6:235--247, 1975.]]

[24]

Vijay V. Vazirani. Approximation algorithms. Springer-Verlag New York, Inc., New York, NY, USA, 2001.]]

Digital Library

[25]

Neal E. Young. Sequential and parallel algorithms for mixed packing and covering. In Proceedings of IEEE Symposium on Foundations of Computer Science, 2001.]]

Digital Library

Cited By

Hellerstein LLidbetter TPirutinsky D(2019)Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search GamesOperations Research10.1287/opre.2019.185367:3(731-743)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1287/opre.2019.1853
Hellerstein LÖzkan ÖSellie L(2017)Max-Throughput for (Conservative) k-of-n TestingAlgorithmica10.1007/s00453-015-0089-477:2(595-618)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s00453-015-0089-4
Nykiel TPotamias MMishra CKollios GKoudas N(2014)Sharing across Multiple MapReduce JobsACM Transactions on Database Systems10.1145/256079639:2(1-46)Online publication date: 26-May-2014
https://dl.acm.org/doi/10.1145/2560796
Show More Cited By

Index Terms

A generic flow algorithm for shared filter ordering problems
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Flow algorithms for two pipelined filter ordering problems
PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pipelined filter ordering is a central problem in database query optimization, and has received renewed attention recently in the context of environments such as the web, continuous high-speed data streams and sensor networks. We present algorithms for ...
Near-optimal algorithms for shared filter evaluation in data stream systems
SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data

We consider the problem of evaluating multiple overlapping queries defined on data streams, where each query is a conjunction of multiple filters and each filter may be shared across multiple queries. Efficient support for overlapping queries is a ...
Parallel pipelined filter ordering with precedence constraints

In the parallel pipelined filter ordering problem, we are given a set of n filters that run in parallel. The filters need to be applied to a stream of elements, to determine which elements pass all filters. Each filter has a rate limit r_i on the number ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

June 2008

330 pages

ISBN:9781605581521

DOI:10.1145/1376916

General Chair:
Phokion Kolaitis
IBM Almaden Research Center, USA
,
Program Chair:
Maurizio Lenzerini
SAPIENZA University of Rome, Italy

Copyright © 2008 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '08

Sponsor:

SIGMOD/PODS '08: SIGMOD/PODS '08 - International Conference on Management of Data

June 9 - 12, 2008

Vancouver, Canada

Acceptance Rates

PODS '08 Paper Acceptance Rate 28 of 159 submissions, 18%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
305
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hellerstein LLidbetter TPirutinsky D(2019)Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search GamesOperations Research10.1287/opre.2019.185367:3(731-743)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1287/opre.2019.1853
Hellerstein LÖzkan ÖSellie L(2017)Max-Throughput for (Conservative) k-of-n TestingAlgorithmica10.1007/s00453-015-0089-477:2(595-618)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s00453-015-0089-4
Nykiel TPotamias MMishra CKollios GKoudas N(2014)Sharing across Multiple MapReduce JobsACM Transactions on Database Systems10.1145/256079639:2(1-46)Online publication date: 26-May-2014
https://dl.acm.org/doi/10.1145/2560796
Tsamoura EGounaris AManolopoulos Y(2013)Optimal Service Ordering in Decentralized Queries Over Web ServicesIntelligence Methods and Systems Advancements for Knowledge-Based Business10.4018/978-1-4666-1873-2.ch003(43-58)Online publication date: 2013
https://doi.org/10.4018/978-1-4666-1873-2.ch003
Tsamoura EGounaris AManolopoulos Y(2012)Optimal Service Ordering in Decentralized Queries Over Web ServicesGrid and Cloud Computing10.4018/978-1-4666-0879-5.ch613(1513-1528)Online publication date: 2012
https://doi.org/10.4018/978-1-4666-0879-5.ch613
Deshpande AHellerstein L(2012)Parallel pipelined filter ordering with precedence constraintsACM Transactions on Algorithms10.1145/2344422.23444318:4(1-38)Online publication date: 4-Oct-2012
https://dl.acm.org/doi/10.1145/2344422.2344431
Tsamoura EGounaris AManolopoulos Y(2012)Optimization of decentralized multi-way join queries over pipelined filtering servicesComputing10.1007/s00607-012-0209-994:12(939-972)Online publication date: 24-Aug-2012
https://doi.org/10.1007/s00607-012-0209-9
Tsamoura EGounaris AManolopoulos Y(2011)Optimal Service Ordering in Decentralized Queries Over Web ServicesInternational Journal of Knowledge-Based Organizations10.4018/ijkbo.20110401011:2(1-16)Online publication date: 1-Apr-2011
https://doi.org/10.4018/ijkbo.2011040101
Candea GPolyzotis NVingralek R(2011)Predictable performance and high query concurrency for data analyticsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-011-0221-220:2(227-248)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1007/s00778-011-0221-2
Hellerstein LÖzkan ÖSellie L(2011)Max-throughput for (conservative) k-of-n testingProceedings of the 22nd international conference on Algorithms and Computation10.1007/978-3-642-25591-5_72(703-713)Online publication date: 5-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25591-5_72
Show More Cited By

View Options

Get Access

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