Dataset Information

Near-Optimal Distributed Band-Joins through Recursive Partitioning.

ABSTRACT: We consider running-time optimization for band-joins in a distributed system, e.g., the cloud. To balance load across worker machines, input has to be partitioned, which causes duplication. We explore how to resolve this tension between maximum load per worker and input duplication for band-joins between two relations. Previous work suffered from high optimization cost or considered partitionings that were too restricted (resulting in suboptimal join performance). Our main insight is that recursive partitioning of the join-attribute space with the appropriate split scoring measure can achieve both low optimization cost and low join cost. It is the first approach that is not only effective for one-dimensional band-joins but also for joins on multiple attributes. Experiments indicate that our method is able to find partitionings that are within 10% of the lower bound for both maximum load per worker and input duplication for a broad range of settings, significantly improving over previous work.

SUBMITTER: Li R

PROVIDER: S-EPMC7872589 | biostudies-literature | 2020 Jun

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Near-Optimal Distributed Band-Joins through Recursive Partitioning.

Li Rundong R Gatterbauer Wolfgang W Riedewald Mirek M

Proceedings. ACM-SIGMOD International Conference on Management of Data 20200601

We consider running-time optimization for band-joins in a distributed system, e.g., the cloud. To balance load across worker machines, input has to be partitioned, which causes duplication. We explore how to resolve this tension between <i>maximum load per worker</i> and <i>input duplication</i> for band-joins between two relations. Previous work suffered from high optimization cost or considered partitionings that were too restricted (resulting in suboptimal join performance). Our main insight ...[more]

PMID: 33568887

Similar Datasets

Project description:The HapMap (haplotype map) projects have produced valuable genetic resources in life science research communities, allowing researchers to investigate sequence variations and conduct genome-wide association study (GWAS) analyses. A typical HapMap project may require sequencing hundreds, even thousands, of individual lines or accessions within a species. Due to limitations in current sequencing technology, the genotype values for some accessions cannot be clearly called. Additionally, allelic heterozygosity can be very high in some lines, causing genetic and sometimes phenotypic segregation in their descendants. Genetic and phenotypic segregation degrades the original accession's specificity and makes it difficult to distinguish one accession from another. Therefore, it is vitally important to determine and validate HapMap accessions before one conducts a GWAS analysis. However, to the best of our knowledge, there are no prior methodologies or tools that can readily distinguish or validate multiple accessions in a HapMap population. We devised a bioinformatics approach to distinguish multiple HapMap accessions using only a minimum number of genetic markers. First, we assign each candidate marker with a distinguishing score (DS), which measures its capability in distinguishing accessions. The DS score prioritizes those markers with higher percentages of homozygous genotypes (allele combinations), as they can be stably passed on to offspring. Next, we apply the "set-partitioning" concept to select optimal markers by recursively partitioning accession sets. Subsequently, we build a hierarchical decision tree in which a specific path represents the selected markers and the homogenous genotypes that can be used to distinguish one accession from others in the HapMap population. Based on these algorithms, we developed a web tool named MAD-HiDTree (Multiple Accession Distinguishment-Hierarchical Decision Tree), designed to analyze a user-input genotype matrix and construct a hierarchical decision tree. Using genetic marker data extracted from the Medicago truncatula HapMap population, we successfully constructed hierarchical decision trees by which the original 262 M. truncatula accessions could be efficiently distinguished. PCR experiments verified our proposed method, confirming that MAD-HiDTree can be used for the identification of a specific accession. MAD-HiDTree was developed in C/C++ in Linux. Both the source code and test data are publicly available at https://bioinfo.noble.org/MAD-HiDTree/.

Project description:ObjectiveThe objectives of this paper are to 1) construct a new network model compatible with distributed computation, 2) construct the full optimal power flow (OPF) in a distributed fashion so that an effective, non-inferior solution can be found, and 3) develop a scalable algorithm that guarantees the convergence to a local minimum.Existing challengesDue to the nonconvexity of the problem, the search for a solution to OPF problems is not scalable, which makes the OPF highly limited for the system operation of large-scale real-world power grids-"the curse of dimensionality". The recent attempts at distributed computation aim for a scalable and efficient algorithm by reducing the computational cost per iteration in exchange of increased communication costs.MotivationA new network model allows for efficient computation without increasing communication costs. With the network model, recent advancements in distributed computation make it possible to develop an efficient and scalable algorithm suitable for large-scale OPF optimizations.MethodsWe propose a new network model in which all nodes are directly connected to the center node to keep the communication costs manageable. Based on the network model, we suggest a nodal distributed algorithm and direct communication to all nodes through the center node. We demonstrate that the suggested algorithm converges to a local minimum rather than a point, satisfying the first optimality condition.ResultsThe proposed algorithm identifies solutions to OPF problems in various IEEE model systems. The solutions are identical to those using a centrally optimized and heuristic approach. The computation time at each node does not depend on the system size, and Niter does not increase significantly with the system size.ConclusionOur proposed network model is a star network for maintaining the shortest node-to-node distances to allow a linear information exchange. The proposed algorithm guarantees the convergence to a local minimum rather than a maximum or a saddle point, and it maintains computational efficiency for a large-scale OPF, scalable algorithm.

Project description:Objective: To identify narcolepsy related regional brain activity alterations compared with matched healthy controls. To determine whether these changes can be used to distinguish narcolepsy from healthy controls by recursive partitioning analysis (RPA) and receiver operating characteristic (ROC) curve analysis. Method: Fifty-one narcolepsy with cataplexy patients (26 adults and 25 juveniles) and sixty matched heathy controls (30 adults and 30 juveniles) were recruited. All subjects underwent a resting-state functional magnetic resonance imaging scan. Fractional low-frequency fluctuations (fALFF) was used to investigate narcolepsy induced regional brain activity alterations among adult and juveniles, respectively. Recursive partitioning analysis and Receiver operating curve analysis was used to seek the ability of fALFF values within brain regions in distinguishing narcolepsy from healthy controls. Results: Compared with healthy controls, both adult and juvenile narcolepsy had lower fALFF values in bilateral medial superior frontal gyrus, bilateral inferior parietal lobule and supra-marginal gyrus. Compared with healthy controls, both adult and juvenile narcolepsy had higher fALFF values in bilateral sensorimotor cortex and middle temporal gyrus. Also juvenile narcolepsy had higher fALFF in right putamen and right thalamus compared with healthy controls. Based on RPA and ROC curve analysis, in adult participants, fALFF differences in right medial superior frontal gyrus can discriminate narcolepsy from healthy controls with high degree of sensitivity (100%) and specificity (88.9%). In juvenile participants, fALFF differences in left superior frontal gyrus can discriminate narcolepsy from healthy controls with moderate degree of sensitivity (57.1%) and specificity (88.9%). Conclusion: Compared with healthy controls, both the adult and juvenile narcolepsy showed overlap brain regions in fALFF differences after case-control comparison. Furthermore, we propose that fALFF value can be a helpful imaging biomarker in distinguishing narcolepsy from healthy controls among both adults and juveniles.

Dataset Information

Near-Optimal Distributed Band-Joins through Recursive Partitioning.

Publications

Near-Optimal Distributed Band-Joins through Recursive Partitioning.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure