5697474
Optimizing ad hoc trade in a commercial barter trade exchange
In this paper, we describe the operation of barter trade exchanges by identifying key techniques used by trade brokers to stimulate trade and satisfy member needs, and present algorithms to automate some of these techniques. In particular, we develop algorithms that emulate the practice of trade brokers by matching buyers and sellers in such a way that trade volume is maximized while the balance of trade is maintained as much as possible. We model the trade balance problem as a minimum cost circulation problem (MCC) on a network. When the products have uniform cost or when the products can be traded in fractional units, we solve the problem exactly. Otherwise, we present a novel stochastic rounding algorithm that takes the fractional optimal solution to the trade balance problem and produces a valid integer solution. We then make use of a greedy heuristic that attempts to match buyers and sellers so that the average number of suppliers that a buyer must use to satisfy a given product need is minimized. We present results of empirical evaluation of our algorithms on test problems and on simulations built using data from an operating trade exchange.
122246710
From discrepancy to declustering: near-optimal multidimensional declustering strategies for range queries
Declustering schemes allocate data blocks among multiple disks to enable parallel retrieval. Given a declustering scheme D, its response time with respect to a query Q, rt(Q), is defined to be the maximum number of disk blocks of the query stored by the scheme in any one of the disks. If vQv is the number of data blocks in Q and M is the number of disks then rt(Q) is at least vQv/M. One way to evaluate the performance of D with respect to a set of queries 𝑄 is to measure its additive error - the maximum difference between rt(Q) from vQv/M over all range queries Q e 𝑄.In this paper, we consider the problem of designing declustering schemes for uniform multidimensional data arranged in a d-dimensional grid so that their additive errors with respect to range queries are as small as possible. It has been shown that such declustering schemes will have an additive error of Ω(log M) when d = 2 and Ω(log d-1/2 M) when d > 2 with respect to range queries.Asymptotically optimal declustering schemes exist for 2-dimensional data. For data in larger dimensions, however, the best bound for additive errors is O(Md-1), which is extremely large. In this paper, we propose the two declustering schemes based on low discrepancy points in d-dimensions. When d is fixed, both schemes have an additive error of O(logd-1 M) with respect to range queries provided certain conditions are satisfied: the first scheme requires d ≥ 3 and M to be a power of a prime where the prime is at least d while the second scheme requires the size of the data to grow within some polynomial of M, with no restriction on M. These are the first known multidimensional declustering schemes with additive errors near optimal.
5951564
Balanced matching of buyers and sellers in e-marketplaces: the barter trade exchange model
In this paper, we describe the operation of barter trade exchanges by identifying key techniques used by trade brokers to stimulate trade and satisfy member needs, and present algorithms to automate some of these techniques. In particular, we develop algorithms that emulate the practice of trade brokers by matching buyers and sellers in such a way that trade volume is maximized while the balance of trade is maintained as much as possible. We show that the buyer/seller matching and trade balance problems can be decoupled, permitting efficient solution as well as numerous options for matching strategies.We model the trade balance problem as a minimum cost circulation problem (MCC) on a network. When the products have uniform cost or when the products can be traded in fractional units, we solve the problem exactly. Otherwise, we present a novel stochastic rounding algorithm that takes the fractional optimal solution to the trade balance problem and produces a valid integer solution. We then make use of a greedy heuristic that attempts to match buyers and sellers so that the average number of suppliers that a buyer must use to satisfy a given product need is minimized.We present results on the empirical evaluation of our algorithms on test problems and simulations. Experiments show that our algorithm (MCC + stochastic rounding) runs in a fraction of the time of a commercial mixed integer programming (MIP) package while producing solutions that are always within 0.7% of the MIP solution. We evaluate the effectiveness of our algorithm on maintaining balance and on stimulating trade using two different simulation techniques, both based on transaction history data from a trade exchange. The simulation results support the barter trade exchange rule of thumb that maximizing single-period trade volume while maintaining balance of trade helps to maximize trade volume over the long run.
34686455
Drawing planar graphs with circular arcs
In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in which edges are drawn using exactly one circular arc. We also give an algorithm for drawing n-vertex planar graphs such that the edges are sequences of two continuous circular arcs. The algorithm runs in O(n) time and embeds the graph on the O(n) × O(n) grid, while maintaining Θ(1/d(v)) angular resolution, where d(v) is the degree of vertex v. Since in this case we use circular arcs of infinite radius, this is also the first algorithm that simultaneously achieves good angular resolution, small area, and at most one bend per edge using straight-line segments. Finally, we show how to create drawings in which edges are smooth C1-continuous curves, represented by a sequence of at most three circular arcs.
1870789
Replication and retrieval strategies of multidimensional data on parallel disks
Aside from enhancing data availability during disk failures, replication of data is also used to speed up I/O performance of read-intensive applications. There are two issues that need to be addressed: (a) data placement (Which disks should store the copies of each data block?) and (b) scheduling (Given a query Q, and a placement scheme P of the data, from which disk should each block in Q be retrieved so that retrieval time is minimized?) In this paper, we consider range queries and assume that the dataset is a multidimensional grid and r copies of each unit block of the grid must be stored among M disks. To accurately measure performance of a scheduling algorithm, we consider a metric that takes into account the scheduling overhead as well as the time it takes to retrieve the data blocks from the disks. We describe several combinations of data placement schemes and scheduling algorithms and analyze their performance for range queries with respect to the above metric. We then present simulation results for the most interesting case r=2, showing that the strategies do perform better than the previously known method, especially for large queries.
14119951
Drawing Planar Graphs with Circular Arcs
In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in which edges are drawn using exactly one circular arc. We also give an algorithm for drawing n-vertex planar graphs such that the edges are sequences of two continuous circular arcs. The algorithm runs in O(n) time and embeds the graph on the O(n) × O(n) grid, while maintaining θ(1/d(v)) angular resolution, where d(v) is the degree of vertex v. Since in this case we use circular arcs of infinite radius, this is also the first algorithm to simultaneously achieve good angular resolution, small area and at most one bend per edge using straight-line segments. Finally, we show how to create drawings in which edges are smooth C 1-continuous curves, represented by a sequence of at most three circular arcs.
14244824
LGen - A Lattice-Based Candidate Set Generation Algorithm for I/O Efficient Association Rule Mining
Most algorithms for association rule mining are variants of the basic Apriori algorithm [2]. One characteristic of these Aprioribased algorithms is that candidate itemsets are generated in rounds, with the size of the itemsets incremented by one per round. The number of database scans required by Apriori-based algorithms thus depends on the size of the largest large itemsets. In this paper we devise a more general candidate set generation algorithm, LGen, which generates candidate itemsets of multiple sizes during each database scan. We show that, given a reasonable set of suggested large itemsets, LGen can significantly reduce the number of I/O passes required. In the best cases, only two passes are sufficient to discover all the large itemsets irrespective of the size of the largest ones.
29287906
Further complexity reduction of parallel FIR filters
Based on recently published low complexity parallel FIR filter structures, this paper proposes a new scheme to further reduce their hardware complexity. A FIR filter is firstly transformed into linear convolution, which is then implemented by the iterated short convolution algorithm. This linear convolution structure for FIR filter is used as a processing core to implement the subfilters of previously proposed parallel FIR filter structures. A large amount of hardware can be saved by the new scheme. For example, for a 576-tap FIR filter, when the parallelism level changes from 12 to 72, the new scheme can save 1755 to 3375 multiplications at the cost of 21 to 4658 additions and 1516 to 4749 delay elements, respectively.
15084300
Joint Optimization of Word Alignment and Epenthesis Generation for Chinese to Taiwanese Sign Synthesis
This work proposes a novel approach to translate Chinese to Taiwanese sign language and to synthesize sign videos. An aligned bilingual corpus of Chinese and Taiwanese sign language (TSL) with linguistic and signing information is also presented for sign language translation. A two-pass alignment in syntax level and phrase level is developed to obtain the optimal alignment between Chinese sentences and Taiwanese sign sequences. For sign video synthesis, a scoring function is presented to develop motion transition-balanced sign videos with rich combinations of intersign transitions. Finally, the maximum a posteriori (MAP) algorithm is employed for sign video synthesis based on joint optimization of two-pass word alignment and intersign epenthesis generation. Several experiments are conducted in an educational environment to evaluate the performance on the comprehension of sign expression. The proposed approach outperforms the IBM Model2 in sign language translation. Moreover, deaf students perceived sign videos generated by the proposed method to be satisfactory
14354011
A study of the total chromatic number of equibipartite graphs
Abstract The total chromatic number χ t ( G ) of a graph G is the least number of colors needed to color the vertices and edges of G so that no adjacent vertices or edges receive the same color, no incident edges receive the same color as either of the vertices it is incident with. In this paper, we obtain some results of the total chromatic number of the equibipartite graphs of order 2 n with maximum degree n − 1. As a part of our results, we disprove the biconformability conjecture.
11083681
MARD: a new method to detect differential gene expression in treatment-control time courses
MOTIVATION
Characterizing the dynamic regulation of gene expression by time course experiments is becoming more and more important. A common problem is to identify differentially expressed genes between the treatment and control time course. It is often difficult to compare expression patterns of a gene between two time courses for the following reasons: (1) the number of sampling time points may be different or hard to be aligned between the treatment and the control time courses; (2) estimation of the function that describes the expression of a gene in a time course is difficult and error-prone due to the limited number of time points. We propose a novel method to identify the differentially expressed genes between two time courses, which avoids direct comparison of gene expression patterns between the two time courses.


RESULTS
Instead of attempting to 'align' and compare the two time courses directly, we first convert the treatment and control time courses into neighborhood systems that reflect the underlying relationships between genes. We then identify the differentially expressed genes by comparing the two gene relationship networks. To verify our method, we apply it to two treatment-control time course datasets. The results are consistent with the previous results and also give some new biologically meaningful findings.


AVAILABILITY
The algorithm in this paper is coded in C++ and is available from http://leili-lab.cmb.usc.edu/yeastaging/projects/MARD/