Research Love, Again
MSR-TR-2008-167
The Betweenness Centrality Game for Strategic Network Formations
Wei Chen; Shang-Hua Teng; Jiajie Zhu
November 2008
30 p.
https://research.microsoft.com/research/pubs/view.aspx?tr_id=1584
In computer networks and social networks, the betweenness centrality of a node measures the amount of information passing through the node when all pairs are conducting shortest-path exchanges. In this paper, we introduce a strategic network-formation game based on the betweenness centrality. In this game, nodes are selfish players, each of which has some budget to build connections. The goal of each player is to fully utilize her budget to strategically build connections so that her betweenness centrality is as large as possible. We refer to this game as the bounded budget betweenness centrality game or the B3C game. We present both theoretical and experimental results about this game. Theoretically, we show that a general B3C game may not have any nontransient Nash equilibrium and it is in fact NP-hard to determine whether nontransient Nash equilibria exist. Experimentally, we studied the family of uniform B3C games, in which there is an equal amount of information exchange between every pair of nodes, every connection has the same construction cost and every node has enough budget to build $k$ connections. We have discovered several interesting Nash equilibria when k = 2. Our experiments have also inspired us to establish some theoretical results about uniform B3C games. For example, we show that, when $k$ is a variable, it is NP-hard to compute a best response of a node in uniform B$^3$C games; we also prove that a family of symmetric graphs called Abelian Cayley graphs cannot be Nash equilibria for k=2 when the graph is large enough, but there is a unique nontransient Nash equilibrium when k=1. We conjecture, based on our experiments, that every uniform B3C game has a Nash equilibrium, and more strongly, has a Nash equilibrium that is Eulerian.
MSR-TR-2008-169
Migrating enterprise storage to SSDs: analysis of tradeoffs
Dushyanth Narayanan; Eno Thereska; Austin Donnelly; Sameh Elnikety; Antony Rowstron
November 2008
12 p.
https://research.microsoft.com/research/pubs/view.aspx?tr_id=1586
Recently, flash-based solid-state drives (SSDs) have become standard options for laptop and desktop storage, but their impact on enterprises has not been studied. Provisioning enterprise storage is challenging. It requires optimizing for the performance, capacity, power and reliability needs of the expected workload, all while minimizing financial costs. This paper, through analysis of a number of enterprise workloads, provides insights as to when, and how, SSDs should be incorporated into the enterprise storage hierarchy. We describe an automated tool that, given device models and a block-level trace of a workload, determines the least-cost storage configuration. It analyzes the factors that drive the configuration choice, and computes the price points at which different SSD-based solutions will become cost-effective. Our optimization framework is flexible and can be used to design a range of storage hierarchies. When applied to current workloads and prices we find the following in a nutshell: for many enterprise workloads capacity dominates provisioning costs and the current per-gigabyte price of SSDs is between a factor of 3 and 3000 times higher than needed to be cost-effective for full replacement. We find that SSDs can provide some benefit as an intermediate tier for caching and write-ahead logging in a hybrid disk-SSD configuration. Surprisingly, the power savings achieved by SSDs are comparable to power savings from using low-power SATA disks.
MSR-TR-2008-172
Txt-it Notes: Paper Based Text Messaging
Stuart Taylor
November 2008
4 p.
https://research.microsoft.com/research/pubs/view.aspx?tr_id=1589
Text messaging or SMS (Short Message Service) has be-come a ubiquitous form of communication, particularly amongst the younger generations. However, older members of society (and technophobes in general) are often excluded from communicating in this way. In an attempt to overcome this problem, and to try and help foster social relationships among family members, we have designed and imple-mented a paper based system for sending and receiving text messages. We describe the underlying technologies used, along with the design of the paper user interface, the sim-plicity of which allows the system to be used by young and old alike.
MSR-TR-2008-178
Cyberchondria: Studies of the Escalation of Medical Concerns in Web Search
Ryen White; Eric Horvitz
November 2008
33 p.
https://research.microsoft.com/research/pubs/view.aspx?tr_id=1595
The World Wide Web provides an abundant source of medical information. This information can assist people who are not healthcare professionals to better understand health and disease, and to provide them with feasible explanations for symptoms. However, the Web has the potential to increase the anxieties of people who have little or no medical training, especially when Web search is employed as a diagnostic procedure. We use the term cyberchondria to refer to the unfounded escalation of concerns about common symptomatology, based on the review of search results and literature on the Web. We performed a large-scale, longitudinal, log-based study of how people search for medical information online, supported by a large-scale survey of 515 individuals’ health-related search experiences. We focused on the extent to which common, likely innocuous symptoms can escalate into the review of content on serious, rare conditions that are linked to the common symptoms. Our results show that Web search engines have the potential to escalate medical concerns. We show that escalation is influenced by the amount and distribution of medical content viewed by users, the presence of escalatory terminology in pages visited, and a user’s predisposition to escalate versus to seek more reasonable explanations for ailments. We also demonstrate the persistence of post-session anxiety following escalations and the effect that such anxieties can have on interrupting user’s activities across multiple sessions. Our findings underscore the potential costs and challenges of cyberchondria and suggest actionable design implications that hold opportunity for improving the search and navigation experience for people turning to the Web to interpret common symptoms.
Comments
Anonymous
January 15, 2009
Oh great, now I have to do a Web search for "Cyberchondria" to see if I have it.Anonymous
January 18, 2009
heheheh