bluuebunny/crossref_metadata_2025 huggingface dataset:
An allolactose trapped at the lacZ β-galactosidase active site with its galactosyl moiety in a 4H3 conformation provides insights into the formation, conformation, and stabilization of the transition state
Authors: Wheatley Robert W. , Huber Reuben E.
Published: June 2015

When lactose was incubated with G794A-β-galactosidase (a variant with a “closed” active site loop that binds transition state analogs well) an allolactose was trapped with its Gal moiety in a 4H3 conformation, similar to the oxocarbenium ion-like conformation expected of the transition state. The numerous interactions formed between the 4H3 structure and β-galactosidase indicate that this structure is representative of the transition state. This conformation is also very similar to that of d-galactono-1,5-lactone, a good transition state analog. Evidence indicates that substrates take up the 4H3 conformation during migration from the shallow to the deep mode. Steric forces utilizing His418 and other residues are important for positioning the O1 leaving group into a quasi-axial position. An electrostatic interaction between the O5 of the distorted Gal and Tyr503 as well as C–H–π bonds with Trp568 are also significant. Computational studies of the energy of sugar ring distortion show that the β-galactosidase reaction itinerary is driven by energetic considerations in utilization of a 4H3 transition state with a novel 4C1-4H3-4C1 conformation itinerary. To our knowledge, this is the first X-ray crystallographic structural demonstration that the transition state of a natural substrate of a glycosidase has a 4H3 conformation.
Gas migration through water-saturated bentonite–sand mixtures, COx argillite, and their interfaces
Authors: Liu Jiang-Feng , Song Yang , Skoczylas Frédéric , Liu Jian
Published: June 2015

France’s deep-seated nuclear waste repository consists of a natural barrier located at a depth of 500 m in a Callovo-Oxfordian clayey formation. This repository has artificial barriers that include plugs of swelling clay (MX80 bentonite – sand mixtures) for sealing purposes. This paper focuses on the gas migration properties of water-saturated bentonite–sand mixtures and their interfaces with COx argillite. The main contribution of our study is the identification of a preferential gas migration pathway by measuring the downstream gas breakthrough pressures and gas flow rates. The water permeabilities of the bentonite–sand mixtures and their interfaces with COx argillite or COx argillite itself are the same order of magnitude (10−20–10−21 m2). Thus, water tightness can be obtained for these materials when they become completely saturated. The results obtained from the gas breakthrough tests suggest that both the COx argillite and its interface with the bentonite–sand mixture can act as preferential pathways for gas migration. The transport of the gas through the COx argillite or through its interface with the bentonite–sand mixture depends on the initial state of the COx argillite.
Insights into thermoadaptation and the evolution of mesophily from the bacterial phylum Thermotogae
Authors: Pollo Stephen M.J. , Zhaxybayeva Olga , Nesbø Camilla L.
Published: June 2015

Thermophiles are extremophiles that grow optimally at temperatures >45 °C. To survive and maintain function of their biological molecules, they have a suite of characteristics not found in organisms that grow at moderate temperature (mesophiles). At the cellular level, thermophiles have mechanisms for maintaining their membranes, nucleic acids, and other cellular structures. At the protein level, each of their proteins remains stable and retains activity at temperatures that would denature their mesophilic homologs. Conversely, cellular structures and proteins from thermophiles may not function optimally at moderate temperatures. These differences between thermophiles and mesophiles presumably present a barrier for evolutionary transitioning between the 2 lifestyles. Therefore, studying closely related thermophiles and mesophiles can help us determine how such lifestyle transitions may happen. The bacterial phylum Thermotogae contains hyperthermophiles, thermophiles, mesophiles, and organisms with temperature ranges wide enough to span both thermophilic and mesophilic temperatures. Genomic, proteomic, and physiological differences noted between other bacterial thermophiles and mesophiles are evident within the Thermotogae. We argue that the Thermotogae is an ideal group of organisms for understanding of the response to fluctuating temperature and of long-term evolutionary adaptation to a different growth temperature range.
Modification in the properties of paper by using cellulase-free xylanase produced from alkalophilic Cellulosimicrobium cellulans CKMX1 in biobleaching of wheat straw pulp
Authors: Walia Abhishek , Mehta Preeti , Guleria Shiwani , Shirkot Chand Karan
Published: June 2015

Alkalophilic Cellulosimicrobium cellulans CKMX1 isolated from mushroom compost is an actinomycete that produces industrially important and environmentally safer thermostable cellulase-free xylanase, which is used in the pulp and paper industry as an alternative to the use of toxic chlorinated compounds. Strain CKMX1 was previously characterized by metabolic fingerprinting, whole-cell fatty acids methyl ester analysis, and 16S rDNA and was found to be C. cellulans CKMX1. Crude enzyme (1027.65 U/g DBP) produced by C. cellulans CKMX1, having pH and temperature optima of 8.0 and 60 °C, respectively, in solid state fermentation of apple pomace, was used in the production of bleached wheat straw pulp. Pretreatment with xylanase at a dose of 5 U/g after pulping decreased pulp kappa points by 1.4 as compared with the control. Prebleaching with a xylanase dose of 5 U/g pulp reduced the chlorine charge by 12.5%, increased the final brightness points by approximately 1.42% ISO, and improved the pulp strength properties. Xylanase could be substituted for alkali extraction in C–Ep–D sequence and used for treating chemically bleached pulp, resulting in bleached pulp with higher strength properties. Modification of bleached pulp with 5 U of enzyme/g increased pulp whiteness and breaking length by 1.03% and 60 m, respectively; decreased tear factor of pulp by 7.29%; increased bulk weight by 3.99%, as compared with the original pulp. Reducing sugars and UV-absorbing lignin-derived compound values were considerably higher in xylanase-treated samples. Cellulosimicrobium cellulans CKMX1 has a potential application in the pulp and paper industries.
Vacuum energy and the cosmological constant
Authors: Bass Steven D.
Published: June 2015

The accelerating expansion of the Universe points to a small positive value for the cosmological constant or vacuum energy density. We discuss recent ideas that the cosmological constant plus Large Hadron Collider (LHC) results might hint at critical phenomena near the Planck scale.
Fundamental constants and cosmic vacuum: The micro and macro connection
Authors: Fritzsch Harald , Solà Joan
Published: June 2015

The idea that the vacuum energy density [Formula: see text] could be time-dependent is a most reasonable one in the expanding Universe; in fact, much more reasonable than just a rigid cosmological constant for the entire cosmic history. Being [Formula: see text] dynamical, it offers a possibility to tackle the cosmological constant problem in its various facets. Furthermore, for a long time (most prominently since Dirac’s first proposal on a time variable gravitational coupling) the possibility that the fundamental “constants” of Nature are slowly drifting with the cosmic expansion has been continuously investigated. In the last two decades, and specially in recent times, mounting experimental evidence attests that this could be the case. In this paper, we consider the possibility that these two groups of facts might be intimately connected, namely that the observed acceleration of the Universe and the possible time variation of the fundamental constants are two manifestations of the same underlying dynamics. We call it: the “micro and macro connection”, and on its basis we expect that the cosmological term in Einstein’s equations, Newton’s coupling and the masses of all the particles in the Universe, both the dark matter (DM) particles and the ordinary baryons and leptons, should all drift with the cosmic expansion. Here, we discuss specific cosmological models realizing such possibility in a way that preserves the principle of covariance of general relativity (GR).
Influence of the 2D periodic potential shape on the jump diffusion in the strong collision limit
Authors: Elkoraychy E. , Kotri A. , Mazroui M. , Sbiaai K. , Saadouni K.
Published: June 2015

In this paper, the dynamic properties of a single adatom subject to a two-dimensional periodic potential of square symmetry are investigated. This problem is addressed through the strong-collision model, where the dynamical interaction of the adatom with the substrate is modeled by well-separated collisions that thermalize the velocity. By means of molecular dynamics simulations, we calculate the jump-length probability distribution and the diffusion coefficient as a function of x–y coupling term and of the collision frequency [Formula: see text]. Our numerical results show that the x–y coupling always suppresses a large proportion of long jumps, inducing thus a decrease of the diffusion coefficient for all values of [Formula: see text]. Implications of these findings are briefly discussed.
Structural, electronic and magnetic properties of Ru2CrGe and Ru2MnGe: FP-LAPW calculations
Authors: Aarizou Zineb , Bahlouli Soumia , Elchikh Mokhtar
Published: June 2015

Structural and magnetic properties as well as the electronic structures of [Formula: see text] Heusler alloys were investigated in the framework of first principle calculation. Using the full-potential linearized augmented plane wave (FP-LAPW) in connection with the generalized gradient approximation (GGA) treatment of exchange-correlation energy, we have performed the structural optimization in the non-magnetic (NM) and three different magnetic configurations: FM, AFM-I and AFM-II. We have found that our two compounds are stable for the AFM-II state, which agree with the available experimental and theoretical results. The exchange constants [Formula: see text] and [Formula: see text] as well as the temperature of transition to the paramagnetic state [Formula: see text] were estimated here by the use of the energy difference method and the mean field approximation. The electronic structure of our compounds in their magnetic state was also studied. The GGA [Formula: see text]+ [Formula: see text]U method has also been used to take into account the strong correlations among the d orbitals of [Formula: see text] and [Formula: see text] atoms. This has considerably improved both the electronic and magnetic results which became close to the corresponding experimental data. We have finally studied the thermodynamic properties using the quasi-harmonic Debye model as implemented in the Gibbs Program.
An ab initio approach on superconducting properties of Mo3X(X = Si,Ga,Ge) compounds
Authors: Subhashree G. , Sankar S. , Krithiga R.
Published: June 2015

Self-consistent first principles calculations on type II weakly coupled superconducting [Formula: see text] compounds of A15 phase are performed to understand their fundamental characteristics of the electronic, thermal and superconducting properties. The bulk modulus [Formula: see text], Debye temperature [Formula: see text], density of states (DOS) [Formula: see text], electron–phonon coupling constant [Formula: see text], superconducting transition temperature [Formula: see text], and electronic specific heat coefficient [Formula: see text] have been computed in terms of the electronic structure results, obtained by using the tight-binding linear muffin-tin orbital method. It is observed that all the three materials have their electronic properties dominated by d-orbital at Fermi energy. Thermal and superconducting properties calculated here are found to corroborate well with the experimental results of literature.
Thermoelectric properties of In-filled and Te-doped CoSb3 prepared by high-pressure and high-temperature
Authors: Deng Le , Wang Li Bin , Qin Jie Ming , Zheng Tao , Ni Jing , Jia Xiao Peng , Ma Hong An
Published: June 2015

A novel chemical alloying method of high-pressure and high-temperature (HPHT) has been used for the synthesis of bulk-skutterudite [Formula: see text]. Through HPHT method, the synthesis time has been shortened from a few days to 30[Formula: see text]min. The samples of [Formula: see text] skutterudites were synthesized at 1.8–3.3[Formula: see text]GPa. We have studied the phase, the microstructure, and the temperature-dependent thermoelectric properties. The Seebeck coefficient, electrical conductivity and thermal conductivity were measured in the temperature range of 295–673[Formula: see text]K. As we expected, the thermal conductivity of sample [Formula: see text] decreased with the increase of the synthetic pressure. A maximal ZT of 0.64 was achieved for the [Formula: see text] synthesized at 1.8[Formula: see text]GPa at 673[Formula: see text]K. These results revealed that HPHT method may be helpful for optimizing electrical conductivity and thermal conductivity in a comparatively independent way.
Image denoising based on edge detection and prethresholding Wiener filtering of multi-wavelets fusion
Authors: Gao Liang , Wang Gang , Liu Jinhai
Published: June 2015

In this paper, we describe a method for removing Gaussian noise from digital images, based on edge detection and prethresholding Wiener filtering of multi-wavelets fusion. First, we decompose the noisy image by using multiple wavelets, then the edge of image is detected via wavelet multi-scale edge detection. On this basis, the wavelet coefficients belonging to the edge position are dealt with the improved wavelet threshold method and the others are dealt with the prethresholding Wiener filtering. Finally, we use the fusion algorithm based on wavelet analysis to obtain the denoised image. The experimental results show that this method not only can remove the noise without blurring the edges and the important characteristics of the images effectively, but also can highlight the characteristics of image edge compared with the existing methods. The denoised images have higher peak signal to noise ratio (PSNR) and mean structural similarity (MSSIM), hence the method is of great application value.
Aggregation behavior of tetraphenylporphyrin in aqueous surfactant solutions: Chiral premicellar J-aggregate formation
Authors: Gradova Margaret A. , Artemov Vladimir V. , Lobanov Anton V.
Published: June 2015

Porphyrin-surfactant interactions in aqueous solutions are known to result in the selfassembly of various supramolecular structures, including pigment-surfactant complexes, J- and H-aggregates, and solubilized dye species. Detailed studies on the mechanisms of the intermolecular interactions governing the above self-assembly processes allow to predict the aggregation state and hence, the photophysical properties of the dye-surfactant assemblies in order to perform a direct synthesis of the desired porphyrin-based nanostructures at the appropriate experimental conditions. This paper describes a novel example of the surfactant-induced J-aggregate formation from the diprotonated hydrophobic tetraphenylporphyrin species in submicellar aqueous anionic surfactant solutions. The above assemblies are characterized by a rod-like morphology and possess supramolecular chirality according to the CD measurements.
Constraining magmatic fluxes through thermal modelling of contact metamorphism
Authors: Floess David , Baumgartner Lukas P.
Published: June 2015

The thermal evolution of a contact aureole is strongly dependent on the emplacement mode of the intrusion that is causing the thermal anomaly. Inferences on the emplacement mode can be made if solid temperature estimates are available. The contact aureole of the Western Adamello Tonalite provides a unique combination of magma ascent close to the host rock and suitable rock chemistry. We use three mineral reactions at different distances in the aureole in combination with phase petrology to estimate temperatures. These temperatures are not reproducible by thermal models considering the emplacement of the intrusion as a single batch. The external zone of the intrusion represents a feeder conduit in which magma was transported. We investigated the thermal effect of the conduit on the host rocks using thermal models. Different thermal profiles for the aureole are obtained by varying flow/no-flow times, conduit thickness and magma temperature. We show that only a few combinations match the temperature constraints in the aureole, and that the amount of magma transported through the conduit can be calculated. A comparison with time-averaged fluxes of recent volcanoes and the presence of reworked volcanic sediments in the surroundings of the Adamello batholith indicate that the calculated rates and volumes are plausible.

Supplementary material:

Tables comparing sample compositions with literature experimental data are available at
http://www.geolsoc.org.uk/SUP18847
Exascale computing and big data
Authors: Reed Daniel A. , Dongarra Jack
Published: June 2015

Scientific discovery and engineering innovation requires unifying traditionally separated high-performance computing and big data analytics.
Layout-Aware Mixture Preparation of Biochemical Fluids on Application-Specific Digital Microfluidic Biochips
Authors: Roy Sudip , Chakrabarti Partha P. , Kumar Srijan , Chakrabarty Krishnendu , Bhattacharya Bhargab B.
Published: June 2015

The recent proliferation of digital microfluidic (DMF) biochips has enabled rapid on-chip implementation of many biochemical laboratory assays or protocols. Sample preprocessing, which includes dilution and mixing of reagents, plays an important role in the preparation of assays. The automation of sample preparation on a digital microfluidic platform often mandates the execution of a mixing algorithm, which determines a sequence of droplet mix-split steps (usually represented as a mixing graph). However, the overall cost and performance of on-chip mixture preparation not only depends on the mixing graph but also on the resource allocation and scheduling strategy, for instance, the placement of boundary reservoirs or dispensers, mixer modules, storage units, and physical design of droplet-routing pathways. In this article, we first present a new mixing algorithm based on a number-partitioning technique that determines a layout-aware mixing tree corresponding to a given target ratio of a number of fluids. The mixing graph produced by the proposed method can be implemented on a chip with a fewer number of crossovers among droplet-routing paths as well as with a reduced reservoir-to-mixer transportation distance. Second, we propose a routing-aware resource-allocation scheme that can be used to improve the performance of a given mixing algorithm on a chip layout. The design methodology is evaluated on various test cases to demonstrate its effectiveness in mixture preparation with the help of two representative mixing algorithms. Simulation results show that on average, the proposed scheme can reduce the number of crossovers among droplet-routing paths by 89.7% when used in conjunction with the new mixing algorithm, and by 75.4% when an earlier algorithm [Thies et al. 2008] is used.
High-Throughput Logic Timing Simulation on GPGPUs
Authors: Holst Stefan , Imhof Michael E. , Wunderlich Hans-Joachim
Published: June 2015

Many EDA tasks such as test set characterization or the precise estimation of power consumption, power droop and temperature development, require a very large number of time-aware gate-level logic simulations. Until now, such characterizations have been feasible only for rather small designs or with reduced precision due to the high computational demands.

The new simulation system presented here is able to accelerate such tasks by more than two orders of magnitude and provides for the first time fast and comprehensive timing simulations for industrial-sized designs. Hazards, pulse-filtering, and pin-to-pin delay are supported for the first time in a GPGPU accelerated simulator, and the system can easily be extended to even more realistic delay models and further applications.

A sophisticated mapping with efficient memory utilization and access patterns as well as minimal synchronizations and control flow divergence is able to use the full potential of GPGPU architectures. To provide such a mapping, we combine for the first time the versatility of event-based timing simulation and multi-dimensional parallelism used in GPU-based gate-level simulators. The result is a throughput-optimized timing simulation algorithm, which runs many simulation instances in parallel and at the same time fully exploits gate-parallelism within the circuit.
Adaptive Generation of Unique IDs for Digital Chips through Analog Excitation
Authors: Suresh Chandra K. H. , Ozev Sule , Sinanoglu Ozgur
Published: June 2015

Globalization of the integrated circuit design and manufacturing flow has successfully ameliorated design complexity and fabrication cost challenges, and helped deliver cost-effective products while meeting stringent time-to-market requirements. On the flip side, it has resulted in various forms of security vulnerabilities in the supply chain that involves designers, fabs, test facilities, and distributors until the end-product reaches customers. One of the biggest threats to semiconductor industry today is the entry of aged, reject, or cloned parts, that is, counterfeit chips, into the supply chain, leading to annual revenue losses in the order of billions of dollars. While traceability of chips between trusted parties can help monitor the supply chain at various points in the flow, existing solutions are in the form of integrating costly hardware units on chip, or utilizing easy-to-circumvent inspection-based detection techniques. In this article, we propose a technique for adaptive unique ID generation that leverages process variations, enabling chip traceability. The proposed method stimulates digital chips with an analog signal from the supply lines, which serve as primary inputs to each gate in the signal path. Using a sinusoidal signal that exercises the transistors as gain components, we create a chip-specific response that can be post-processed into a digital ID. The proposed technique enables quick and cost-effective authenticity validation that requires no on-chip hardware support. Our simulation and experimentation on actual chips show that the proposed technique is capable of generating unique IDs even in the presence of environmental noise.
Lazy-RTGC
Authors: Zhang Qi , Li Xuandong , Wang Linzhang , Zhang Tian , Wang Yi , Shao Zili
Published: June 2015

Due to many attractive and unique properties, NAND flash memory has been widely adopted in mission-critical hard real-time systems and some soft real-time systems. However, the nondeterministic garbage collection operation in NAND flash memory makes it difficult to predict the system response time of each data request. This article presents
Lazy-RTGC
, a real-time lazy garbage collection mechanism for NAND flash memory storage systems. Lazy-RTGC adopts two design optimization techniques: on-demand page-level address mappings, and partial garbage collection. On-demand page-level address mappings can achieve high performance of address translation and can effectively manage the flash space with the minimum RAM cost. On the other hand, partial garbage collection can provide the guaranteed system response time. By adopting these techniques, Lazy-RTGC jointly optimizes both the average and the worst system response time, and provides a lower bound of reclaimed free space. Lazy-RTGC is implemented in FlashSim and compared with representative real-time NAND flash memory management schemes. Experimental results show that our technique can significantly improve both the average and worst system performance with very low extra flash-space requirements.
Array Interleaving—An Energy-Efficient Data Layout Transformation
Authors: Sharma Namita , Panda Preeti Ranjan , Catthoor Francky , Raghavan Praveen , Aa Tom Vander
Published: June 2015

Optimizations related to memory accesses and data storage make a significant difference to the performance and energy of a wide range of data-intensive applications. These techniques need to evolve with modern architectures supporting wide memory accesses. We investigate
array interleaving
, a data layout transformation technique that achieves energy efficiency by combining the storage of data elements from multiple arrays in contiguous locations, in an attempt to exploit spatial locality. The transformation reduces the number of memory accesses by loading the right set of data into vector registers, thereby minimizing redundant memory fetches. We perform a global analysis of array accesses, and account for possibly different array behavior in different loop nests that might ultimately lead to changes in data layout decisions for the same array across program regions. Our technique relies on detailed estimates of the savings due to interleaving, and also the cost of performing the actual data layout modifications. We also account for the vector register widths and the possibility of choosing the appropriate granularity for interleaving. Experiments on several benchmarks show a 6--34% reduction in memory energy due to the strategy.
Using free and open source tools to manage software quality
Authors: Dowling Phelim , McGrath Kevin
Published: June 2015

An agile process implementation
Bounded-Distance Network Creation Games
Authors: Bilò Davide , Gualà Luciano , Proietti Guido
Published: June 2015

A
network creation game
simulates a decentralized and noncooperative construction of a communication network. Informally, there are
n
players sitting on the network nodes, which attempt to establish a reciprocal communication by activating, thereby incurring a certain cost, any of their incident links. The goal of each player is to have all the other nodes as close as possible in the resulting network, while buying as few links as possible. According to this intuition, any model of the game must then appropriately address a balance between these two conflicting objectives. Motivated by the fact that a player might have a strong requirement about her centrality in the network, we introduce a new setting in which a player who maintains her (maximum or average) distance to the other nodes within a given bound incurs a cost equal to the number of activated edges; otherwise her cost is unbounded. We study the problem of understanding the structure of pure Nash equilibria of the resulting games, which we call M
ax
BD and S
um
BD, respectively. For both games, we show that when distance bounds associated with players are nonuniform, then equilibria can be arbitrarily bad. On the other hand, for M
ax
BD, we show that when nodes have a uniform bound
D
≥ 3 on the maximum distance, then the
price of anarchy
(PoA) is lower and upper bounded by 2 and
O
(
n

1/⌊log
3
D
⌋+1

), respectively (i.e., PoA is constant as soon as
D
is Ω(
n
ϵ
), for any ϵ > 0), while for the interesting case
D
=2, we are able to prove that the PoA is Ω(√
n
) and
O
(√
n
log
n
). For the uniform S
um
BD, we obtain similar (asymptotically) results and moreover show that PoA becomes constant as soon as the bound on the average distance is 2

ω
(√log
n
)

.
Anti-circumvention rules limit reverse engineering
Authors: Samuelson Pamela
Published: June 2015

Considering some of the requested exceptions to technical protection mechanisms.
Respecting people and respecting privacy
Authors: Camp L. Jean
Published: June 2015

Minimizing data collection to protect user privacy and increase security.
Preserving the digital record of computing history
Authors: Anderson David
Published: June 2015

Reflecting on the complexities associated with maintaining rapidly changing information technology.
An updated software Almanac
Authors: Armour Phillip G.
Published: June 2015

Research into what makes software projects succeed.
The Effect of Data Caps upon ISP Service Tier Design and Users
Authors: Dai Wei , Jordan Scott
Published: June 2015

We model the design and impact of Internet pricing plans with data caps. We consider a monopoly ISP that maximizes its profit by setting tier prices, tier rates, network capacity, data caps, and overage charges. We show that when data caps are used to maximize profit, a monopoly ISP will keep the basic tier price the same, increase the premium tier rate, and decrease the premium tier price and the basic tier rate. We give analytical and numerical results to illustrate the increase in ISP profit, and the corresponding changes in user tier choices, user surplus, and social welfare.
Interaction-Based Recommendations for Online Communities
Authors: Nepal Surya , Paris Cecile , Pour Payam Aghaei , Freyne Jill , Bista Sanat Kumar
Published: June 2015

A key challenge in online communities is that of keeping a community active and alive. All online communities work hard to keep their members through various initiatives, such as personalisation and recommendation technologies. In online communities aimed at supporting behavioural change, that is, in domains such as diet, lifestyle, or the environment, the main reason for participation is not to connect with real-world friends for sharing and communicating, but to meet and gain support from like-minded people in an online environment. Introducing personalisation and recommendation features in these networks is challenging, as traditional approaches leverage the densely populated friendship relations found in typical social networks, and these are not present in these new community types. We address this challenge by looking beyond the articulated friendships of a community for evidence of relationships. In particular, we look at the interactions of members of an online community with other members and resources. In this article, we present a social behaviour model and apply it to two types of recommendation systems, a people recommender and a content recommender system. We evaluate our systems using the interaction logs of an online diet and lifestyle community in which 5,000 Australians participated in a 12-week programme. Our results show that our social behaviour-based recommendation algorithms outperform baselines, friendship-based, and link-prediction algorithms.
Cache efficient functional algorithms
Authors: Blelloch Guy E. , Harper Robert
Published: June 2015

The widely studied I/O and ideal-cache models were developed to account for the large difference in costs to access memory at different levels of the memory hierarchy. Both models are based on a two level memory hierarchy with a fixed size fast memory (cache) of size
M
, and an unbounded slow memory organized in blocks of size
B.
The cost measure is based purely on the number of block transfers between the primary and secondary memory. All other operations are free. Many algorithms have been analyzed in these models and indeed these models predict the relative performance of algorithms much more accurately than the standard Random Access Machine (RAM) model. The models, however, require specifying algorithms at a very low level, requiring the user to carefully lay out their data in arrays in memory and manage their own memory allocation.

We present a cost model for analyzing the memory efficiency of algorithms expressed in a simple functional language. We show how some algorithms written in standard forms using just lists and trees (no arrays) and requiring no explicit memory layout or memory management are efficient in the model. We then describe an implementation of the language and show provable bounds for mapping the cost in our model to the cost in the ideal-cache model. These bounds imply that purely functional programs based on lists and trees with no special attention to any details of memory layout can be asymptotically as efficient as the carefully designed imperative I/O efficient algorithms. For example we describe an
o
(
n/B
log

M/B
n/B

) cost sorting algorithm, which is optimal in the ideal cache and I/O models.
Beyond Independent Relevance
Authors: Zhai ChengXiang , Cohen William W. , Lafferty John
Published: June 2015

We present a non-traditional retrieval problem we call subtopic retrieval. The subtopic retrieval problem is concerned with finding documents that cover many different subtopics of a query topic. In such a problem, the utility of a document in a ranking is dependent on other documents in the ranking, violating the assumption of independent relevance which is assumed in most traditional retrieval methods. Subtopic retrieval poses challenges for evaluating performance, as well as for developing effective algorithms. We propose a framework for evaluating subtopic retrieval which generalizes the traditional precision and recall metrics by accounting for intrinsic topic difficulty as well as redundancy in documents. We propose and systematically evaluate several methods for performing subtopic retrieval using statistical language models and a maximal marginal relevance (MMR) ranking strategy. A mixture model combined with query likelihood relevance ranking is shown to modestly outperform a baseline relevance ranking on a data set used in the TREC interactive track.
Report on the Fourth Workshop on Location and the Web (LocWeb 2014)
Authors: Ahlers Dirk , Wilde Erik , Martins Bruno
Published: June 2015

Location is a major aspect behind many approaches in Information Retrieval, naturally appearing in diverse forms and as a cross-cutting topic. To give the location topic an adequate venue, LocWeb 2014 restarted a workshop series at the intersection of geospatial search, information management, and Web architecture, with a main focus on location-aware information access. LocWeb has in the past been a 'travelling' workshop, gathering views from different communities, but always centered on the topic of location. As previously, contributions to the workshop reflected a multitude of fields that demand and use location features and geospatial information, and LocWeb 2014 featured presentations that look at the topic of location on the Web from an interdisciplinary perspective. Reflecting this interdisciplinarity, LocWeb 2014 consisted of an interesting variety of contributions from a range of topics: one keynote, four long and two short papers, and a discussion session. This report gives an overview of the workshop and summarizes its major contributions.
Bandits with Budgets
Authors: Combes Richard , Jiang Chong , Srikant Rayadurgam
Published: June 2015

We investigate multi-armed bandits with budgets, a natural model for ad-display optimization encountered in search engines. We provide asymptotic regret lower bounds satisfied by any algorithm, and propose algorithms which match those lower bounds. We consider different types of budgets: scenarios where the advertiser has a fixed budget over a time horizon, and scenarios where the amount of money that is available to spend is incremented in each time slot. Further, we consider two different pricing models, one in which an advertiser is charged for each time her ad is shown (i.e., for each impression) and one in which the advertiser is charged only if a user clicks on the ad. For all of these cases, we show that it is possible to achieve O(log(T)) regret. For both the cost-per-impression and cost-per-click models, with a fixed budget, we provide regret lower bounds that apply to any uniformly good algorithm. Further, we show that B-KL-UCB, a natural variant of KL-UCB, is asymptotically optimal for these cases. Numerical experiments (based on a real-world data set) further suggest that B-KL-UCB also has the same or better finite-time performance when compared to various previously proposed (UCB-like) algorithms, which is important when applying such algorithms to a real-world problem.
Learning to Rank
Authors: Combes Richard , Magureanu Stefan , Proutiere Alexandre , Laroche Cyrille
Published: June 2015

Algorithms for learning to rank Web documents, display ads, or other types of items constitute a fundamental component of search engines and more generally of online services. In such systems, when a user makes a request or visits a web page, an ordered list of items (e.g. documents or ads) is displayed; the user scans this list in order, and clicks on the first relevant item if any. When the user clicks on an item, the reward collected by the system typically decreases with the position of the item in the displayed list. The main challenge in the design of sequential list selection algorithms stems from the fact that the probabilities with which the user clicks on the various items are unknown and need to be learned. We formulate the design of such algorithms as a stochastic bandit optimization problem. This problem differs from the classical bandit framework: (1) the type of feedback received by the system depends on the actual relevance of the various items in the displayed list (if the user clicks on the last item, we know that none of the previous items in the list are relevant); (2) there are inherent correlations between the average relevance of the items (e.g. the user may be interested in a specific topic only). We assume that items are categorized according to their topic and that users are clustered, so that users of the same cluster are interested in the same topic. We investigate several scenarios depending on the available side-information on the user before selecting the displayed list: (a) we first treat the case where the topic the user is interested in is known when she places a request; (b) we then study the case where the user cluster is known but the mapping between user clusters and topics is unknown. For both scenarios, we derive regret lower bounds and devise algorithms that approach these fundamental limits.
Social Network Monetization via Sponsored Viral Marketing
Authors: Chalermsook Parinya , Das Sarma Atish , Lall Ashwin , Nanongkai Danupon
Published: June 2015

Viral marketing is a powerful tool for online advertising and sales because it exploits the influence people have on one another. While this marketing technique has been beneficial for advertisers, it has not been shown how the social network
providers
such as Facebook and Twitter can benefit from it. In this paper, we initiate the study of
sponsored viral marketing
where a social network provider that has complete knowledge of its network is hired by several advertisers to provide viral marketing. Each advertiser has its own advertising budget and a fixed amount they are willing to pay for each user that adopts their product or shares their ads. The goal of the social network provider is to gain the most revenue from the advertisers. Since the products or ads from different advertisers may compete with each other in getting users' attention, and advertisers pay differently per share and have different budgets, it is very important that the social network providers start the "seeds" of the viral marketing of each product at the right places in order to gain the most benefit.

We study both when advertisers have limited and unlimited budgets. In the unlimited budget setting, we give a
tight
approximation algorithm for the above task: we present a polynomial-time
O
(log
n
)-approximation algorithm for maximizing the expected revenue, where
n
is the number of nodes (i.e., users) in the social network, and show that no polynomial-time
O
(log
1-ε
n
)-approximation algorithm exists, unless NP ⊆ DTIME}(
n

poly log
n

). In the limited budget setting, we show that it is hopeless to solve the problem (even approximately): unless P = NP, there is no polynomial-time
O
(
n
1-ε
)-approximation algorithm. We perform experiments on several data sets to compare our provable algorithms to several heuristic baselines.
Online Auctions in IaaS Clouds
Authors: Zhang Xiaoxi , Huang Zhiyi , Wu Chuan , Li Zongpeng , Lau Francis C.M.
Published: June 2015

Auction design has recently been studied for dynamic resource bundling and VM provisioning in IaaS clouds, but is mostly restricted to the one-shot or offline setting. This work targets a more realistic case of online VM auction design, where: (i) cloud users bid for resources into the future to assemble customized VMs with desired occupation durations; (ii) the cloud provider dynamically packs multiple types of resources on heterogeneous physical machines (servers) into the requested VMs; (iii) the operational costs of servers are considered in resource allocation; (iv) both social welfare and the cloud provider's net profit are to be maximized over the system running span. We design truthful, polynomial time auctions to achieve social welfare maximization and/or the provider's profit maximization with good competitive ratios. Our mechanisms consist of two main modules: (1) an online primal-dual optimization framework for VM allocation to maximize the social welfare with server costs, and for revealing the payments through the dual variables to guarantee truthfulness; and (2) a randomized reduction algorithm to convert the social welfare maximizing auctions to ones that provide a maximal expected profit for the provider, with competitive ratios comparable to those for social welfare. We adopt a new application of Fenchel duality in our primal-dual framework, which provides richer structures for convex programs than the commonly used Lagrangian duality, and our optimization framework is general and expressive enough to handle various convex server cost functions. The efficacy of the online auctions is validated through careful theoretical analysis and trace-driven simulation studies.
Exchange of Services in Networks
Authors: Georgiadis Leonidas , Iosifidis George , Tassiulas Leandros
Published: June 2015

Exchange of services and resources in, or over, networks is attracting nowadays renewed interest. However, despite the broad applicability and the extensive study of such models, e.g., in the context of P2P networks, many fundamental questions regarding their properties and efficiency remain unanswered. We consider such a service exchange model and analyze the users' interactions under three different approaches. First, we study a centrally designed service allocation policy that yields the fair total service each user should receive based on the service it offers to the others. Accordingly, we consider a competitive market where each user determines selfishly its allocation policy so as to maximize the service it receives in return, and a coalitional game model where users are allowed to coordinate their policies. We prove that there is a unique equilibrium exchange allocation for both game theoretic formulations, which also coincides with the central fair service allocation. Furthermore, we characterize its properties in terms of the coalitions that emerge and the equilibrium allocations, and analyze its dependency on the underlying network graph. That servicing policy is the natural reference point to the various mechanisms that are currently proposed to incentivize user participation and improve the efficiency of such networked service (or, resource) exchange markets.
Fisher Information-based Experiment Design for Network Tomography
Authors: He Ting , Liu Chang , Swami Ananthram , Towsley Don , Salonidis Theodoros , Bejan Andrei Iu. , Yu Paul
Published: June 2015

Network tomography aims to infer the individual performance of networked elements (e.g., links) using aggregate measurements on end-to-end paths. Previous work on network tomography focuses primarily on developing estimators using the given measurements, while the design of measurements is often neglected. We fill this gap by proposing a framework to design probing experiments with focus on probe allocation, and applying it to two concrete problems: packet loss tomography and packet delay variation (PDV) tomography. Based on the Fisher Information Matrix (FIM), we design the distribution of probes across paths to maximize the best accuracy of unbiased estimators, asymptotically achievable by the maximum likelihood estimator. We consider two widely-adopted objective functions: determinant of the inverse FIM (D-optimality) and trace of the inverse FIM (A-optimality). We also extend the A-optimal criterion to incorporate heterogeneity in link weights. Under certain conditions on the FIM, satisfied by both loss and PDV tomography, we derive explicit expressions for both objective functions. When the number of probing paths equals the number of links, these lead to closed-form solutions for the optimal design; when there are more paths, we develop a heuristic to select a subset of paths and optimally allocate probes within the subset. Observing the dependency of the optimal design on unknown parameters, we further propose an algorithm that iteratively updates the design based on parameter estimates, which converges to the design based on true parameters as the number of probes increases. Using packet-level simulations on real datasets, we verify that the proposed design effectively reduces estimation error compared with the common approach of uniformly distributing probes.
Greedy-Bayes for Targeted News Dissemination
Authors: Massoulié Laurent , Ohannessian Mesrob I. , Proutière Alexandre
Published: June 2015

This work addresses user targeting for news content delivery. Specifically, we wish to disseminate a fresh news content, whose topic is yet unknown, to all interested users, while "spamming" a minimum number of uninterested users. We formulate this as an online stochastic optimization problem that extends in several ways the classical multi-armed bandit problem.

We introduce Greedy-Bayes, a policy with appealing robustness properties. We establish optimal scaling of a suitably defined regret measure in various scenarios of interest. To that end we develop an original proof technique based on martingale concentration inequalities. Numerical experiments show that Greedy-Bayes improves upon Thompson sampling, the state-of-the-art algorithm for bandit problems.

Our analysis further implies that low regret can only be achieved if the assessment of content relevance for one user leverages feedback from users with widely distinct tastes. This impacts the design of efficient news dissemination platforms: existing systems typically do not leverage such negative feedback and could hence be improved upon with adequate extensions.
Resource Allocation and Rate Gains in Practical Full-Duplex Systems
Authors: Marasevic Jelena , Zhou Jin , Krishnaswamy Harish , Zhong Yuan , Zussman Gil
Published: June 2015

Full-duplex communication has the potential to substantially increase the throughput in wireless networks. However, the benefits of full-duplex are still not well understood. In this paper, we characterize the full-duplex rate gains in both single-channel and multi-channel use cases. For the single-channel case, we quantify the rate gain as a function of the remaining self-interference and SNR values. We also provide a sufficient condition under which the sum of uplink and downlink rates on a full-duplex channel is concave in the transmission power levels. Building on these results, we consider the multi-channel case. For that case, we introduce a new realistic model of a small form-factor (e.g., smartphone) full-duplex receiver and demonstrate its accuracy via measurements. We study the problem of jointly allocating power levels to different channels and selecting the frequency of maximum self-interference suppression, where the objective is maximizing the sum of the rates over uplink and downlink OFDM channels. We develop a polynomial time algorithm which is nearly optimal under very mild restrictions. To reduce the running time, we develop an efficient nearly-optimal algorithm under the high SINR approximation. Finally, we demonstrate via numerical evaluations the capacity gains in the different use cases and obtain insights into the impact of the remaining self-interference and wireless channel states on the performance.