Search

SIGMOD 2008 was the first database conference that offered to test submitters' programs against their data to verify the repeatability of the experiments published [1]. Given the positive feedback concerning the SIGMOD 2008 repeatability initiative, SIGMOD 2009 modified and expanded the initiative with a workability assessment.

SIGMOD 2008 was the first database conference that offered to test submitters' programs against their data to verify the experiments published. This paper discusses the rationale for this effort, the community's reaction, our experiences, and advice for future similar efforts.

We report a simple new algorithm, cis/TF, that uses genomewide expression data and the full genomic sequence to match transcription factors to their binding sites. Most previous computational methods discovered binding sites by clustering genes having similar expression patterns and then identifying over-represented subsequences in the promoter regions of those genes. By contrast, cis/TF asserts that B is a likely binding site of a transcription factor T if the expression pattern of T is correlated to the composite expression patterns of all genes containing B, even when those genes are not mutually correlated. Thus, our method focuses on binding sites rather than genes. The algorithm has successfully identified experimentally-supported transcription factor binding relationships in tests on several data sets from Saccharomyces cerevisiae.

Ordered labeled trees are trees in which the sibling order matters. This paper presents algorithms for three problems having to do with approximate matching for such trees with variable length don't cares (VLDCs). In strings, a VLDC symbol in the pattern may substitute for zero or more symbols in the data string. For example, if "com∗er" is the pattern, then the "∗" would substitute for the substring "put" when matching the data string "computer." Approximate VLDC matching in strings means that after the best possible substitution, the pattern still need not be the same as the data string for a match to be allowed. For example, "com∗er" matches "counter" within distance one (representing the cost of removing the "m" from "com∗er" and having the "∗" substitute for "unt"). We generalize approximate VLDC string matching to three algorithms for approximate VLDC matching on trees. The time complexity of our algorithms is O(|P| × |D| × min(depth(P), leaves(P)) × min(depth(D), leaves(D))) (where |P| and |D| are the number of nodes respectively of the pattern P and the data tree D), the same as for the best approximate tree matching algorithm without VLDCs previously reported.Copyright 1994, 1999 Academic Press

By precision dose delivery to a well-defined target, brachytherapy fulfills the complementary goals of delivering sufficient dose for tumor cell kill while sparing normal adjacent structures. The unique properties of this modality, either used alone or implemented in a combined modality setting with surgery or externalbeam irradiation, offer an ideal means of enhancing the therapeutic ratio by exploiting the effect of local therapies while respecting normal tissue, tolerance. Brachytherapy also provides an effective technique for the retreatment of patients with recurrent, persistent, or second primary head and neck malignant tumors in a previously irradiated region. The benefits of this treatment modality are reflected in excellent reported local control rates, shortened overall treatment times, reduced functional deficits improved quality of life, and decreased costs. Successful brachytherapy relies, however, on close collaborative efforts between radiation oncologists and surgeons, careful assessment of the patients, precise planning, and technique that adheres to the rules of a system. Brachytherapy has been clearly identified as an effective, safe, and appealing modality in the treatment of head and neck malignancies.

With respect to on-line scheduling algorithms that must direct the service of sporadic task requests we quantify the benefit of clairvoyancy, i.e., the power of possessing knowledge of various task parameters of future events. Specifically, we consider the problem of preemptively sheduling sporadic task requests in both uni- and multi-processor environments. If a task request is successfuly scheduled to completion, a value equal to the task's execution time is obtained; otherwise no value is obtained. We prove that no on-line scheduling algorithm can guarantee a cumulative value greater than 1/4th the value obtainable by a clairvoyant scheduler; i.e., we prove a 1/4th upper bound on the competitive factor of on-line real-time schedulers. We present an online uniprocessor scheduling algorithm TD1 that actually has a competitive factor of 1/4; this bound is thus shown to be tight. We further consider the effect of restricting the amount of overloading permitted (the loading factor), and quantify the relationship between the loading factor and the upper bound on the competitive factor. Other results of a similar nature deal with the effect of value densities (measuring the importance of type of a task). Generalizations to dual-processor on-line scheduling are also considered. For the dual-processor case, we prove an upper bound of 1/2 on the competitive factor. This bound is shown to be tight in the special case when all the tasks have the same density and zero laxity.