Proceedings of the 20th International Conference on World Wide Web, WWW 2011, Hyderabad, India, March 28 - April 1, 2011. ACM 【DBLP Link】
【Paper Link】 【Pages】:1-2
【Authors】: A. P. J. Abdul Kalam
【Abstract】:
【Keywords】: www 2011 keynote talk
【Paper Link】 【Pages】:3-4
【Authors】: Tim Berners-Lee
【Abstract】: How can we best design Web technology to support the features we would like of our society such as: openness, justice, transparency, accountability, participation, innovation, science and democracy?
【Keywords】: www 2011 keynote talk
【Paper Link】 【Pages】:5-6
【Authors】: Christos H. Papadimitriou
【Abstract】: The advent of the Internet brought parallel paradigm shifts to both Economics and Computer Science. Computer scientists realized that large-scale performing systems can emerge from the interaction of selfish agents and that incentives are a quintessential part of a good system design. And economists saw that the default platforms of economic transactions are computational and interconnected. Algorithmic Game Theory is a subdiscipline that emerged from this turmoil, revisiting some of the most important problems in Economics and Game Theory from a computational and network perspective. This talk will survey some of the major themes, results and challenges in this field.
【Keywords】: www 2011 keynote talk
【Paper Link】 【Pages】:7-16
【Authors】: Yelong Shen ; Jun Yan ; Shuicheng Yan ; Lei Ji ; Ning Liu ; Zheng Chen
【Abstract】: Understanding user intent from her sequential search behaviors, i.e. predicting the intent of each user query in a search session, is crucial for modern Web search engines. However, due to the huge number of user behavior variables and coarse level intent labels defined by human editors, it is very difficult to directly model user behavioral dynamics or user intent dynamics in user search sessions. In this paper, we propose a novel Sparse Hidden-Dynamic Conditional Random Fields (SHDCRF) model for user intent learning from their search sessions. Through incorporating the proposed hidden state variables, SHDCRF aims to learn a substructure, i.e. a set of related hidden variables, for each intent label and they are used to model the intermediate dynamics between user intent labels and user behavioral variables. In addition, SHDCRF learns a sparse relation between the hidden variables and intent labels to make the hidden state variables explainable. Extensive experiment results, on real user search sessions from a popular commercial search engine show that the proposed SHDCRF model significantly outperforms in terms of intent prediction results that those classical solutions such as Support Vector Machine (SVM), Conditional Random Field (CRF) and Latnet-Dynamic Conditional Random Field (LDCRF).
【Keywords】: conditional random field; hidden variable; sparse hidden-dynamic; user intent; user search session
【Paper Link】 【Pages】:17-26
【Authors】: Botao Hu ; Yuchen Zhang ; Weizhu Chen ; Gang Wang ; Qiang Yang
【Abstract】: Modeling a user's click-through behavior in click logs is a challenging task due to the well-known position bias problem. Recent advances in click models have adopted the examination hypothesis which distinguishes document relevance from position bias. In this paper, we revisit the examination hypothesis and observe that user clicks cannot be completely explained by relevance and position bias. Specifically, users with different search intents may submit the same query to the search engine but expect different search results. Thus, there might be a bias between user search intent and the query formulated by the user, which can lead to the diversity in user clicks. This bias has not been considered in previous works such as UBM, DBN and CCM. In this paper, we propose a new intent hypothesis as a complement to the examination hypothesis. This hypothesis is used to characterize the bias between the user search intent and the query in each search session. This hypothesis is very general and can be applied to most of the existing click models to improve their capacities in learning unbiased relevance. Experimental results demonstrate that after adopting the intent hypothesis, click models can better interpret user clicks and achieve a significant NDCG improvement.
【Keywords】: click model; intent bias; intent diversity; search engine; user behavior
【Paper Link】 【Pages】:27-36
【Authors】: Lydia B. Chilton ; Jaime Teevan
【Abstract】: Web search engines have historically focused on connecting people with information resources. For example, if a person wanted to know when their flight to Hyderabad was leaving, a search engine might connect them with the airline where they could find flight status information. However, search engines have recently begun to try to meet people's search needs directly, providing, for example, flight status information in response to queries that include an airline and a flight number. In this paper, we use large scale query log analysis to explore the challenges a search engine faces when trying to meet an information need directly in the search result page. We look at how people's interaction behavior changes when inline content is returned, finding that such content can cannibalize clicks from the algorithmic results. We see that in the absence of interaction behavior, an individual's repeat search behavior can be useful in understanding the content's value. We also discuss some of the ways user behavior can be used to provide insight into when inline answers might better trigger and what types of additional information might be included in the results.
【Keywords】: answers; query log analysis; question asking; web search
【Paper Link】 【Pages】:37-46
【Authors】: Xiaofei Zhu ; Jiafeng Guo ; Xueqi Cheng ; Pan Du ; Huawei Shen
【Abstract】: Query recommendation has been considered as an effective way to help search users in their information seeking activities. Traditional approaches mainly focused on recommending alternative queries with close search intent to the original query. However, to only take relevance into account may generate redundant recommendations to users. It is better to provide diverse as well as relevant query recommendations, so that we can cover multiple potential search intents of users and minimize the risk that users will not be satisfied. Besides, previous query recommendation approaches mostly relied on measuring the relevance or similarity between queries in the Euclidean space. However, there is no convincing evidence that the query space is Euclidean. It is more natural and reasonable to assume that the query space is a manifold. In this paper, therefore, we aim to recommend diverse and relevant queries based on the intrinsic query manifold. We propose a unified model, named manifold ranking with stop points, for query recommendation. By turning ranked queries into stop points on the query manifold, our approach can generate query recommendations by simultaneously considering both diversity and relevance in a unified way. Empirical experimental results on a large scale query log of a commercial search engine show that our approach can effectively generate highly diverse as well as closely related query recommendations.
【Keywords】: diversity; manifold ranking with stop points; query recommendation
【Paper Link】 【Pages】:47-56
【Authors】: Idan Szpektor ; Aristides Gionis ; Yoelle Maarek
【Abstract】: The ability to aggregate huge volumes of queries over a large population of users allows search engines to build precise models for a variety of query-assistance features such as query recommendation, correction, etc. Yet, no matter how much data is aggregated, the long-tail distribution implies that a large fraction of queries are rare. As a result, most query assistance services perform poorly or are not even triggered on long-tail queries. We propose a method to extend the reach of query assistance techniques (and in particular query recommendation) to long-tail queries by reasoning about rules between query templates rather than individual query transitions, as currently done in query-flow graph models. As a simple example, if we recognize that 'Montezuma' is a city in the rare query "Montezuma surf" and if the rule 'city surf → beach has been observed, we are able to offer "Montezuma beach" as a recommendation, even if the two queries were never observed in a same session. We conducted experiments to validate our hypothesis, first via traditional small-scale editorial assessments but more interestingly via a novel automated large scale evaluation methodology. Our experiments show that general coverage can be relatively increased by 24% using templates without penalizing quality. Furthermore, for 36% of the 95M queries in our query flow graph, which have no out edges and thus could not be served recommendations, we can now offer at least one recommendation in 98% of the cases.
【Keywords】: query mining; query recommendation; query templates
【Paper Link】 【Pages】:57-66
【Authors】: Yuanhua Lv ; Taesup Moon ; Pranam Kolari ; Zhaohui Zheng ; Xuanhui Wang ; Yi Chang
【Abstract】: With the explosive growth of online news readership, recommending interesting news articles to users has become extremely important. While existing Web services such as Yahoo! and Digg attract users' initial clicks by leveraging various kinds of signals, how to engage such users algorithmically after their initial visit is largely under-explored. In this paper, we study the problem of post-click news recommendation. Given that a user has perused a current news article, our idea is to automatically identify "related" news articles which the user would like to read afterwards. Specifically, we propose to characterize relatedness between news articles across four aspects: relevance, novelty, connection clarity, and transition smoothness. Motivated by this understanding, we define a set of features to capture each of these aspects and put forward a learning approach to model relatedness. In order to quantitatively evaluate our proposed measures and learn a unified relatedness function, we construct a large test collection based on a four-month commercial news corpus with editorial judgments. The experimental results show that the proposed heuristics can indeed capture relatedness, and that the learned unified relatedness function works quite effectively.
【Keywords】: connection clarity; learning; novelty; post-click news recommendation; relatedness; relevance; transition smoothness
【Paper Link】 【Pages】:67-76
【Authors】: Ashok Kumar Ponnuswami ; Kumaresh Pattabiraman ; Desmond Brand ; Tapas Kanungo
【Abstract】: Modern day federated search engines aggregate heterogeneous types of results from multiple vertical search engines and compose a single search engine result page (SERP). The search engine aggregates the results and produces one ranked list, constraining the vertical results to specific slots on the SERP. The usual way to compare two ranking algorithms is to first fix their operating points (internal thresholds), and then run an online experiment that lasts multiple weeks. Online user engagement metrics are then compared to decide which algorithm is better. However, this method does not characterize and compare the behavior over the entire span of operating points. Furthermore, this time-consuming approach is not practical if we have to conduct the experiment over numerous operating points. In this paper we propose a method of characterizing the performance of models that allows us to predict answers to "what if" questions about online user engagement using click-logs over the entire span of feasible operating points. We audition verticals at various slots on the SERP and generate click-logs. This log is then used to create operating curves between variables of interest (for example between result quality and click-through). The operating point for the system then can be chosen to achieve a specific trade-off between the variables. We apply this methodology to predict i) the online performance of two different models, ii) the impact of changing internal quality thresholds on clickthrough, iii) the behavior of introducing a new feature, iv) which machine learning loss function will give better online engagement, v) the impact of sampling distribution of head and tail queries in the training process. The results are reported on a well-known federated search engine. We validate the predictions with online experiments.
【Keywords】: metrics; offline prediction; online evaluation; randomization; user engagement
【Paper Link】 【Pages】:77-86
【Authors】: Jangwon Seo ; Fernando Diaz ; Evgeniy Gabrilovich ; Vanja Josifovski ; Bo Pang
【Abstract】: Proactive link suggestion leads to improved user experience by allowing users to reach relevant information with fewer clicks, fewer pages to read, or simply faster because the right pages are prefetched just in time. In this paper we tackle two new scenarios for link suggestion, which were not covered in prior work owing to scarcity of historical browsing data. In the web search scenario, we propose a method for generating quick links - additional entry points into Web sites, which are shown for top search results for navigational queries - for tail sites, for which little browsing statistics is available. Beyond Web search, we also propose a method for link suggestion in general web browsing, effectively anticipating the next link to be followed by the user. Our approach performs clustering of Web sites in order to aggregate information across multiple sites, and enables relevant link suggestion for virtually any site, including tail sites and brand new sites for which little historical data is available. Empirical evaluation confirms the validity of our method using editorially labeled data as well as real-life search and browsing data from a major US search engine.
【Keywords】: assisted browsing; link suggestion; quick links; tail sites; website clustering
【Paper Link】 【Pages】:87-96
【Authors】: Wei Hu ; Jianfeng Chen ; Yuzhong Qu
【Abstract】: An object on the Semantic Web is likely to be denoted with multiple URIs by different parties. Object coreference resolution is to identify "equivalent" URIs that denote the same object. Driven by the Linking Open Data (LOD) initiative, millions of URIs have been explicitly linked with owl:sameAs statements, but potentially coreferent ones are still considerable. Existing approaches address the problem mainly from two directions: one is based upon equivalence inference mandated by OWL semantics, which finds semantically coreferent URIs but probably omits many potential ones; the other is via similarity computation between property-value pairs, which is not always accurate enough. In this paper, we propose a self-training approach for object coreference resolution on the Semantic Web, which leverages the two classes of approaches to bridge the gap between semantically coreferent URIs and potential candidates. For an object URI, we firstly establish a kernel that consists of semantically coreferent URIs based on owl:sameAs, (inverse) functional properties and (max-)cardinalities, and then extend such kernel iteratively in terms of discriminative property-value pairs in the descriptions of URIs. In particular, the discriminability is learnt with a statistical measurement, which not only exploits key characteristics for representing an object, but also takes into account the matchability between properties from pragmatics. In addition, frequent property combinations are mined to improve the accuracy of the resolution. We implement a scalable system and demonstrate that our approach achieves good precision and recall for resolving object coreference, on both benchmark and large-scale datasets.
【Keywords】: data fusion; object consolidation; object coreference; property combination; self-training
【Paper Link】 【Pages】:97-106
【Authors】: Matthias Hagen ; Martin Potthast ; Benno Stein ; Christof Bräutigam
【Abstract】: We address the problem of query segmentation: given a keyword query, the task is to group the keywords into phrases, if possible. Previous approaches to the problem achieve reasonable segmentation performance but are tested only against a small corpus of manually segmented queries. In addition, many of the previous approaches are fairly intricate as they use expensive features and are difficult to be reimplemented. The main contribution of this paper is a new method for query segmentation that is easy to implement, fast, and that comes with a segmentation accuracy comparable to current state-of-the-art techniques. Our method uses only raw web n-gram frequencies and Wikipedia titles that are stored in a hash table. At the same time, we introduce a new evaluation corpus for query segmentation. With about 50,000 human-annotated queries, it is two orders of magnitude larger than the corpus being used up to now.
【Keywords】: corpus; query segmentation; web n-grams
【Paper Link】 【Pages】:107-116
【Authors】: Ziv Bar-Yossef ; Naama Kraus
【Abstract】: Query auto completion is known to provide poor predictions of the user's query when her input prefix is very short (e.g., one or two characters). In this paper we show that context, such as the user's recent queries, can be used to improve the prediction quality considerably even for such short prefixes. We propose a context-sensitive query auto completion algorithm, NearestCompletion, which outputs the completions of the user's input that are most similar to the context queries. To measure similarity, we represent queries and contexts as high-dimensional term-weighted vectors and resort to cosine similarity. The mapping from queries to vectors is done through a new query expansion technique that we introduce, which expands a query by traversing the query recommendation tree rooted at the query. In order to evaluate our approach, we performed extensive experimentation over the public AOL query log. We demonstrate that when the recent user's queries are relevant to the current query she is typing, then after typing a single character, NearestCompletion's MRR is 48% higher relative to the MRR of the standard MostPopularCompletion algorithm on average. When the context is irrelevant, however, NearestCompletion's MRR is essentially zero. To mitigate this problem, we propose HybridCompletion, which is a hybrid of NearestCompletion with MostPopularCompletion. HybridCompletion is shown to dominate both NearestCompletion and MostPopularCompletion, achieving a total improvement of 31.5% in MRR relative to MostPopularCompletion on average.
【Keywords】: context-awareness; query auto-completion; query expansion
【Paper Link】 【Pages】:117-126
【Authors】: Huizhong Duan ; Bo-June Paul Hsu
【Abstract】: In this paper, we study the problem of online spelling correction for query completions. Misspelling is a common phenomenon among search engines queries. In order to help users effectively express their information needs, mechanisms for automatically correcting misspelled queries are required. Online spelling correction aims to provide spell corrected completion suggestions as a query is incrementally entered. As latency is crucial to the utility of the suggestions, such an algorithm needs to be not only accurate, but also efficient. To tackle this problem, we propose and study a generative model for input queries, based on a noisy channel transformation of the intended queries. Utilizing spelling correction pairs, we train a Markov n-gram transformation model that captures user spelling behavior in an unsupervised fashion. To find the top spell-corrected completion suggestions in real-time, we adapt the A* search algorithm with various pruning heuristics to dynamically expand the search space efficiently. Evaluation of the proposed methods demonstrates a substantial increase in the effectiveness of online spelling correction over existing techniques.
【Keywords】: a* search; query completion; spelling correction; transformation model
【Paper Link】 【Pages】:127-136
【Authors】: Paul Dütting ; Monika Henzinger ; Ingmar Weber
【Abstract】: Auctions are widely used on the Web. Applications range from internet advertising to platforms such as eBay. In most of these applications the auctions in use are single/multi-item auctions with unit demand. The main drawback of standard mechanisms for this type of auctions, such as VCG and GSP, is the limited expressiveness that they offer to the bidders. The General Auction Mechanism (GAM) of [1] is taking a first step towards addressing the problem of limited expressiveness by computing a bidder optimal, envy free outcome for linear utility functions with identical slopes and a single discontinuity per bidder-item pair. We show that in many practical situations this does not suffice to adequately model the preferences of the bidders, and we overcome this problem by presenting the first mechanism for piece-wise linear utility functions with non-identical slopes and multiple discontinuities. Our mechanism runs in polynomial time. Like GAM it is incentive compatible for inputs that fulfill a certain non-degeneracy requirement, but our requirement is more general than the requirement of GAM. For discontinuous utility functions that are non-degenerate as well as for continuous utility functions the outcome of our mechanism is a competitive equilibrium. We also show how our mechanism can be used to compute approximately bidder optimal, envy free outcomes for a general class of continuous utility functions via piece-wise linear approximation. Finally, we prove hardness results for even more expressive settings.
【Keywords】: bidder optimality; competitive equilibrium; envy freeness; expressiveness; general auction mechanism; gsp; vcg
【Paper Link】 【Pages】:137-146
【Authors】: Arpita Ghosh ; R. Preston McAfee
【Abstract】: We model the economics of incentivizing high-quality user generated content (UGC), motivated by settings such as online review forums, question-answer sites, and comments on news articles and blogs. We provide a game-theoretic model within which to study the problem of incentivizing high quality UGC, in which contributors are strategic and motivated by exposure. Our model has the feature that both the quality of contributions as well as the extent of participation is determined endogenously in a free-entry Nash equilibrium. The model predicts, as observed in practice, that if exposure is independent of quality, there will be a flood of low quality contributions in equilibrium. An ideal mechanism in this context would elicit both high quality and high participation in equilibrium, with near-optimal quality as the available attention diverges, and should be easily implementable in practice. We consider a very simple elimination mechanism, which subjects each contribution to rating by some number A of viewers, and eliminates any contributions that are not uniformly rated positively. We construct and analyze free-entry Nash equilibria for this mechanism, and show that A can be chosen to achieve quality that tends to optimal, along with diverging participation, as the number of viewers diverges.
【Keywords】: attention economics; game theory; quality of online content; user generated content (ugc)
【Paper Link】 【Pages】:147-156
【Authors】: L. Elisa Celis ; Gregory Lewis ; Markus M. Mobius ; Hamid Nazerzadeh
【Abstract】: We present a simple auction mechanism which extends the second-price auction with reserve and is truthful in expectation. This mechanism is particularly effective in private value environments where the distribution of valuations are irregular. Bidders can "buy-it-now", or alternatively "take-a-chance" where the top d bidders are equally likely to win. The randomized take-a-chance allocation incentivizes high valuation bidders to buy-it-now. We show that for a large class of valuations, this mechanism achieves similar allocations and revenues as Myerson's optimal mechanism, and outperforms the second-price auction with reserve. In addition, we present an evaluation of bid data from Microsoft's AdECN platform. We find the valuations are irregular, and counterfactual experiments suggest our BIN-TAC mechanism would improve revenue by 11% relative to an optimal second-price mechanism with reserve.
【Keywords】: ad auctions; adecn; mechanism design; online advertising; sequential screening
【Paper Link】 【Pages】:157-166
【Authors】: Randall A. Lewis ; Justin M. Rao ; David H. Reiley
【Abstract】: Measuring the causal effects of online advertising (adfx) on user behavior is important to the health of the WWW publishing industry. In this paper, using three controlled experiments, we show that observational data frequently lead to incorrect estimates of adfx. The reason, which we label "activity bias," comes from the surprising amount of time-based correlation between the myriad activities that users undertake online. In Experiment 1, users who are exposed to an ad on a given day are much more likely to engage in brand-relevant search queries as compared to their recent history for reasons that had nothing do with the advertisement. In Experiment 2, we show that activity bias occurs for page views across diverse websites. In Experiment 3, we track account sign-ups at a competitor's (of the advertiser) website and find that many more people sign-up on the day they saw an advertisement than on other days, but that the true "competitive effect" was minimal. In all three experiments, exposure to a campaign signals doing "more of everything" in given period of time, making it difficult to find a suitable "matched control" using prior behavior. In such cases, the "match" is fundamentally different from the exposed group, and we show how and why observational methods lead to a massive overestimate of adfx in such circumstances.
【Keywords】: advertising effectiveness; browsing behavior; causal inference; field experiments; selection bias
【Paper Link】 【Pages】:167-176
【Authors】: Michael Grabchak ; Narayan L. Bhamidipati ; Rushi Bhatt ; Dinesh Garg
【Abstract】: Stochastic knapsack problems deal with selecting items with potentially random sizes and rewards so as to maximize the total reward while satisfying certain capacity constraints. A novel variant of this problem, where items are worthless unless collected in bundles, is introduced here. This setup is similar to the Groupon model, where a deal is off unless a minimum number of users sign up for it. Since the optimal algorithm to solve this problem is not practical, several adaptive greedy approaches with reasonable time and memory requirements are studied in detail - theoretically, as well as, experimentally. Worst case performance guarantees are provided for some of these greedy algorithms, while results of experimental evaluation demonstrate that they are much closer to optimal than what the theoretical bounds suggest. Applications include optimizing for online advertising pricing models where advertisers pay only when certain goals, in terms of clicks or conversions, are met. We perform extensive experiments for the situation where there are between two and five ads. For typical ad conversion rates, the greedy policy of selecting items having the highest individual expected reward obtains a value within 5% of optimal over 95% of the time for a wide selection of parameters.
【Keywords】: ad selection; chunked rewards; groupon; revenue maximization
【Paper Link】 【Pages】:177-186
【Authors】: Danilo Ardagna ; Barbara Panicucci ; Mauro Passacantando
【Abstract】: Cloud computing is an emerging paradigm which allows the on-demand delivering of software, hardware, and data as services. As cloud-based services are more numerous and dynamic, the development of efficient service provisioning policies become increasingly challenging. Game theoretic approaches have shown to gain a thorough analytical understanding of the service provisioning problem. In this paper we take the perspective of Software as a Service (SaaS) providers which host their applications at an Infrastructure as a Service (IaaS) provider. Each SaaS needs to comply with quality of service requirements, specified in Service Level Agreement (SLA) contracts with the end-users, which determine the revenues and penalties on the basis of the achieved performance level. SaaS providers want to maximize their revenues from SLAs, while minimizing the cost of use of resources supplied by the IaaS provider. Moreover, SaaS providers compete and bid for the use of infrastructural resources. On the other hand, the IaaS wants to maximize the revenues obtained providing virtualized resources. In this paper we model the service provisioning problem as a Generalized Nash game, and we propose an efficient algorithm for the run time management and allocation of IaaS resources to competing SaaSs.
【Keywords】: game theory; generalized nash equilibrium; resource allocation
【Paper Link】 【Pages】:187-196
【Authors】: Junjie Zhang ; Christian Seifert ; Jack W. Stokes ; Wenke Lee
【Abstract】: A drive-by download attack occurs when a user visits a webpage which attempts to automatically download malware without the user's consent. Attackers sometimes use a malware distribution network (MDN) to manage a large number of malicious webpages, exploits, and malware executables. In this paper, we provide a new method to determine these MDNs from the secondary URLs and redirect chains recorded by a high-interaction client honeypot. In addition, we propose a novel drive-by download detection method. Instead of depending on the malicious content used by previous methods, our algorithm first identifies and then leverages the URLs of the MDN's central servers, where a central server is a common server shared by a large percentage of the drive-by download attacks in the same MDN. A set of regular expression-based signatures are then generated based on the URLs of each central server. This method allows additional malicious webpages to be identified which launched but failed to execute a successful drive-by download attack. The new drive-by detection system named ARROW has been implemented, and we provide a large-scale evaluation on the output of a production drive-by detection system. The experimental results demonstrate the effectiveness of our method, where the detection coverage has been boosted by 96% with an extremely low false positive rate.
【Keywords】: detection; drive-by download; malware distribution network; signature generation
【Paper Link】 【Pages】:197-206
【Authors】: Davide Canali ; Marco Cova ; Giovanni Vigna ; Christopher Kruegel
【Abstract】: Malicious web pages that host drive-by-download exploits have become a popular means for compromising hosts on the Internet and, subsequently, for creating large-scale botnets. In a drive-by-download exploit, an attacker embeds a malicious script (typically written in JavaScript) into a web page. When a victim visits this page, the script is executed and attempts to compromise the browser or one of its plugins. To detect drive-by-download exploits, researchers have developed a number of systems that analyze web pages for the presence of malicious code. Most of these systems use dynamic analysis. That is, they run the scripts associated with a web page either directly in a real browser (running in a virtualized environment) or in an emulated browser, and they monitor the scripts' executions for malicious activity. While the tools are quite precise, the analysis process is costly, often requiring in the order of tens of seconds for a single page. Therefore, performing this analysis on a large set of web pages containing hundreds of millions of samples can be prohibitive. One approach to reduce the resources required for performing large-scale analysis of malicious web pages is to develop a fast and reliable filter that can quickly discard pages that are benign, forwarding to the costly analysis tools only the pages that are likely to contain malicious code. In this paper, we describe the design and implementation of such a filter. Our filter, called Prophiler, uses static analysis techniques to quickly examine a web page for malicious content. This analysis takes into account features derived from the HTML contents of a page, from the associated JavaScript code, and from the corresponding URL. We automatically derive detection models that use these features using machine-learning techniques applied to labeled datasets. To demonstrate the effectiveness and efficiency of Prophiler, we crawled and collected millions of pages, which we analyzed for malicious behavior. Our results show that our filter is able to reduce the load on a more costly dynamic analysis tools by more than 85%, with a negligible amount of missed malicious pages.
【Keywords】: drive-by download exploits; efficient web page filtering; malicious web page analysis
【Paper Link】 【Pages】:207-216
【Authors】: John P. John ; Fang Yu ; Yinglian Xie ; Arvind Krishnamurthy ; Martín Abadi
【Abstract】: Many malicious activities on the Web today make use of compromised Web servers, because these servers often have high pageranks and provide free resources. Attackers are therefore constantly searching for vulnerable servers. In this work, we aim to understand how attackers find, compromise, and misuse vulnerable servers. Specifically, we present heat-seeking honeypots that actively attract attackers, dynamically generate and deploy honeypot pages, then analyze logs to identify attack patterns. Over a period of three months, our deployed honeypots, despite their obscure location on a university network, attracted more than 44,000 attacker visits from close to 6,000 distinct IP addresses. By analyzing these visits, we characterize attacker behavior and develop simple techniques to identify attack traffic. Applying these techniques to more than 100 regular Web servers as an example, we identified malicious queries in almost all of their logs.
【Keywords】: honeypots; web security
【Paper Link】 【Pages】:217-226
【Authors】: Xiaoxin Yin ; Wenzhao Tan
【Abstract】: Accessing online information from various data sources has become a necessary part of our everyday life. Unfortunately such information is not always trustworthy, as different sources are of very different qualities and often provide inaccurate and conflicting information. Existing approaches attack this problem using unsupervised learning methods, and try to infer the confidence of the data value and trustworthiness of each source from each other by assuming values provided by more sources are more accurate. However, because false values can be widespread through copying among different sources and out-of-date data often overwhelm up-to-date data, such bootstrapping methods are often ineffective. In this paper we propose a semi-supervised approach that finds true values with the help of ground truth data. Such ground truth data, even in very small amount, can greatly help us identify trustworthy data sources. Unlike existing studies that only provide iterative algorithms, we derive the optimal solution to our problem and provide an iterative algorithm that converges to it. Experiments show our method achieves higher accuracy than existing approaches, and it can be applied on very huge data sets when implemented with MapReduce.
【Keywords】: data quality; semi-supervised; truth discovery
【Paper Link】 【Pages】:227-236
【Authors】: Raju Balakrishnan ; Subbarao Kambhampati
【Abstract】: One immediate challenge in searching the deep web databases is source selection - i.e. selecting the most relevant web databases for answering a given query. The existing database selection methods (both text and relational) assess the source quality based on the query-similarity-based relevance assessment. When applied to the deep web these methods have two deficiencies. First is that the methods are agnostic to the correctness (trustworthiness) of the sources. Secondly, the query based relevance does not consider the importance of the results. These two considerations are essential for the open collections like the deep web. Since a number of sources provide answers to any query, we conjuncture that the agreements between these answers are likely to be helpful in assessing the importance and the trustworthiness of the sources. We compute the agreement between the sources as the agreement of the answers returned. While computing the agreement, we also measure and compensate for possible collusion between the sources. This adjusted agreement is modeled as a graph with sources at the vertices. On this agreement graph, a quality score of a source that we call SourceRank, is calculated as the stationary visit probability of a random walk. We evaluate SourceRank in multiple domains, including sources in Google Base, with sizes up to 675 sources. We demonstrate that the SourceRank tracks source corruption. Further, our relevance evaluations show that SourceRank improves precision by 22-60% over the Google Base and the other baseline methods. SourceRank has been implemented in a system called Factal.
【Keywords】: deep web; source selection; sourcerank; web integration
【Paper Link】 【Pages】:237-246
【Authors】: Michael J. Welch ; Junghoo Cho ; Christopher Olston
【Abstract】: Ambiguous queries constitute a significant fraction of search instances and pose real challenges to web search engines. With current approaches the top results for these queries tend to be homogeneous, making it difficult for users interested in less popular aspects to find relevant documents. While existing research in search diversification offers several solutions for introducing variety into the results, the majority of such work is predicated, implicitly or otherwise, on the assumption that a single relevant document will fulfill a user's information need, making them inadequate for many informational queries. In this paper we present a search-diversification algorithm particularly suitable for informational queries by explicitly modeling that the user may need more than one page to satisfy their need. This modeling enables our algorithm to make a well-informed tradeoff between a user's desire for multiple relevant documents, probabilistic information about an average user's interest in the subtopics of a multifaceted query, and uncertainty in classifying documents into those subtopics. We evaluate the effectiveness of our algorithm against commercial search engine results and other modern ranking strategies, demonstrating notable improvement in multiple document scenarios.
【Keywords】: expected hits; informational queries; search diversity
【Paper Link】 【Pages】:247-256
【Authors】: Zhijun Yin ; Liangliang Cao ; Jiawei Han ; Chengxiang Zhai ; Thomas S. Huang
【Abstract】: This paper studies the problem of discovering and comparing geographical topics from GPS-associated documents. GPS-associated documents become popular with the pervasiveness of location-acquisition technologies. For example, in Flickr, the geo-tagged photos are associated with tags and GPS locations. In Twitter, the locations of the tweets can be identified by the GPS locations from smart phones. Many interesting concepts, including cultures, scenes, and product sales, correspond to specialized geographical distributions. In this paper, we are interested in two questions: (1) how to discover different topics of interests that are coherent in geographical regions? (2) how to compare several topics across different geographical locations? To answer these questions, this paper proposes and compares three ways of modeling geographical topics: location-driven model, text-driven model, and a novel joint model called LGTA (Latent Geographical Topic Analysis) that combines location and text. To make a fair comparison, we collect several representative datasets from Flickr website including Landscape, Activity, Manhattan, National park, Festival, Car, and Food. The results show that the first two methods work in some datasets but fail in others. LGTA works well in all these datasets at not only finding regions of interests but also providing effective comparisons of the topics across different locations. The results confirm our hypothesis that the geographical distributions can help modeling topics, while topics provide important cues to group different geographical regions.
【Keywords】: geographical topics; topic comparison; topic modeling
【Paper Link】 【Pages】:257-266
【Authors】: Yookyung Jo ; John E. Hopcroft ; Carl Lagoze
【Abstract】: In this paper we study how to discover the evolution of topics over time in a time-stamped document collection. Our approach is uniquely designed to capture the rich topology of topic evolution inherent in the corpus. Instead of characterizing the evolving topics at fixed time points, we conceptually define a topic as a quantized unit of evolutionary change in content and discover topics with the time of their appearance in the corpus. Discovered topics are then connected to form a topic evolution graph using a measure derived from the underlying document network. Our approach allows inhomogeneous distribution of topics over time and does not impose any topological restriction in topic evolution graphs. We evaluate our algorithm on the ACM corpus. The topic evolution graphs obtained from the ACM corpus provide an effective and concrete summary of the corpus with remarkably rich topology that are congruent to our background knowledge. In a finer resolution, the graphs reveal concrete information about the corpus that were previously unknown to us, suggesting the utility of our approach as a navigational tool for the corpus.
【Keywords】: citation network; language model; topic evolution; topology
【Paper Link】 【Pages】:267-276
【Authors】: Amr Ahmed ; Qirong Ho ; Jacob Eisenstein ; Eric P. Xing ; Alexander J. Smola ; Choon Hui Teo
【Abstract】: News clustering, categorization and analysis are key components of any news portal. They require algorithms capable of dealing with dynamic data to cluster, interpret and to temporally aggregate news articles. These three tasks are often solved separately. In this paper we present a unified framework to group incoming news articles into temporary but tightly-focused storylines, to identify prevalent topics and key entities within these stories, and to reveal the temporal structure of stories as they evolve. We achieve this by building a hybrid clustering and topic model. To deal with the available wealth of data we build an efficient parallel inference algorithm by sequential Monte Carlo estimation. Time and memory costs are nearly constant in the length of the history, and the approach scales to hundreds of thousands of documents. We demonstrate the efficiency and accuracy on the publicly available TDT dataset and data of a major internet news site.
【Keywords】: dirichlet processes; online inference; topic models
【Paper Link】 【Pages】:277-286
【Authors】: Vidit Jain ; Manik Varma
【Abstract】: Our objective is to improve the performance of keyword based image search engines by re-ranking their original results. To this end, we address three limitations of existing search engines in this paper. First, there is no straight-forward, fully automated way of going from textual queries to visual features. Image search engines therefore primarily rely on static and textual features for ranking. Visual features are mainly used for secondary tasks such as finding similar images. Second, image rankers are trained on query-image pairs labeled with relevance judgments determined by human experts. Such labels are well known to be noisy due to various factors including ambiguous queries, unknown user intent and subjectivity in human judgments. This leads to learning a sub-optimal ranker. Finally, a static ranker is typically built to handle disparate user queries. The ranker is therefore unable to adapt its parameters to suit the query at hand which again leads to sub-optimal results. We demonstrate that all of these problems can be mitigated by employing a re-ranking algorithm that leverages aggregate user click data. We hypothesize that images clicked in response to a query are mostly relevant to the query. We therefore re-rank the original search results so as to promote images that are likely to be clicked to the top of the ranked list. Our re-ranking algorithm employs Gaussian Process regression to predict the normalized click count for each image, and combines it with the original ranking score. Our approach is shown to significantly boost the performance of the Bing image search engine on a wide range of tail queries.
【Keywords】: click data; image re-ranking; image search
【Paper Link】 【Pages】:287-296
【Authors】: Liangda Li ; Ke Zhou ; Gui-Rong Xue ; Hongyuan Zha ; Yong Yu
【Abstract】: It is well-known that textual information such as video transcripts and video reviews can significantly enhance the performance of video summarization algorithms. Unfortunately, many videos on the Web such as those from the popular video sharing site YouTube do not have useful textual information. The goal of this paper is to propose a transfer learning framework for video summarization: in the training process both the video features and textual features are exploited to train a summarization algorithm while for summarizing a new video only its video features are utilized. The basic idea is to explore the transferability between videos and their corresponding textual information. Based on the assumption that video features and textual features are highly correlated with each other, we can transfer textual information into knowledge on summarization using video information only. In particular, we formulate the video summarization problem as that of learning a mapping from a set of shots of a video to a subset of the shots using the general framework of SVM-based structured learning. Textual information is transferred by encoding them into a set of constraints used in the structured learning process which tend to provide a more detailed and accurate characterization of the different subsets of shots. Experimental results show significant performance improvement of our approach and demonstrate the utility of textual information for enhancing video summarization.
【Keywords】: structural svm; transfer learning; video summarization
【Paper Link】 【Pages】:297-306
【Authors】: Guojun Qi ; Charu C. Aggarwal ; Thomas S. Huang
【Abstract】: In this paper, we study the problem of transfer learning from text to images in the context of network data in which link based bridges are available to transfer the knowledge between the different domains. The problem of classification of image data is often much more challenging than text data because of the following two reasons: (a) Labeled text data is very widely available for classification purposes. On the other hand, this is often not the case for image data, in which a lot of images are available from many sources, but many of them are often not labeled. (b) The image features are not directly related to semantic concepts inherent in class labels. On the other hand, since text data tends to have natural semantic interpretability (because of their human origins), they are often more directly related to class labels. Therefore, the relationships between the images and text features also provide additional hints for the classification process in terms of the image feature transformations which provide the most effective results. The semantic challenges of image features are glaringly evident, when we attempt to recognize complex abstract concepts, and the visual features often fail to discriminate such concepts. However, the copious availability of bridging relationships between text and images in the context of web and social network data can be used in order to design for effective classifiers for image data. One of our goals in this paper is to develop a mathematical model for the functional relationships between text and image features, so as indirectly transfer semantic knowledge through feature transformations. This feature transformation is accomplished by mapping instances from different domains into a common space of unspecific topics. This is used as a bridge to semantically connect the two heterogeneous spaces. This is also helpful for the cases where little image data is available for the classification process. We evaluate our knowledge transfer techniques on an image classification task with labeled text corpora and show the effectiveness with respect to competing algorithms.
【Keywords】: cross-domain label propagation; heterogeneous knowledge propagation; text corpus and web images; translator function
【Paper Link】 【Pages】:307-316
【Authors】: Ghassan Karame ; Aurélien Francillon ; Srdjan Capkun
【Abstract】: Currently, several online businesses deem that advertising revenues alone are not sufficient to generate profits and are therefore set to charge for online content. In this paper, we explore a complement to the current advertisement model; more specifically, we propose a micropayment model for non-specialized commodity web-services based on microcomputations. In our model, a user that wishes to access online content offered by a website does not need to register or pay to access the website; instead, he will accept to run microcomputations on behalf of the website in exchange for access to the content. These microcomputations can, for example, support ongoing computing projects that have clear social benefits (e.g., projects relating to HIV, dengue, cancer, etc.) or can contribute towards commercial computing projects. We argue that this micropayment model is economically and technically viable and that it can be integrated in existing distributed computing frameworks (e.g., the BOINC platform). We implement a preliminary prototype of a system based on our model through which we evaluate its performance and usability. Finally, we analyze the security and privacy of our proposal and we show that it ensures payment for the content while preserving the privacy of users.
【Keywords】: distributed computing; microcomputations; micropayments; monetization; privacy
【Paper Link】 【Pages】:317-326
【Authors】: Sayan Bhattacharya ; Sreenivas Gollapudi ; Kamesh Munagala
【Abstract】: In commerce search, the set of products returned by a search engine often forms the basis for all user interactions leading up to a potential transaction on the web. Such a set of products is known as the consideration set. In this study, we consider the problem of generating consideration set of products in commerce search so as to maximize user satisfaction. One of the key features of commerce search that we exploit in our study is the association of a set of important attributes with the products and a set of specified attributes with the user queries. Those important attributes not used in the query are treated as unspecified. The attribute space admits a natural definition of user satisfaction via user preferences on the attributes and their values, viz. require that the surfaced products be close to the specified attribute values in the query, and diverse with respect to the unspecified attributes. We model this as a general Max-Sum Dispersion problem wherein we are given a set of n nodes in a metric space and the objective is to select a subset of nodes with total cost at most a given budget, and maximize the sum of the pairwise distances between the selected nodes. In our setting, each node denotes a product, the cost of a node being inversely proportional to its relevance with respect to specified attributes. The distance between two nodes quantifies the diversity with respect to the unspecified attributes. The problem is NP-hard and a 2-approximation was previously known only when all the nodes have unit cost. In our setting, we do not make any assumptions on the cost. We label this problem as the General Max-Sum Dispersion problem. We give the first constant factor approximation algorithm for this problem, achieving an approximation ratio of 2. Further, we perform extensive empirical analysis on real-world data to show the effectiveness of our algorithm.
【Keywords】: approximation algorithms; facility dispersion; novelty; relevance
【Paper Link】 【Pages】:327-336
【Authors】: Beibei Li ; Anindya Ghose ; Panagiotis G. Ipeirotis
【Abstract】: With the growing pervasiveness of the Internet, online search for products and services is constantly increasing. Most product search engines are based on adaptations of theoretical models devised for information retrieval. However, the decision mechanism that underlies the process of buying a product is different than the process of locating relevant documents or objects. We propose a theory model for product search based on expected utility theory from economics. Specifically, we propose a ranking technique in which we rank highest the products that generate the highest surplus, after the purchase. In a sense, the top ranked products are the "best value for money" for a specific user. Our approach builds on research on "demand estimation" from economics and presents a solid theoretical foundation on which further research can build on. We build algorithms that take into account consumer demographics, heterogeneity of consumer preferences, and also account for the varying price of the products. We show how to achieve this without knowing the demographics or purchasing histories of individual consumers but by using aggregate demand data. We evaluate our work, by applying the techniques on hotel search. Our extensive user studies, using more than 15,000 user-provided ranking comparisons, demonstrate an overwhelming preference for the rankings generated by our techniques, compared to a large number of existing strong state-of-the-art baselines.
【Keywords】: consumer surplus; economics; product search; ranking; text mining; user-generated content; utility theory
【Paper Link】 【Pages】:337-346
【Authors】: Kira Radinsky ; Eugene Agichtein ; Evgeniy Gabrilovich ; Shaul Markovitch
【Abstract】: Computing the degree of semantic relatedness of words is a key functionality of many language applications such as search, clustering, and disambiguation. Previous approaches to computing semantic relatedness mostly used static language resources, while essentially ignoring their temporal aspects. We believe that a considerable amount of relatedness information can also be found in studying patterns of word usage over time. Consider, for instance, a newspaper archive spanning many years. Two words such as "war" and "peace" might rarely co-occur in the same articles, yet their patterns of use over time might be similar. In this paper, we propose a new semantic relatedness model, Temporal Semantic Analysis (TSA), which captures this temporal information. The previous state of the art method, Explicit Semantic Analysis (ESA), represented word semantics as a vector of concepts. TSA uses a more refined representation, where each concept is no longer scalar, but is instead represented as time series over a corpus of temporally-ordered documents. To the best of our knowledge, this is the first attempt to incorporate temporal evidence into models of semantic relatedness. Empirical evaluation shows that TSA provides consistent improvements over the state of the art ESA results on multiple benchmarks.
【Keywords】: semantic analysis; semantic similarity; temporal dynamics; temporal semantics; word relatedness
【Paper Link】 【Pages】:347-356
【Authors】: Yue Lu ; Malú Castellanos ; Umeshwar Dayal ; ChengXiang Zhai
【Abstract】: The explosion of Web opinion data has made essential the need for automatic tools to analyze and understand people's sentiments toward different topics. In most sentiment analysis applications, the sentiment lexicon plays a central role. However, it is well known that there is no universally optimal sentiment lexicon since the polarity of words is sensitive to the topic domain. Even worse, in the same domain the same word may indicate different polarities with respect to different aspects. For example, in a laptop review, "large" is negative for the battery aspect while being positive for the screen aspect. In this paper, we focus on the problem of learning a sentiment lexicon that is not only domain specific but also dependent on the aspect in context given an unlabeled opinionated text collection. We propose a novel optimization framework that provides a unified and principled way to combine different sources of information for learning such a context-dependent sentiment lexicon. Experiments on two data sets (hotel reviews and customer feedback surveys on printers) show that our approach can not only identify new sentiment words specific to the given domain but also determine the different polarities of a word depending on the aspect in context. In further quantitative evaluation, our method is proved to be effective in constructing a high quality lexicon by comparing with a human annotated gold standard. In addition, using the learned context-dependent sentiment lexicon improved the accuracy in an aspect-level sentiment classification task.
【Keywords】: opinion mining; optimization; sentiment analysis; sentiment lexicon
【Paper Link】 【Pages】:357-366
【Authors】: Kuansan Wang ; Christopher Thrasher ; Bo-June Paul Hsu
【Abstract】: This paper uses the URL word breaking task as an example to elaborate what we identify as crucial in designing statistical natural language processing (NLP) algorithms for Web scale applications: (1) rudimentary multilingual capabilities to cope with the global nature of the Web, (2) multi-style modeling to handle diverse language styles seen in the Web contents, (3) fast adaptation to keep pace with the dynamic changes of the Web, (4) minimal heuristic assumptions for generalizability and robustness, and (5) possibilities of efficient implementations and minimal manual efforts for processing massive amount of data at a reasonable cost. We first show that the state-of-the-art word breaking techniques can be unified and generalized under the Bayesian minimum risk (BMR) framework that, using a Web scale N-gram, can meet the first three requirements. We discuss how the existing techniques can be viewed as introducing additional assumptions to the basic BMR framework, and describe a generic yet efficient implementation called word synchronous beam search. Testing the framework and its implementation on a series of large scale experiments reveals the following. First, the language style used to build the model plays a critical role in the word breaking task, and the most suitable for the URL word breaking task appears to be that of the document title where the best performance is obtained. Models created from other language styles, such as from document body, anchor text, and even queries, exhibit varying degrees of mismatch. Although all styles benefit from increasing modeling power which, in our experiments, corresponds to the use of a higher order N-gram, the gain is most recognizable for the title model. The heuristics proposed by the prior arts do contribute to the word breaking performance for mismatched or less powerful models, but are less effective and, in many cases, lead to poorer performance than the matched model with minimal assumptions. For the matched model based on document titles, an accuracy rate of 97.18% can already be achieved using simple trigram without any heuristics.
【Keywords】: compound splitting; multi-style language model; url segmentation; web scale word breaking; word segmentation
【Paper Link】 【Pages】:367-376
【Authors】: Krysta Marie Svore ; Maksims Volkovs ; Christopher J. C. Burges
【Abstract】: We investigate the problem of learning to rank with document retrieval from the perspective of learning for multiple objective functions. We present solutions to two open problems in learning to rank: first, we show how multiple measures can be combined into a single graded measure that can be learned. This solves the problem of learning from a 'scorecard' of measures by making such scorecards comparable, and we show results where a standard web relevance measure (NDCG) is used for the top-tier measure, and a relevance measure derived from click data is used for the second-tier measure; the second-tier measure is shown to significantly improve while leaving the top-tier measure largely unchanged. Second, we note that the learning-to-rank problem can itself be viewed as changing as the ranking model learns: for example, early in learning, adjusting the rank of all documents can be advantageous, but later during training, it becomes more desirable to concentrate on correcting the top few documents for each query. We show how an analysis of these problems leads to an improved, iteration-dependent cost function that interpolates between a cost function that is more appropriate for early learning, with one that is more appropriate for late-stage learning. The approach results in a significant improvement in accuracy with the same size models. We investigate these ideas using LambdaMART, a state-of-the-art ranking algorithm.
【Keywords】: learning to rank; relevance measures; web search
【Paper Link】 【Pages】:377-386
【Authors】: Maryam Karimzadehgan ; Wei Li ; Ruofei Zhang ; Jianchang Mao
【Abstract】: This paper is concerned with the problem of learning a model to rank objects (Web pages, ads and etc.). We propose a framework where the ranking model is both optimized and evaluated using the same information retrieval measures such as Normalized Discounted Cumulative Gain (NDCG) and Mean Average Precision (MAP). The main difficulty in direct optimization of NDCG and MAP is that these measures depend on the rank of objects and are not differentiable. Most learning-to-rank methods that attempt to optimize NDCG or MAP approximate such measures so that they can be differentiable. In this paper, we propose a simple yet effective stochastic optimization algorithm to directly minimize any loss function, which can be defined on NDCG or MAP for the learning-to-rank problem. The algorithm employs Simulated Annealing along with Simplex method for its parameter search and finds the global optimal parameters. Experiment results using NDCG-Annealing algorithm, an instance of the proposed algorithm, on LETOR benchmark data sets show that the proposed algorithm is both effective and stable when compared to the baselines provided in LETOR 3.0. In addition, we applied the algorithm for ranking ads in contextual advertising. Our method has shown to significantly improve relevance in offline evaluation and business metrics in online tests in a real large-scale advertising serving system. To scale our computations, we parallelize the algorithm in a MapReduce framework running on Hadoop.
【Keywords】: contextual advertising; ir measures; learning to rank; ndcg; ndcg-annealing; simplex algorithm; simulated annealing
【Paper Link】 【Pages】:387-396
【Authors】: Stephen Tyree ; Kilian Q. Weinberger ; Kunal Agrawal ; Jennifer Paykin
【Abstract】: Gradient Boosted Regression Trees (GBRT) are the current state-of-the-art learning paradigm for machine learned web-search ranking - a domain notorious for very large data sets. In this paper, we propose a novel method for parallelizing the training of GBRT. Our technique parallelizes the construction of the individual regression trees and operates using the master-worker paradigm as follows. The data are partitioned among the workers. At each iteration, the worker summarizes its data-partition using histograms. The master processor uses these to build one layer of a regression tree, and then sends this layer to the workers, allowing the workers to build histograms for the next layer. Our algorithm carefully orchestrates overlap between communication and computation to achieve good performance. Since this approach is based on data partitioning, and requires a small amount of communication, it generalizes to distributed and shared memory machines, as well as clouds. We present experimental results on both shared memory machines and clusters for two large scale web search ranking data sets. We demonstrate that the loss in accuracy induced due to the histogram approximation in the regression tree creation can be compensated for through slightly deeper trees. As a result, we see no significant loss in accuracy on the Yahoo data sets and a very small reduction in accuracy for the Microsoft LETOR data. In addition, on shared memory machines, we obtain almost perfect linear speed-up with up to about 48 cores on the large data sets. On distributed memory machines, we get a speedup of 25 with 32 processors. Due to data partitioning our approach can scale to even larger data sets, on which one can reasonably expect even higher speedups.
【Keywords】: boosted regression trees; boosting; distributed computing; machine learning; parallel computing; ranking; web search
【Paper Link】 【Pages】:397-406
【Authors】: Umut Ozertem ; Rosie Jones ; Benoît Dumoulin
【Abstract】: We provide a novel method of evaluating search results, which allows us to combine existing editorial judgments with the relevance estimates generated by click-based user browsing models. There are evaluation methods in the literature that use clicks and editorial judgments together, but our approach is novel in the sense that it allows us to predict the impact of unseen search models without online tests to collect clicks and without requesting new editorial data, since we are only re-using existing editorial data, and clicks observed for previous result set configurations. Since the user browsing model and the pre-existing editorial data cannot provide relevance estimates for all documents for the selected set of queries, one important challenge is to obtain this performance estimation where there are a lot of ranked documents with missing relevance values. We introduce a query and rank based smoothing to overcome this problem. We show that a hybrid of these smoothing techniques performs better than both query and position based smoothing, and despite the high percentage of missing judgments, the resulting method is significantly correlated (0.74) with DCG values evaluated using fully judged datasets, and approaches inter-annotator agreement. We show that previously published techniques, applicable to frequent queries, degrade when applied to a random sample of queries, with a correlation of only 0.29. While our experiments focus on evaluation using DCG, our method is also applicable to other commonly used metrics.
【Keywords】: relevance estimation; relevance evaluation; user browsing models
【Paper Link】 【Pages】:407-416
【Authors】: Azin Ashkan ; Charles L. A. Clarke
【Abstract】: The Maximum Entropy Method provides one technique for validating search engine effectiveness measures. Under this method, the value of an effectiveness measure is used as a constraint to estimate the most likely distribution of relevant documents under a maximum entropy assumption. This inferred distribution may then be compared to the actual distribution to quantify the "informativeness" of the measure. The inferred distribution may also be used to estimate values for other effectiveness measures. Previous work focused on traditional effectiveness measures, such as average precision. In this paper, we extend the Maximum Entropy Method to the newer cascade and intent-aware effectiveness measures by considering the dependency of the documents ranked in a results list. These measures are intended to reflect the novelty and diversity of search results in addition to the traditional relevance. Our results indicate that intent-aware measures based on the cascade model are informative in terms of both inferring actual distribution and predicting the values of other retrieval measures.
【Keywords】: diversity; effectiveness measures; evaluation; measure informativeness; novelty
【Paper Link】 【Pages】:417-426
【Authors】: Denis Helic ; Markus Strohmaier ; Christoph Trattner ; Markus Muhr ; Kristina Lerman
【Abstract】: Recently, a number of algorithms have been proposed to obtain hierarchical structures - so-called folksonomies - from social tagging data. Work on these algorithms is in part driven by a belief that folksonomies are useful for tasks such as: (a) Navigating social tagging systems and (b) Acquiring semantic relationships between tags. While the promises and pitfalls of the latter have been studied to some extent, we know very little about the extent to which folksonomies are pragmatically useful for navigating social tagging systems. This paper sets out to address this gap by presenting and applying a pragmatic framework for evaluating folksonomies. We model exploratory navigation of a tagging system as decentralized search on a network of tags. Evaluation is based on the fact that the performance of a decentralized search algorithm depends on the quality of the background knowledge used. The key idea of our approach is to use hierarchical structures learned by folksonomy algorithm as background knowledge for decentralized search. Utilizing decentralized search on tag networks in combination with different folksonomies as hierarchical background knowledge allows us to evaluate navigational tasks in social tagging systems. Our experiments with four state-of-the-art folksonomy algorithms on five different social tagging datasets reveal that existing folksonomy algorithms exhibit significant, previously undiscovered, differences with regard to their utility for navigation. Our results are relevant for engineers aiming to improve navigability of social tagging systems and for scientists aiming to evaluate different folksonomy algorithms from a pragmatic perspective.
【Keywords】: decentralized search; evaluation; folksonomies; navigation
【Paper Link】 【Pages】:427-436
【Abstract】: In this paper, we study the problem of expanding a set of given seed entities into a more complete set by discovering other entities that also belong to the same concept set. A typical example is to use "Canon" and "Nikon" as seed entities, and derive other entities (e.g., "Olympus") in the same concept set of camera brands. In order to discover such relevant entities, we exploit several web data sources, including lists extracted from web pages and user queries from a web search engine. While these web data are highly diverse with rich information that usually cover a wide range of the domains of interest, they tend to be very noisy. We observe that previously proposed random walk based approaches do not perform very well on these noisy data sources. Accordingly, we propose a new general framework based on iterative similarity aggregation, and present detailed experimental results to show that, when using general-purpose web data for set expansion, our approach outperforms previous techniques in terms of both precision and recall.
【Keywords】: named entity recognition; set expansion; similarity measure
【Paper Link】 【Pages】:437-446
【Authors】: Lorenzo Blanco ; Nilesh N. Dalvi ; Ashwin Machanavajjhala
【Abstract】: In this paper, we present a highly scalable algorithm for structurally clustering webpages for extraction. We show that, using only the URLs of the webpages and simple content features, it is possible to cluster webpages effectively and efficiently. At the heart of our techniques is a principled framework, based on the principles of information theory, that allows us to effectively leverage the URLs, and combine them with content and structural properties. Using an extensive evaluation over several large full websites, we demonstrate the effectiveness of our techniques, at a scale unattainable by previous techniques.
【Keywords】: information extraction; minimum description length; structural clustering
【Paper Link】 【Pages】:447-456
【Authors】: Anton Bakalov ; Ariel Fuxman ; Partha Pratim Talukdar ; Soumen Chakrabarti
【Abstract】: Search engines today offer a rich user experience, no longer restricted to "ten blue links". For example, the query "Canon EOS Digital Camera" returns a photo of the digital camera, and a list of suitable merchants and prices. Similar results are offered in other domains like food, entertainment, travel, etc. All these experiences are fueled by the availability of structured data about the entities of interest. To obtain this structured data, it is necessary to solve the following problem: given a category of entities with its schema, and a set of Web pages that mention and describe entities belonging to the category, build a structured representation for the entity under the given schema. Specifically, collect structured numerical or discrete attributes of the entities. Most previous approaches regarded this as an information extraction problem on individual documents, and made no special use of numerical attributes. In contrast, we present an end-to-end framework which leverages signals not only from the Web page context, but also from a collective analysis of all the pages corresponding to an entity, and from constraints related to the actual values within the domain. Our current implementation uses a general and flexible Integer Linear Program (ILP) to integrate all these signals into holistic decisions over all attributes. There is one ILP per entity and it is small enough to be solved in under 38 milliseconds in our experiments. We apply the new framework to a setting of significant practical importance: catalog expansion for Commerce search engines, using data from Bing Shopping. Finally, we present experiments that validate the effectiveness of the framework and its superiority to local extraction.
【Keywords】: attribute discovery; collective information extraction; commerce search; integer linear program; weak supervision
【Paper Link】 【Pages】:457-466
【Authors】: Salvatore Scellato ; Cecilia Mascolo ; Mirco Musolesi ; Jon Crowcroft
【Abstract】: Providers such as YouTube offer easy access to multimedia content to millions, generating high bandwidth and storage demand on the Content Delivery Networks they rely upon. More and more, the diffusion of this content happens on online social networks such as Facebook and Twitter, where social cascades can be observed when users increasingly repost links they have received from others. In this paper we describe how geographic information extracted from social cascades can be exploited to improve caching of multimedia files in a Content Delivery Network. We take advantage of the fact that social cascades can propagate in a geographically limited area to discern whether an item is spreading locally or globally. This informs cache replacement policies, which utilize this information to ensure that content relevant to a cascade is kept close to the users who may be interested in it. We validate our approach by using a novel dataset which combines social interaction data with geographic information: we track social cascades of YouTube links over Twitter and build a proof-of-concept geographic model of a realistic distributed Content Delivery Network. Our performance evaluation shows that we are able to improve cache hits with respect to cache policies without geographic and social information.
【Keywords】: content delivery networks; information propagation; online social networks
【Paper Link】 【Pages】:467-476
【Authors】: Sipat Triukose ; Zhihua Wen ; Michael Rabinovich
【Abstract】: Content delivery networks (CDNs) have become a crucial part of the modern Web infrastructure. This paper studies the performance of the leading content delivery provider - Akamai. It measures the performance of the current Akamai platform and considers a key architectural question faced by both CDN designers and their prospective customers: whether the co-location approach to CDN platforms adopted by Akamai, which tries to deploy servers in numerous Internet locations, brings inherent performance benefits over a more consolidated data center approach pursued by other influential CDNs such as Limelight. We believe the methodology we developed for this study will be useful for other researchers in the CDN arena.
【Keywords】: akamai; cdn performance; content delivery networks
【Paper Link】 【Pages】:477-486
【Authors】: Paul Heymann ; Hector Garcia-Molina
【Abstract】: We present "Turkalytics," a novel analytics tool for human computation systems. Turkalytics processes and reports logging events from workers in real-time and has been shown to scale to over one hundred thousand logging events per day. We present a state model for worker interaction that covers the Mechanical Turk (the SCRAP model) and a data model that demonstrates the diversity of data collected by Turkalytics. We show that Turkalytics is effective at data collection, in spite of it being unobtrusive. Lastly, we describe worker locations, browser environments, activity information, and other examples of data collected by our tool.
【Keywords】: analytics; crowdsourcing; human computation; human processing; human programming; mechanical turk
【Paper Link】 【Pages】:487-496
【Authors】: Gal Lavee ; Ronny Lempel ; Edo Liberty ; Oren Somekh
【Abstract】: Modern search engines are expected to make documents searchable shortly after they appear on the ever changing Web. To satisfy this requirement, the Web is frequently crawled. Due to the sheer size of their indexes, search engines distribute the crawled documents among thousands of servers in a scheme called local index-partitioning, such that each server indexes only several million pages. To ensure documents from the same host (e.g., www.nytimes.com) are distributed uniformly over the servers, for load balancing purposes, random routing of documents to servers is common. To expedite the time documents become searchable after being crawled, documents may be simply appended to the existing index partitions. However, indexing by merely appending documents, results in larger index sizes since document reordering for index compactness is no longer performed. This, in turn, degrades search query processing performance which depends heavily on index sizes. A possible way to balance quick document indexing with efficient query processing, is to deploy online document routing strategies that are designed to reduce index sizes. This work considers the effects of several online document routing strategies on the aggregated partitioned index size. We show that there exists a tradeoff between the compression of a partitioned index and the distribution of documents from the same host across the index partitions (i.e., host distribution). We suggest and evaluate several online routing strategies with regard to their compression, host distribution, and complexity. In particular, we present a term based routing algorithm which is shown analytically to provide better compression results than the industry standard random routing scheme. In addition, our algorithm demonstrates comparable compression performance and host distribution while having much better running time complexity than other document routing heuristics. Our findings are validated by experimental evaluation performed on a large benchmark collection of Web pages.
【Keywords】: document routing; index compression; index partitioning; inverted index; online algorithm
【Paper Link】 【Pages】:497-506
【Authors】: Andrei Z. Broder ; Shirshanka Das ; Marcus Fontoura ; Bhaskar Ghosh ; Vanja Josifovski ; Jayavel Shanmugasundaram ; Sergei Vassilvitskii
【Abstract】: We introduce the problem of evaluating graph constraints in content-based publish/subscribe (pub/sub) systems. This problem formulation extends traditional content-based pub/sub systems in the following manner: publishers and subscribers are connected via a (logical) directed graph G with node and edge constraints, which limits the set of valid paths between them. Such graph constraints can be used to model a Web advertising exchange (where there may be restrictions on how advertising networks can connect advertisers and publishers) and content delivery problems in social networks (where there may be restrictions on how information can be shared via the social graph). In this context, we develop efficient algorithms for evaluating graph constraints over arbitrary directed graphs G. We also present experimental results that demonstrate the effectiveness and scalability of the proposed algorithms using a realistic dataset from Yahoo!'s Web advertising exchange.
【Keywords】: graph constraints; indexing; pub/sub
【Paper Link】 【Pages】:507-516
【Authors】: Xiaoxin Yin ; Wenzhao Tan ; Chao Liu
【Abstract】: Recently answers for fact lookup queries have appeared on major search engines. For example, for the query Barack Obama date of birth Google directly shows "4 August 1961" above its regular results. In this paper, we describe FACTO, an end-to-end system for answering fact lookup queries for web search. FACTO extracts structured data from tables on the web, aggregates and cleans such data and stores them in a database. Given a web search query, FACTO will decide if it asks for facts in this database, and provides the most confident answer when possible. FACTO achieves higher precision and comparable coverage comparing with the fact lookup engines by Google and Ask.com, although FACTO is developed by a very small team. We present the challenges and our solutions in developing every component of FACTO. Some solutions are based on existing technologies, and many others are novel approaches proposed by us.
【Keywords】: information extraction; question answering; web search
【Paper Link】 【Pages】:517-526
【Authors】: Brendan Meeder ; Brian Karrer ; Amin Sayedi ; R. Ravi ; Christian Borgs ; Jennifer T. Chayes
【Abstract】: Understanding a network's temporal evolution appears to require multiple observations of the graph over time. These often expensive repeated crawls are only able to answer questions about what happened from observation to observation, and not what happened before or between network snapshots. Contrary to this picture, we propose a method for Twitter's social network that takes a single static snapshot of network edges and user account creation times to accurately infer when these edges were formed. This method can be exact in theory, and we demonstrate empirically for a large subset of Twitter relationships that it is accurate to within a few hours in practice. We study users who have a very large number of edges or who are recommended by Twitter. We examine the graph formed by these nearly 1,800 Twitter celebrities and their 862 million edges in detail, showing that a single static snapshot can give novel insights about Twitter's evolution. We conclude from this analysis that real-world events and changes to Twitter's interface for recommending users strongly influence network growth.
【Keywords】: graph analysis; large-scale data collection; network evolution; online social networks; user behavior
【Paper Link】 【Pages】:527-536
【Authors】: Mohsen Jamali ; Gholamreza Haffari ; Martin Ester
【Abstract】: A social rating network (SRN) is a social network in which edges represent social relationships and users (nodes) express ratings on some of the given items. Such networks play an increasingly important role in reviewing websites such as Epinions.com or online sharing websites like Flickr.com. In this paper, we first observe and analyze the temporal behavior of users in a social rating network, who express ratings and create social relations. Then, we model the temporal dynamics of an SRN based on our observations, using the bidirectional effects of ratings and social relations. While existing models for other types of social networks have captured some of the effects, our model is the first one to represent all four effects, i.e. social relations-on-ratings (social influence), social relations-on-social relations (transitivity), ratings-on-social relations (selection), and ratings-on-ratings (correlational influence). Existing works consider these effects as static and constant throughout the evolution of an SRN, however our observations reveal that these effects are actually dynamic. We propose a probabilistic generative model for SRNs, which models the strength and dynamics of each effect throughout the network evolution. This model can serve for the prediction of future links, ratings or community structures. Due to the sensitive nature of SRNs, another motivation for our work is the generation of synthetic SRN data sets for research purposes. Our experimental studies on two real life datasets (Epinions and Flickr) demonstrate that the proposed model produces social rating networks that agree with real world data on a comprehensive set of evaluation criteria.
【Keywords】: generative models; social rating networks; temporal dynamics; user behavioral modeling
【Paper Link】 【Pages】:537-546
【Authors】: Shuang-Hong Yang ; Bo Long ; Alexander J. Smola ; Narayanan Sadagopan ; Zhaohui Zheng ; Hongyuan Zha
【Abstract】: Targeting interest to match a user with services (e.g. news, products, games, advertisements) and predicting friendship to build connections among users are two fundamental tasks for social network systems. In this paper, we show that the information contained in interest networks (i.e. user-service interactions) and friendship networks (i.e. user-user connections) is highly correlated and mutually helpful. We propose a framework that exploits homophily to establish an integrated network linking a user to interested services and connecting different users with common interests, upon which both friendship and interests could be efficiently propagated. The proposed friendship-interest propagation (FIP) framework devises a factor-based random walk model to explain friendship connections, and simultaneously it uses a coupled latent factor model to uncover interest interactions. We discuss the flexibility of the framework in the choices of loss objectives and regularization penalties and benchmark different variants on the Yahoo! Pulse social networking system. Experiments demonstrate that by coupling friendship with interest, FIP achieves much higher performance on both interest targeting and friendship prediction than systems using only one source of information.
【Keywords】: interest targeting; link prediction; social network
【Paper Link】 【Pages】:547-556
【Authors】: Simla Ceyhan ; Xiaolin Shi ; Jure Leskovec
【Abstract】: Online peer-to-peer (P2P) lending services are a new type of social platform that enables individuals borrow and lend money directly from one to another. In this paper, we study the dynamics of bidding behavior in a P2P loan auction website, Prosper.com. We investigate the change of various attributes of loan requesting listings over time, such as the interest rate and the number of bids. We observe that there is herding behavior during bidding, and for most of the listings, the numbers of bids they receive reach spikes at very similar time points. We explain these phenomena by showing that there are economic and social factors that lenders take into account when deciding to bid on a listing. We also observe that the profits the lenders make are tied with their bidding preferences. Finally, we build a model based on the temporal progression of the bidding, that reliably predicts the success of a loan request listing, as well as whether a loan will be paid back or not.
【Keywords】: auction; dynamics; peer-to-peer lending service; user behavior
【Paper Link】 【Pages】:557-566
【Authors】: Mangesh Gupte ; Pravin Shankar ; Jing Li ; S. Muthukrishnan ; Liviu Iftode
【Abstract】: Social hierarchy and stratification among humans is a well studied concept in sociology. The popularity of online social networks presents an opportunity to study social hierarchy for different types of networks and at different scales. We adopt the premise that people form connections in a social network based on their perceived social hierarchy; as a result, the edge directions in directed social networks can be leveraged to infer hierarchy. In this paper, we define a measure of hierarchy in a directed online social network, and present an efficient algorithm to compute this measure. We validate our measure using ground truth including Wikipedia notability score. We use this measure to study hierarchy in several directed online social networks including Twitter, Delicious, YouTube, Flickr, LiveJournal, and curated lists of several categories of people based on different occupations, and different organizations. Our experiments on different online social networks show how hierarchy emerges as we increase the size of the network. This is in contrast to random graphs, where the hierarchy decreases as the network size increases. Further, we show that the degree of stratification in a network increases very slowly as we increase the size of the graph.
【Keywords】: hierarchy; measure; social networks
【Paper Link】 【Pages】:567-576
【Authors】: Abhinav Mishra ; Arnab Bhattacharya
【Abstract】: Many real-life graphs such as social networks and peer-to-peer networks capture the relationships among the nodes by using trust scores to label the edges. Important usage of such networks includes trust prediction, finding the most reliable or trusted node in a local subgraph, etc. For many of these applications, it is crucial to assess the prestige and bias of a node. The bias of a node denotes its propensity to trust/mistrust its neighbours and is closely related to truthfulness. If a node trusts all its neighbours, its recommendation of another node as trustworthy is less reliable. It is based on the idea that the recommendation of a highly biased node should weigh less. In this paper, we propose an algorithm to compute the bias and prestige of nodes in networks where the edge weight denotes the trust score. Unlike most other graph-based algorithms, our method works even when the edge weights are not necessarily positive. The algorithm is iterative and runs in O(km) time where k is the number of iterations and m is the total number of edges in the network. The algorithm exhibits several other desirable properties. It converges to a unique value very quickly. Also, the error in bias and prestige values at any particular iteration is bounded. Further, experiments show that our model conforms well to social theories such as the balance theory (enemy of a friend is an enemy, etc.).
【Keywords】: bias; deserve; prestige; social networks; trust-based network
【Paper Link】 【Pages】:577-586
【Authors】: Wei Dong ; Moses Charikar ; Kai Li
【Abstract】: K-Nearest Neighbor Graph (K-NNG) construction is an important operation with many web related applications, including collaborative filtering, similarity search, and many others in data mining and machine learning. Existing methods for K-NNG construction either do not scale, or are specific to certain similarity measures. We present NN-Descent, a simple yet efficient algorithm for approximate K-NNG construction with arbitrary similarity measures. Our method is based on local search, has minimal space overhead and does not rely on any shared global index. Hence, it is especially suitable for large-scale applications where data structures need to be distributed over the network. We have shown with a variety of datasets and similarity measures that the proposed method typically converges to above 90% recall with each point comparing only to several percent of the whole dataset on average.
【Keywords】: arbitrary similarity measure; iterative method; k-nearest neighbor graph
【Paper Link】 【Pages】:587-596
【Authors】: Paolo Boldi ; Marco Rosa ; Massimo Santini ; Sebastiano Vigna
【Abstract】: We continue the line of research on graph compression started with WebGraph, but we move our focus to the compression of social networks in a proper sense (e.g., LiveJournal): the approaches that have been used for a long time to compress web graphs rely on a specific ordering of the nodes (lexicographical URL ordering) whose extension to general social networks is not trivial. In this paper, we propose a solution that mixes clusterings and orders, and devise a new algorithm, called Layered Label Propagation, that builds on previous work on scalable clustering and can be used to reorder very large graphs (billions of nodes). Our implementation uses task decomposition to perform aggressively on multi-core architecture, making it possible to reorder graphs of more than 600 millions nodes in a few hours. Experiments performed on a wide array of web graphs and social networks show that combining the order produced by the proposed algorithm with the WebGraph compression framework provides a major increase in compression with respect to all currently known techniques, both on web graphs and on social networks. These improvements make it possible to analyse in main memory significantly larger graphs.
【Keywords】: graph clustering; graph compression; social networks; web graphs
【Paper Link】 【Pages】:597-606
【Authors】: Liran Katzir ; Edo Liberty ; Oren Somekh
【Abstract】: Online social networks have become very popular in recent years and their number of users is already measured in many hundreds of millions. For various commercial and sociological purposes, an independent estimate of their sizes is important. In this work, algorithms for estimating the number of users in such networks are considered. The proposed schemes are also applicable for estimating the sizes of networks' sub-populations. The suggested algorithms interact with the social networks via their public APIs only, and rely on no other external information. Due to obvious traffic and privacy concerns, the number of such interactions is severely limited. We therefore focus on minimizing the number of API interactions needed for producing good size estimates. We adopt the abstraction of social networks as undirected graphs and use random node sampling. By counting the number of collisions or non-unique nodes in the sample, we produce a size estimate. Then, we show analytically that the estimate error vanishes with high probability for smaller number of samples than those required by prior-art algorithms. Moreover, although our algorithms are provably correct for any graph, they excel when applied to social network-like graphs. The proposed algorithms were evaluated on synthetic as well real social networks such as Facebook, IMDB, and DBLP. Our experiments corroborated the theoretical results, and demonstrated the effectiveness of the algorithms.
【Keywords】: population estimator; sampling; social network; undirected graph
【Paper Link】 【Pages】:607-614
【Authors】: Siddharth Suri ; Sergei Vassilvitskii
【Abstract】: The clustering coefficient of a node in a social network is a fundamental measure that quantifies how tightly-knit the community is around the node. Its computation can be reduced to counting the number of triangles incident on the particular node in the network. In case the graph is too big to fit into memory, this is a non-trivial task, and previous researchers showed how to estimate the clustering coefficient in this scenario. A different avenue of research is to to perform the computation in parallel, spreading it across many machines. In recent years MapReduce has emerged as a de facto programming paradigm for parallel computation on massive data sets. The main focus of this work is to give MapReduce algorithms for counting triangles which we use to compute clustering coefficients. Our contributions are twofold. First, we describe a sequential triangle counting algorithm and show how to adapt it to the MapReduce setting. This algorithm achieves a factor of 10-100 speed up over the naive approach. Second, we present a new algorithm designed specifically for the MapReduce framework. A key feature of this approach is that it allows for a smooth tradeoff between the memory available on each individual machine and the total memory available to the algorithm, while keeping the total work done constant. Moreover, this algorithm can use any triangle counting algorithm as a black box and distribute the computation across many machines. We validate our algorithms on real world datasets comprising of millions of nodes and over a billion edges. Our results show both algorithms effectively deal with skew in the degree distribution and lead to dramatic speed ups over the naive implementation.
【Keywords】: clustering coefficient; mapreduce
【Paper Link】 【Pages】:615-624
【Authors】: Lars Backstrom ; Jon M. Kleinberg
【Abstract】: Bucket testing, also known as A/B testing, is a practice that is widely used by on-line sites with large audiences: in a simple version of the methodology, one evaluates a new feature on the site by exposing it to a very small fraction of the total user population and measuring its effect on this exposed group. For traditional uses of this technique, uniform independent sampling of the population is often enough to produce an exposed group that can serve as a statistical proxy for the full population. In on-line social network applications, however, one often wishes to perform a more complex test: evaluating a new social feature that will only produce an effect if a user and some number of his or her friends are exposed to it. In this case, independent uniform draws from the population will be unlikely to produce groups that contains users together with their friends, and so the construction of the sample must take the network structure into account. This leads quickly to challenging combinatorial problems, since there is an inherent tension between producing enough correlation to select users and their friends, but also enough uniformity and independence that the selected group is a reasonable sample of the full population. Here we develop an algorithmic framework for bucket testing in a network that addresses these challenges. First we describe a novel walk-based sampling method for producing samples of nodes that are internally well-connected but also approximately uniform over the population. Then we show how a collection of multiple independent subgraphs constructed this way can yield reasonable samples for testing. We demonstrate the effectiveness of our algorithms through computational experiments on large portions of the Facebook network.
【Keywords】: a/b testing; bucket testing; random walks; social networks
【Paper Link】 【Pages】:625-634
【Authors】: Paolo Boldi ; Marco Rosa ; Sebastiano Vigna
【Abstract】: The neighbourhood function NG(t) of a graph G gives, for each t ∈ N, the number of pairs of nodes x, y such that y is reachable from x in less that t hops. The neighbourhood function provides a wealth of information about the graph [10] (e.g., it easily allows one to compute its diameter), but it is very expensive to compute it exactly. Recently, the ANF algorithm [10] (approximate neighbourhood function) has been proposed with the purpose of approximating NG(t) on large graphs. We describe a breakthrough improvement over ANF in terms of speed and scalability. Our algorithm, called HyperANF, uses the new HyperLogLog counters [5] and combines them efficiently through broadword programming [8]; our implementation uses talk decomposition to exploit multi-core parallelism. With HyperANF, for the first time we can compute in a few hours the neighbourhood function of graphs with billions of nodes with a small error and good confidence using a standard workstation. Then, we turn to the study of the distribution of the distances between reachable nodes (that can be efficiently approximated by means of HyperANF), and discover the surprising fact that its index of dispersion provides a clear-cut characterisation of proper social networks vs. web graphs. We thus propose the spid (Shortest-Paths Index of Dispersion) of a graph as a new, informative statistics that is able to discriminate between the above two types of graphs. We believe this is the first proposal of a significant new non-local structural index for complex networks whose computation is highly scalable.
【Keywords】: effective diameter; neighbourhood function; probabilistic counters; shortest paths
【Paper Link】 【Pages】:635-644
【Authors】: Darko Anicic ; Paul Fodor ; Sebastian Rudolph ; Nenad Stojanovic
【Abstract】: Streams of events appear increasingly today in various Web applications such as blogs, feeds, sensor data streams, geospatial information, on-line financial data, etc. Event Processing (EP) is concerned with timely detection of compound events within streams of simple events. State-of-the-art EP provides on-the-fly analysis of event streams, but cannot combine streams with background knowledge and cannot perform reasoning tasks. On the other hand, semantic tools can effectively handle background knowledge and perform reasoning thereon, but cannot deal with rapidly changing data provided by event streams. To bridge the gap, we propose Event Processing SPARQL (EP-SPARQL) as a new language for complex events and Stream Reasoning. We provide syntax and formal semantics of the language and devise an effective execution model for the proposed formalism. The execution model is grounded on logic programming, and features effective event processing and inferencing capabilities over temporal and static knowledge. We provide an open-source prototype implementation and present a set of tests to show the usefulness and effectiveness of our approach.
【Keywords】: complex event processing; etalis; rule systems; semantic web; streams
【Paper Link】 【Pages】:645-654
【Authors】: Markus Krötzsch ; Frederick Maier ; Adila Krisnadhi ; Pascal Hitzler
【Abstract】: We propose a description-logic style extension of OWL 2 with nominal schemas which can be used like "variable nominal classes" within axioms. This feature allows ontology languages to express arbitrary DL-safe rules (as expressible in SWRL or RIF) in their native syntax. We show that adding nominal schemas to OWL 2 does not increase the worst-case reasoning complexity, and we identify a novel tractable language SROELV3(∩, x) that is versatile enough to capture the lightweight languages OWL EL and OWL RL.
【Keywords】: datalog; description logic; semantic web rule language; sroiq; tractability; web ontology language
【Paper Link】 【Pages】:655-664
【Authors】: Wangchao Le ; Songyun Duan ; Anastasios Kementsietsidis ; Feifei Li ; Min Wang
【Abstract】: The problem of answering SPARQL queries over virtual SPARQL views is commonly encountered in a number of settings, including while enforcing security policies to access RDF data, or when integrating RDF data from disparate sources. We approach this problem by rewriting SPARQL queries over the views to equivalent queries over the underlying RDF data, thus avoiding the costs entailed by view materialization and maintenance. We show that SPARQL query rewriting combines the most challenging aspects of rewriting for the relational and XML cases: like the relational case, SPARQL query rewriting requires synthesizing multiple views; like the XML case, the size of the rewritten query is exponential to the size of the query and the views. In this paper, we present the first native query rewriting algorithm for SPARQL. For an input SPARQL query over a set of virtual SPARQL views, the rewritten query resembles a union of conjunctive queries and can be of exponential size. We propose optimizations over the basic rewriting algorithm to (i) minimize each conjunctive query in the union; (ii) eliminate conjunctive queries with empty results from evaluation; and (iii) efficiently prune out big portions of the search space of empty rewritings. The experiments, performed on two RDF stores, show that our algorithms are scalable and independent of the underlying RDF stores. Furthermore, our optimizations have order of magnitude improvements over the basic rewriting algorithm in both the rewriting size and evaluation time.
【Keywords】: rewriting; sparql query; sparql views
【Paper Link】 【Pages】:665-674
【Authors】: Ceren Budak ; Divyakant Agrawal ; Amr El Abbadi
【Abstract】: In this work, we study the notion of competing campaigns in a social network and address the problem of influence limitation where a "bad" campaign starts propagating from a certain node in the network and use the notion of limiting campaigns to counteract the effect of misinformation. The problem can be summarized as identifying a subset of individuals that need to be convinced to adopt the competing (or "good") campaign so as to minimize the number of people that adopt the "bad" campaign at the end of both propagation processes. We show that this optimization problem is NP-hard and provide approximation guarantees for a greedy solution for various definitions of this problem by proving that they are submodular. We experimentally compare the performance of the greedy method to various heuristics. The experiments reveal that in most cases inexpensive heuristics such as degree centrality compare well with the greedy approach. We also study the influence limitation problem in the presence of missing data where the current states of nodes in the network are only known with a certain probability and show that prediction in this setting is a supermodular problem. We propose a prediction algorithm that is based on generating random spanning trees and evaluate the performance of this approach. The experiments reveal that using the prediction algorithm, we are able to tolerate about 90% missing data before the performance of the algorithm starts degrading and even with large amounts of missing data the performance degrades only to 75% of the performance that would be achieved with complete data.
【Keywords】: competing campaigns; information cascades; misinformation; social networks; submodular functions; supermodular functions
【Paper Link】 【Pages】:675-684
【Authors】: Carlos Castillo ; Marcelo Mendoza ; Barbara Poblete
【Abstract】: We analyze the information credibility of news propagated through Twitter, a popular microblogging service. Previous research has shown that most of the messages posted on Twitter are truthful, but the service is also used to spread misinformation and false rumors, often unintentionally. On this paper we focus on automatic methods for assessing the credibility of a given set of tweets. Specifically, we analyze microblog postings related to "trending" topics, and classify them as credible or not credible, based on features extracted from them. We use features from users' posting and re-posting ("re-tweeting") behavior, from the text of the posts, and from citations to external sources. We evaluate our methods using a significant number of human assessments about the credibility of items on a recent sample of Twitter postings. Our results shows that there are measurable differences in the way messages propagate, that can be used to classify them automatically as credible or not credible, with precision and recall in the range of 70% to 80%.
【Keywords】: social media analytics; social media credibility; twitter
【Paper Link】 【Pages】:685-694
【Authors】: Xinyu Xing ; Yu-Li Liang ; Hanqiang Cheng ; Jianxun Dang ; Sui Huang ; Richard Han ; Xue Liu ; Qin Lv ; Shivakant Mishra
【Abstract】: Online video chat services such as Chatroulette, Omegle, and vChatter that randomly match pairs of users in video chat sessions are fast becoming very popular, with over a million users per month in the case of Chatroulette. A key problem encountered in such systems is the presence of flashers and obscene content. This problem is especially acute given the presence of underage minors in such systems. This paper presents SafeVchat, a novel solution to the problem of flasher detection that employs an array of image detection algorithms. A key contribution of the paper concerns how the results of the individual detectors are fused together into an overall decision classifying the user as misbehaving or not, based on Dempster-Shafer Theory. The paper introduces a novel, motion-based skin detection method that achieves significantly higher recall and better precision. The proposed methods have been evaluated over real-world data and image traces obtained from Chatroulette.com.
【Keywords】: chatroulette; obscene content detection; online video chat
【Paper Link】 【Pages】:695-704
【Authors】: Daniel M. Romero ; Brendan Meeder ; Jon M. Kleinberg
【Abstract】: There is a widespread intuitive sense that different kinds of information spread differently on-line, but it has been difficult to evaluate this question quantitatively since it requires a setting where many different kinds of information spread in a shared environment. Here we study this issue on Twitter, analyzing the ways in which tokens known as hashtags spread on a network defined by the interactions among Twitter users. We find significant variation in the ways that widely-used hashtags on different topics spread. Our results show that this variation is not attributable simply to differences in "stickiness," the probability of adoption based on one or more exposures, but also to a quantity that could be viewed as a kind of "persistence" - the relative extent to which repeated exposures to a hashtag continue to have significant marginal effects. We find that hashtags on politically controversial topics are particularly persistent, with repeated exposures continuing to have unusually large marginal effects on adoption; this provides, to our knowledge, the first large-scale validation of the "complex contagion" principle from sociology, which posits that repeated exposures to an idea are particularly crucial when the idea is in some way controversial or contentious. Among other findings, we discover that hashtags representing the natural analogues of Twitter idioms and neologisms are particularly non-persistent, with the effect of multiple exposures decaying rapidly relative to the first exposure. We also study the subgraph structure of the initial adopters for different widely-adopted hashtags, again finding structural differences across topics. We develop simulation-based and generative models to analyze how the adoption dynamics interact with the network structure of the early adopters on which a hashtag spreads.
【Keywords】: information diffusion; social contagion; social media
【Paper Link】 【Pages】:705-714
【Authors】: Shaomei Wu ; Jake M. Hofman ; Winter A. Mason ; Duncan J. Watts
【Abstract】: We study several longstanding questions in media communications research, in the context of the microblogging service Twitter, regarding the production, flow, and consumption of information. To do so, we exploit a recently introduced feature of Twitter known as "lists" to distinguish between elite users - by which we mean celebrities, bloggers, and representatives of media outlets and other formal organizations - and ordinary users. Based on this classification, we find a striking concentration of attention on Twitter, in that roughly 50% of URLs consumed are generated by just 20K elite users, where the media produces the most information, but celebrities are the most followed. We also find significant homophily within categories: celebrities listen to celebrities, while bloggers listen to bloggers etc; however, bloggers in general rebroadcast more information than the other categories. Next we re-examine the classical "two-step flow" theory of communications, finding considerable support for it on Twitter. Third, we find that URLs broadcast by different categories of users or containing different types of content exhibit systematically different lifespans. And finally, we examine the attention paid by the different user categories to different news topics.
【Keywords】: classification; communication networks; communications; information flow; twitter; two-step flow
【Paper Link】 【Pages】:715-724
【Authors】: Demetres Antoniades ; Iasonas Polakis ; Georgios Kontaxis ; Elias Athanasopoulos ; Sotiris Ioannidis ; Evangelos P. Markatos ; Thomas Karagiannis
【Abstract】: Short URLs have become ubiquitous. Especially popular within social networking services, short URLs have seen a significant increase in their usage over the past years, mostly due to Twitter's restriction of message length to 140 characters. In this paper, we provide a first characterization on the usage of short URLs. Specifically, our goal is to examine the content short URLs point to, how they are published, their popularity and activity over time, as well as their potential impact on the performance of the web. Our study is based on traces of short URLs as seen from two different perspectives: i) collected through a large-scale crawl of URL shortening services, and ii) collected by crawling Twitter messages. The former provides a general characterization on the usage of short URLs, while the latter provides a more focused view on how certain communities use shortening services. Our analysis highlights that domain and website popularity, as seen from short URLs, significantly differs from the distributions provided by well publicised services such as Alexa. The set of most popular websites pointed to by short URLs appears stable over time, despite the fact that short URLs have a limited high popularity lifetime. Surprisingly short URLs are not ephemeral, as a significant fraction, roughly 50%, appears active for more than three months. Overall, our study emphasizes the fact that short URLs reflect an "alternative" web and, hence, provide an additional view on web usage and content consumption complementing traditional measurement sources. Furthermore, our study reveals the need for alternative shortening architectures that will eliminate the non-negligible performance penalty imposed by today's shortening services.
【Keywords】: online social networks; short urls; twitter
【Paper Link】 【Pages】:725-734
【Authors】: Silvio Lattanzi ; Alessandro Panconesi ; D. Sivakumar
【Abstract】: We demonstrate how a recent model of social networks ("Affiliation Networks", [21]) offers powerful cues in local routing within social networks, a theme made famous by sociologist Milgram's "six degrees of separation" experiments. This model posits the existence of an "interest space" that underlies a social network; we prove that in networks produced by this model, not only do short paths exist among all pairs of nodes but natural local routing algorithms can discover them effectively. Specifically, we show that local routing can discover paths of length O(log2 n) to targets chosen uniformly at random, and paths of length O(1) to targets chosen with probability proportional to their degrees. Experiments on the co-authorship graph derived from DBLP data confirm our theoretical results, and shed light into the power of one step of lookahead in routing algorithms for social networks.
【Keywords】: affiliation networks; milgram's experiment; social networks
【Paper Link】 【Pages】:735-744
【Authors】: Dashun Wang ; Zhen Wen ; Hanghang Tong ; Ching-Yung Lin ; Chaoming Song ; Albert-László Barabási
【Abstract】: Information spreading processes are central to human interactions. Despite recent studies in online domains, little is known about factors that could affect the dissemination of a single piece of information. In this paper, we address this challenge by combining two related but distinct datasets, collected from a large scale privacy-preserving distributed social sensor system. We find that the social and organizational context significantly impacts to whom and how fast people forward information. Yet the structures within spreading processes can be well captured by a simple stochastic branching model, indicating surprising independence of context. Our results build the foundation of future predictive models of information flow and provide significant insights towards design of communication platforms.
【Keywords】: context; information spread; network science; social networks; structure
【Paper Link】 【Pages】:745-754
【Authors】: Cristian Danescu-Niculescu-Mizil ; Michael Gamon ; Susan T. Dumais
【Abstract】: The psycholinguistic theory of communication accommodation accounts for the general observation that participants in conversations tend to converge to one another's communicative behavior: they coordinate in a variety of dimensions including choice of words, syntax, utterance length, pitch and gestures. In its almost forty years of existence, this theory has been empirically supported exclusively through small-scale or controlled laboratory studies. Here we address this phenomenon in the context of Twitter conversations. Undoubtedly, this setting is unlike any other in which accommodation was observed and, thus, challenging to the theory. Its novelty comes not only from its size, but also from the non real-time nature of conversations, from the 140 character length restriction, from the wide variety of social relation types, and from a design that was initially not geared towards conversation at all. Given such constraints, it is not clear a priori whether accommodation is robust enough to occur given the constraints of this new environment. To investigate this, we develop a probabilistic framework that can model accommodation and measure its effects. We apply it to a large Twitter conversational dataset specifically developed for this task. This is the first time the hypothesis of linguistic style accommodation has been examined (and verified) in a large scale, real world setting. Furthermore, when investigating concepts such as stylistic influence and symmetry of accommodation, we discover a complexity of the phenomenon which was never observed before. We also explore the potential relation between stylistic influence and network features commonly associated with social status.
【Keywords】: linguistic convergence; linguistic style accommodation; social media; twitter conversations
【Paper Link】 【Pages】:755-764
【Authors】: Matthew Richardson ; Ryen W. White
【Abstract】: Synchronous social Q&A systems exist on the Web and in the enterprise to connect people with questions to people with answers in real-time. In such systems, askers' desire for quick answers is in tension with costs associated with interrupting numerous candidate answerers per question. Supporting users of synchronous social Q&A systems at various points in the question lifecycle (from conception to answer) helps askers make informed decisions about the likelihood of question success and helps answerers face fewer interruptions. For example, predicting that a question will not be well answered may lead the asker to rephrase or retract the question. Similarly, predicting that an answer is not forthcoming during the dialog can prompt system behaviors such as finding other answerers to join the conversation. As another example, predictions of asker satisfaction can be assigned to completed conversations and used for later retrieval. In this paper, we use data from an instant-messaging-based synchronous social Q&A service deployed to an online community of over two thousand users to study the prediction of: (i) whether a question will be answered, (ii) the number of candidate answerers that the question will be sent to, and (iii) whether the asker will be satisfied by the answer received. Predictions are made at many points of the question lifecycle (e.g., when the question is entered, when the answerer is located, halfway through the asker-answerer dialog, etc.). The findings from our study show that we can learn capable models for these tasks using a broad range of features derived from user profiles, system interactions, question setting, and the dialog between asker and answerer. Our research can lead to more sophisticated and more useful real-time Q&A support.
【Keywords】: predictive models; question answering; synchronous social q&a
【Paper Link】 【Pages】:765-774
【Authors】: Mikhil Masli ; Werner Geyer ; Casey Dugan ; Beth Brownholtz
【Abstract】: Existing enterprise calendaring systems have suffered from problems like rigidity, lack of transparency, and poor integration with social networks. We present the system design and rationale for a novel social coordination mechanism, called "Suggestions," that addresses these issues. Our system integrates ideas drawn from designs of lightweight polling systems and one's social network into an open calendar tool, providing a space for users to coordinate, socialize around, or negotiate the "what" and the "when" of their events. Suggestions was released inside a large enterprise setting, where initial interviews revealed users' thoughts on transparent scheduling, reaching wider audiences and task appropriateness, and suggested ways to improve our design.
【Keywords】: calendar; electronic calendars; gcs; microcalendar; social coordination; social software
【Paper Link】 【Pages】:775-784
【Authors】: Tom Yeh ; Brandyn White ; Jose San Pedro ; Boris Katz ; Larry S. Davis
【Abstract】: The multimedia information retrieval community has dedicated extensive research effort to the problem of content-based image retrieval (CBIR). However, these systems find their main limitation in the difficulty of creating pictorial queries. As a result, few systems offer the option of querying by visual examples, and rely on automatic concept detection and tagging techniques to provide support for searching visual content using textual queries. This paper proposes and studies a practical multimodal web search scenario, where CBIR fits intuitively to improve the retrieval of rich information queries. Many online articles contain useful know-how knowledge about computer applications. These articles tend to be richly illustrated by screenshots. We present a system to search for such software know-how articles that leverages the visual correspondences between screenshots. Users can naturally create pictorial queries simply by taking a screenshot of the application to retrieve a list of articles containing a matching screenshot. We build a prototype comprising 150k articles that are classified into walkthrough, book, gallery, and general categories, and provide a comprehensive evaluation of this system, focusing on technical (accuracy of CBIR techniques) and usability (perceived system usefulness) aspects. We also consider the study of added value features of such a visual-supported search, including the ability to perform cross-lingual queries. We find that the system is able to retrieve matching screenshots for a wide variety of programs, across language boundaries, and provide subjectively more useful results than keyword-based web and image search engines.
【Keywords】: content-based image retrieval; multimodal search; online help
【Paper Link】 【Pages】:785-794
【Authors】: Young Yoon ; Chunyang Ye ; Hans-Arno Jacobsen
【Abstract】: In service-oriented architectures (SOA), independently developed Web services can be dynamically composed. However, the composition is prone to producing semantically conflicting interactions among the services. For example, in an interdepartmental business collaboration through Web services, the decision by the marketing department to clear out the inventory might be inconsistent with the decision by the operations department to increase production. Resolving semantic conflicts is challenging especially when services are loosely coupled and their interactions are not carefully governed. To address this problem, we propose a novel distributed service choreography framework. We deploy safety constraints to prevent conflicting behavior and enforce reliable and efficient service interactions via federated publish/subscribe messaging, along with strategic placement of distributed choreography agents and coordinators to minimize runtime overhead. Experimental results show that our framework prevents semantic conflicts with negligible overhead and scales better than a centralized approach by up to 60%.
【Keywords】: event processing; publish/subscribe; semantic conflict prevention; service choreography; service composition; service interaction
【Paper Link】 【Pages】:795-804
【Authors】: Samik Basu ; Tevfik Bultan
【Abstract】: Choreography analysis has been a crucial problem in service oriented computing. Interactions among services involve message exchanges across organizational boundaries in a distributed computing environment, and in order to build such systems in a reliable manner, it is necessary to develop techniques for analyzing such interactions. Choreography conformance involves verifying that a set of services behave according to a given choreography specification that characterizes their interactions. Unfortunately this is an undecidable problem when services interact with asynchronous communication. In this paper we present techniques that identify if the interaction behavior for a set of services remain the same when asynchronous communication is replaced with synchronous communication. This is called the synchronizability problem and determining the synchronizability of a set of services has been an open problem for several years. We solve this problem in this paper. Our results can be used to identify synchronizable services for which choreography conformance can be checked efficiently. Our results on synchronizability are applicable to any software infrastructure that supports message-based interactions.
【Keywords】: message-based interactions; synchronizability
【Paper Link】 【Pages】:805-814
【Authors】: Yunhui Zheng ; Tao Bao ; Xiangyu Zhang
【Abstract】: Ajax becomes more and more important for web applications that care about client side user experience. It allows sending requests asynchronously, without blocking clients from continuing execution. Callback functions are only executed upon receiving the responses. While such mechanism makes browsing a smooth experience, it may cause severe problems in the presence of unexpected network latency, due to the non-determinism of asynchronism. In this paper, we demonstrate the possible problems caused by the asynchronism and propose a static program analysis to automatically detect such bugs in web applications. As client side Ajax code is often wrapped in server-side scripts, we also develop a technique that extracts client-side JavaScript code from server-side scripts. We evaluate our technique on a number of real-world web applications. Our results show that it can effectively identify real bugs. We also discuss possible ways to avoid such bugs.
【Keywords】: ajax; automatic debugging; javascript; static analysis