Ensemble-based clustering of large probabilistic graphs using neighborhood and distance metric learning

Graphs are commonly used to express the communication of various data. Faced with uncertain data, we have probabilistic graphs. As a fundamental problem of such graphs, clustering has many applications in analyzing uncertain data. In this paper, we propose a novel method based on ensemble clustering for large probabilistic graphs. To generate ensemble clusters, we develop a set of probable possible worlds of the initial probabilistic graph. Then, we present a probabilistic co-association matrix as a consensus function to integrate base clustering results. It relies on co-occurrences of node pairs based on the probability of the corresponding common cluster graphs. Also, we apply two improvements in the steps before and after of ensembles generation. In the before step, we append neighborhood information based on node features to the initial graph to achieve a more accurate estimation of the probability between the nodes. In the after step, we use supervised metric learning-based Mahalanobis distance to automatically learn a metric from ensemble clusters. It aims to gain crucial features of the base clustering results. We evaluate our work using five real-world datasets and three clustering evaluation metrics, namely the Dunn index, Davies–Bouldin index, and Silhouette coefficient. The results show the impressive performance of clustering large probabilistic graphs.

     

List update with probabilistic locality of reference

In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that Move-To-Front (MTF) is the best list update algorithm under any such distribution. We also show that the performance of MTF depends on the amount of locality of reference, while the performance of any static list update algorithm is independent of the amount of locality.     

Low area/power decimal addition with carry-select correction and carry-select sum-digits

We improve a carry-select technique for decimal adders, where pairs of corrective carry-out bits for all decimal positions are computed in parallel. Selection is based on the corresponding positional carry-in bits, which are produced by a quaternary parallel prefix carry network. Carry-out bits select pairs of corrected or intact sum-digits to be later selected by actual carry-in bits at the end of addition process. Analytical evaluation and synthesis results for various hardware sharing architectures on binary, decimal, adders, and subtractors show lower area consumption and less power dissipation of the proposed designs at no additional latency, compared to previous works.     

On the relative dominance of paging algorithms

In this paper, we give a finer separation of several known paging algorithms using a new technique called relative interval analysis. This technique compares the fault rate of two paging algorithms across the entire range of inputs of a given size, rather than in the worst case alone. Using this technique, we characterize the relative performance of LRU and LRU-2, as well as LRU and FWF, among others. We also show that look-ahead is beneficial for a paging algorithm, a fact that is well known in practice but it was, until recently, not verified by theory.