NDLI: A generic flow algorithm for shared filter ordering problems

Please wait, while we are loading the content...

Curated databases

The recovery of a schema mapping: bringing exchanged data back

Evaluating rank joins with optimal cost

Estimating PageRank on graph streams

Approximating predicates and expressive queries on probabilistic databases

Answering aggregate queries in data exchange

Dependencies revisited for improving data quality

On searching compressed string collections cache-obliviously

Static analysis of active XML systems

XPath evaluation in linear time

Near-optimal dynamic replication in unstructured peer-to-peer networks

PODS Alberto O. Mendelzon Test-of-Time Award 2008

On the complexity of deriving schema mappings from database instances

Effective characterizations of tree logics

A generic flow algorithm for shared filter ordering problems

Incorporating constraints in probabilistic XML

Data exchange and schema mappings in open and closed worlds

Epistemic privacy

Approximation algorithms for clustering uncertain data

Complexity and composition of synthesized web services

XPath, transitive closure logic, and nested tree walking automata

Type inference for datalog and its application to query optimisation

SIGMOD 10-year Test-of-Time Award: “Integration of heterogeneous databases without common domains using queries based on textual simularity”

Towards a theory of schema-mapping optimization

Time-decaying aggregates in out-of-order streams

Query evaluation with soft-key constraints

The chase revisited

Approximation algorithms for co-clustering

Local Hoare reasoning about DOM

Shape sensitive geometric monitoring

SIGMOD Best Dissertation Award: “Efficient query processing over inconsistent databases”

The power of two min-hashes for similarity search among hierarchical data objects

Annotated XML: queries and provenance

Tree-width and functional dependencies in databases

Best Newcomer Award: Evaluating rank joins with optimal costs

A generic flow algorithm for shared filter ordering problems

Content Provider	ACM Digital Library
Author	Ranganathan, Anand Liu, Zhen Parthasarathy, Srinivasan Yang, Hao
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.
Starting Page	79
Ending Page	88
Page Count	10
File Format	PDF
ISBN	9781605581521
DOI	10.1145/1376916.1376929
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-06-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Flow maximization Parallel Query optimization Shared filter ordering
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Flow algorithms for two pipelined filter ordering problems

Near-optimal algorithms for shared filter evaluation in data stream systems

Algorithms for distributional and adversarial pipelined filter ordering problems

Parallel pipelined filter ordering with precedence constraints

Flow Algorithms for Parallel Query Optimization

Flow algorithms for parallel query optimization (2007)

Genetic optimization for the join ordering problem of database queries

Progressive optimization in a shared-nothing parallel database

Coloring Away Communication in Parallel Query Optimization (1995)

A generic flow algorithm for shared filter ordering problems

Similar Documents

Flow algorithms for two pipelined filter ordering problems

Near-optimal algorithms for shared filter evaluation in data stream systems

Algorithms for distributional and adversarial pipelined filter ordering problems

Parallel pipelined filter ordering with precedence constraints

Flow Algorithms for Parallel Query Optimization

Flow algorithms for parallel query optimization (2007)

Genetic optimization for the join ordering problem of database queries

Progressive optimization in a shared-nothing parallel database

Coloring Away Communication in Parallel Query Optimization (1995)

A generic flow algorithm for shared filter ordering problems