Shao B.,Microsoft |
Wang H.,Microsoft |
Proceedings of the ACM SIGMOD International Conference on Management of Data | Year: 2013
Computations performed by graph algorithms are data driven, and require a high degree of random data access. Despite the great progresses made in disk technology, it still cannot provide the level of efficient random access required by graph computation. On the other hand, memory-based approaches usually do not scale due to the capacity limit of single machines. In this paper, we introduce Trinity, a general purpose graph engine over a distributed memory cloud. Through optimized memory management and network communication, Trinity supports fast graph exploration as well as efficient parallel computing. In particular, Trinity leverages graph access patterns in both online and offline computation to optimize memory and communication for best performance. These enable Trinity to support efficient online query processing and offline analytics on large graphs with just a few commodity machines. Furthermore, Trinity provides a high level specification language called TSL for users to declare data schema and communication protocols, which brings great ease-of-use for general purpose graph management and computing. Our experiments show Trinity's performance in both low latency graph queries as well as high throughput graph analytics on web-scale, billion-node graphs. Copyright © 2013 ACM.
Cheng S.-W.,HKUST |
Proceedings of the Annual ACM Symposium on Theory of Computing | Year: 2014
We present an algorithm for computing shortest paths on polyhedral surfaces under convex distance functions. Let n be the total number of vertices, edges and faces of the surface. Our algorithm can be used to compute L1 and L∞ shortest paths on a polyhedral surface in O(n2 log4 n) time. Given an ε ∈ (0, 1), our algorithm can find (1 + ε)- approximate shortest paths on a terrain with gradient constraints and under cost functions that are linear combinations of path length and total ascent. The running time is O (1/√εn2 log n + n 2 log4 n ". This is the first efficient PTAS for such a general setting of terrain navigation. © 2014 ACM.
Jin X.,Oracle Inc. |
Gary Chan S.-H.,HKUST
IEEE Communications Magazine | Year: 2010
Many peer-to-peer systems assume that peers are cooperative to share and relay data. But in the open environment of the Internet, there may be uncooperative malicious peers. To detect malicious peers or reward well behaved ones, a reputation system is often used. In this article we give an overview of P2P reputation systems and investigate two fundamental issues in the design: reputation estimation and query. We classify the state-of-the-art approaches into several categories and study representative examples in each category. We also qualitatively compare them and outline open issues for future research. © 2010 IEEE.
Dong Y.,Tsinghua University |
Fan P.,Tsinghua University |
IEEE Transactions on Vehicular Technology | Year: 2014
High-speed railways (HSRs) have been widely deployed all over the world in recent years. Different from traditional cellular communications, the high mobility of HSR communication makes it essential to implement power allocation (PA) along time. In the HSR case, the transmission rate greatly depends on the distance between the base station (BS) and the train. As a result, the train receives a time-varying data rate service when passing by a BS. It is clear that the most efficient PA will spend all the power when the train is nearest the BS, which will cause great unfairness along time. On the other hand, channel inversion allocation achieves the best fairness in terms of constant rate transmission. However, its power efficiency is much lower. Therefore, power efficiency and fairness along time are two incompatible objects. For the HSR cellular system considered in this paper, a tradeoff between the two is achieved by proposing a temporal proportional-fair PA scheme. In addition, a near-optimal closed-form solution and one algorithm finding ε-optimal allocation are presented. © 2013 IEEE.
Babu P.,HKUST |
Stoica P.,Uppsala University
Signal Processing | Year: 2014
In this note we show that the sparse estimation technique named Square-Root LASSO (SR-LASSO) is connected to a previously introduced method named SPICE. More concretely we prove that the SR-LASSO with a unit weighting factor is identical to SPICE. Furthermore we show via numerical simulations that the performance of the SR-LASSO changes insignificantly when the weighting factor is varied. SPICE stands for sparse iterative covariance-based estimation and LASSO for least absolute shrinkage and selection operator. © 2013 Elsevier B.V.