The size, heterogeneity and dynamicity of data within an enterprise makes indexing, integration and analysis of the data increasingly difficult tasks. On the other hand, there has been a massive increase in the amount of high-quality open data available on the Web that could provide invaluable insights to data analysts and business intelligence specialists within the enterprise. The goal of Helix project is to provide users within the enterprise with a platform that allows them to perform online analysis of almost any type and amount of internal data using the power of external knowledge bases available on the Web. Such a platform requires a novel, data-format agnostic indexing mechanism, and light-weight data linking techniques that could link semantically related records across internal and external data sources of various characteristics. We present the initial architecture of our system and discuss several research challenges involved in building such a system.
Demo: Helix: Online Enterprise Data Analytics
Proceedings of the 20th World Wide Web Conference (WWW2011), Hyderabad, India
Two-Stream Indexing for Spoken Web Search
This paper presents two-stream processing of audio to index the audio content for Spoken Web search. The first stream indexes the meta-data associated with a particular audio document. The meta-data is usually very sparse, but accurate. This therefore results in a high-precision, low-recall index. The second stream uses a novel language-independent speech recognition to generate text to be indexed. Owing to the multiple languages and the noise in user generated content on the Spoken Web, the speech recognition accuracy of such systems is not high, thus they result in a low-precision, high-recall index. The paper attempts to use these two complementary streams to generate a combined index to increase the precision-recall performance in audio content search. The problem of audio content search is motivated by the real world implication of the Web in developing regions, where due to literacy and affordability issues, people use Spoken Web which consists of interconnected VoiceSites, which have content in audio. The experiments are based on more than 20,000 audio documents spanning over seven live VoiceSites and four different languages. The results suggest significant improvement over a meta-data-only or a speech-recognitiononly system, thus justifying the two-stream processing approach. Audio content search is a growing problem area and this paper wishes to be a first step to solving this at a large scale, across languages, in a Web context.
Scalable Integration and Processing of Linked Data
A Better Uncle for OWL: Nominal Schemas for Integrating Rules and Ontologies
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 SROELV_3 that is versatile enough to capture the lightweight languages OWL EL and OWL RL.
Paper Presentation: A Better Uncle for OWL: Nominal Schemas for Integrating Rules and Ontologies
A Self-Training Approach for Resolving Object Coreference on the Semantic Web
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.
Paper Presentation: A Self-Training Approach for Resolving Object Coreference on the Semantic Web
Caching Intermediate Result of SPARQL Queries
The complexity and growing scale of RDF data has made data management back end the performance bottleneck of Semantic Web applications. Caching is one of the ways that could solve this problem. However, few existing research projects focus on caching in RDF data processing. We present an adaptive caching scheme that caches intermediate result of basic graph pattern SPARQL queries. Benchmark test results are provided to illustrate the effectiveness of our caching scheme.
Generating Summaries for Ontology Search
This poster proposes a novel approach for generating summaries for ontology search. Following previous work, we define ontology summarization as the problem of ranking and selecting RDF sentences, for which we examine three aspects. Firstly, to assess the salience of RDF sentences in an ontology, we devise a bipartite graph model for representing the ontology and analyze random walks on this graph. Secondly, to reflect how an ontology is matched with user needs expressed via keyword queries, we incorporate query relevance into the selection of RDF sentences. Finally, to improve the unity of a summary, we optimize its cohesion in terms of the connections between constituent RDF sentences. We have implemented an online prototype system called Falcons Ontology Search.
Characterizing Search Intent Diversity into Click Models
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.
Is Pay-Per-Click Efficient? An Empirical Analysis of Click Values
Current sponsored search auction adopts per-click bidding. It implicitly assumes that an advertiser treats all clicks to be equally valuable. This is not always true in real world situations. Clicks which lead to conversions are definitely more valuable than those fraudulent clicks. In this work , we use post-ad-click behavior to measure a click's value and empirically show that for an advertiser, values of different clicks are highly variant. Thus for many clicks, the advertiser's single bid does not reflect his true valuations. This indicates that the sponsored search system under PPC mechanism is not efficient, or does not always give a slot to the advertiser who needs it most.
Paper Presentation: Characterizing Search Intent Diversity into Click Models
Video Summarization Via Transferrable Structured Learning
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.
EP-SPARQL: A Unified Language for Event Processing and Stream Reasoning
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.
Paper Presentation: EP-SPARQL: A Unified Language for Event Processing and Stream Reasoning
Paper Presentation: Video Summarization via Transferrable Structured Learning
Addressing the RDFa Publishing Bottleneck
In the more dynamic environments emerging from ad hoc and peer-to-peer networks, our research has explored the extent to which Web-based knowledge sharing as well as community formation require automation to understand human-readable content in a more distributed manner. RDFa is a syntactic format which can leverage this issue by allowing machine-readable data to be easily integrated into XHTML Web pages. Although there is a growing number of tools and techniques for generating and distilling RDFa, comparatively little work has been carried out on publishing existing RDF data sets as an XHTML+RDFa serialization. This paper proposes a generic approach to integrating RDF data into Web pages using the concept of automatically discovered "topic nodes". RDFa≤ is a proof-of-concept implementation of this approach and provides an on-line service assisting users in generating and personalizing pages with RDFa. We provide experimental results that support the viability of our approach to generating Web documents such as FOAF-based online profiles as well as RDF vocabularies with little user intervention.
Paper Presentation: Addressing the RDFa Publishing Bottleneck
An Adaptive Ontology-Based Approach to Identify Correlation Between Publications
In this paper, we propose an adaptive ontology-based approach for related paper identification, to meet most researchers' practical needs. By searching ontology, we can return a diverse set of papers that are explicitly and implicitly related to an input paper. Moreover, our approach does not rely on known ontology. Instead, we build and update ontology for a collection with any domain of interest. Being independent from known ontology, our approach is much more adaptive for different domains.
Automatically Generating Labels Based on Unified Click Model
Ground truth labels are one of the most important parts in many test collections for information retrieval. Each label, depicting the relevance between a query-document pair, is usually judged by a human, and this process is time-consuming and labor-intensive. Automatically Generating labels from click-through data has attracted increasing attention. In this paper, we propose a Unified Click Model to predict the multi-level labels, which aims at comprehensively considering the advantages of the Position Models and Cascade Models. Experiments show that the proposed click model outperforms the existing click models in predicting the multi-level labels, and could replace the labels judged by humans for test collections.
Autopedia: Automatic Domain-Independent Wikipedia Article Generation
This paper proposes a general framework, named Autopedia, to generate high-quality wikipedia articles for given concepts in any domains, by automatically selecting the best wikipedia template consisting the sub-topics to organize the article for the input concept. Experimental results on 4,526 concepts validate the effectiveness of Autopedia, and the wikipedia template selection approach which takes into account both the template quality and the semantic relatedness between the input concept and its sibling concepts, performs the best.
REACTOR: A Framework for Semantic Relation Extraction and Tagging Over Enterprise Data
Relation extraction from Web data has attracted a lot of attention in recent years. However, little work has been done when it comes to relation extraction from enterprise data regardless of the urgent needs to such work in real applications (e.g., E-discovery). In this paper, we propose a novel unsupervised hybrid framework, called REACTOR (abbreviated for a fRamework for sEmantic relAtion extraCtion and Tagging Over enteRprise data). We evaluate REACTOR over a real-world enterprise data set and empirical results show the effectiveness of REACTOR.
OntoWiki Mobile - Knowledge Management in Your Pocket
As comparatively powerful mobile computing devices become more common, mobile web applications have started gaining in popularity. Such mobile web applications as Google Mail or Calendar are already in everyday use of millions of people. Some first examples of these applications use Semantic Web technologies and information in the form of RDF (e.g. TripIt). An important feature of these applications is their ability to provide offline functionality with local updates for later synchronization with a web server. The key problem to this is the reconciliation, i.e. the problem of potentially conflicting updates from disconnected clients. In this paper we present an approach for a mobile semantic collaboration platform based on the OntoWiki framework. It allows users to collect instance data and refine the structure knowledge bases on the go. A crucial part of OntoWiki Mobile is the advanced conflict resolution for RDF stores. The approach is based on the EvoPat method for data evolution and ontology refactoring.
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.
FZI Research Center for Information Technology
On Computing Text-Based Similarity in Scientific Literature
This paper addresses computing of similarity among papers using text-based measures. First, we analyze the accuracy of the similarities computed using different parts of a paper, and propose a method of Keyword-Extension, which is very useful when text information is incomplete.
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.
Towards Semantic Knowledge Propagation from Text Corpus to Web Images
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.
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.
The Design and Usage of Tentative Events for Time-Based Social Coordination in the Enterprise
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.
Korea Advanced Institute of Science and Technology
Anytime Algorithm for QoS Web Service Composition
The QoS-aware web service composition (WSC) problem aims at the automatic construction of a composite web service with the optimal accumulated QoS value. It is, however, intractable to solve the QoS-aware WSC problem for large scale instances, since the problem corresponds to a global optimization problem. In this paper, we propose a novel anytime algorithm for the QoS-aware WSC problem to identify composite web services with high quality much earlier than an optimal algorithm and the beam stack search.
L3S Research Center, University of Hannover
Collaborative Classification Over P2P Networks
We propose a novel collaborative approach for distributed document classification, combining the knowledge of multiple users for improved organization of data such as individual document repositories or emails. The approach builds on top of a P2P network and outperforms the state of the art approaches in collaborative classification.
Filtering Microblogging Messages for Social TV
Social TV was named one of the ten most important emerging technologies in 2010 by the MIT Technology Review. Manufacturers of set-top boxes and televisions have recently started to integrate access to social networks into their products. Some of these systems allow users to read microblogging messages related to the TV program they are currently watching. However, such systems suffer from low precision and recall when they use the title of the show as keywords when retrieving messages, without any additional filtering. We propose a bootstrapping approach to collecting microblogging messages related to a given TV program. We start with a small set of annotated data, in which, for a given show and a candidate message, we annotate the pair to be relevant or irrelevant. From this annotated data set, we train an initial classifier. The features are designed to capture the association between the TV program and the message. Using our initial classifier and a large dataset of unlabeled messages we derive broader features for a second classifier to further improve precision.
Until recently, the TV viewing experience has not been a very social activity compared to activities on the World Wide Web. In this work, we will present a Voice-enabled Social TV system (VoiSTV) which allows users to interact, follow and monitor the online social media messages related to a TV show while watching it. Users can create, send, and reply to messages using spoken language. VoiSTV also provides metadata information about TV shows such as trends, hot topics, popularity as well as aggregated sentiment of show-related messages, all of which are valuable for TV program search and recommendation.
Social network services have become a viable source of information for users. In Twitter, information deemed important by the community propagates through retweets. Studying the characteristics of such popular messages is important for a number of tasks, such as breaking news detection, personalized message recommendation, viral marketing and others. This paper investigates the problem of predicting the popularity of messages as measured by the number of future retweets and sheds some light on what kinds of factors influence information propagation in Twitter. We formulate the task into a classification problem and study two of its variants by investigating a wide spectrum of features based on the content of the messages, temporal information, metadata of messages and users, as well as structural properties of the users' social graph on a large scale dataset. We show that our method can successfully predict messages which will attract thousands of retweets with good performance.
Web entities, such as documents and hyperlinks, are created for different purposes, or intents. Existing intent-based retrieval methods largely focus on information seekers' intent expressed by queries, ignoring the other side of the problem: web content creators' intent. We argue that understanding why the content was created is also important. In this work, we propose to classify such intents into two broad categories: "navigational" and "informational". Then we incorporate such intents into traditional retrieval models, and show their effect on ranking performance.
Exploiting Session-Like Behaviors in Tag Prediction
In social bookmarking systems, existing methods in tag prediction have shown that the performance of prediction can be significantly improved by modeling users preferences. However, these preferences are usually treated as constant over time, neglecting the temporal factor within users behaviors. In this paper, we study the problem of session-like behavior in social tagging systems and demonstrate that the predictive performance can be improved by considering sessions. Experiments, conducted on three public datasets, show that our session-based method can outperform baselines and two state-of-the-art algorithms significantly.
University of Maryland, Baltimore County
Adapting a Map Query Interface for a Gesturing Touch Screen Interface
NewsStand is an example application of a general framework that we are developing to enable searching for information using a map query interface, where the information results from monitoring the output of over 8,000 RSS news sources and is available for retrieval within minutes of publication. The user interface of NewsStand was recently adapted so that NewsStand can execute on mobile and tablet devices with a gesturing touch screen interface such as the iPhone, iPod Touch, and iPad. This action led to a discovery of some shortcomings of current mapping APIs as well as devising some interesting new widgets. These issues are discussed, and the realization can be seen by a demo at http://newsstand.umiacs.umd.edu on any of the above Apple devices as well as other devices that support gestures such as an Android phone.
A Case for Query by Image and Text Content: Searching Computer Help Using Screenshots and Keywords
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.
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.
A Self-Organizing Document Map Algorithm for Large Scale Hyperlinked Data Inspired by Neuronal Migration
Web document clustering is one of the research topics that is being pursued continuously due to the large variety of applications. Since Web documents usually have variety and diversity in terms of domains, content and quality, one of the technical difficulties is to find a reasonable number and size of clusters. In this research, we pay attention to SOMs (Self Organizing Maps) because of their capability of visualized clustering that helps users to investigate characteristics of data in detail. The SOM is widely known as a "scalable" algorithm because of its capability to handle large numbers of records. However, it is effective only when the vectors are small and dense. Although several research efforts on making the SOM scalable have been conducted, technical issues on scalability and performance for sparse high-dimensional data such as hyperlinked documents still remain. In this paper, we introduce MIGSOM, an SOM algorithm inspired by a recent discovery on neuronal migration. The two major advantages of MIGSOM are its scalability for sparse high-dimensional data and its clustering visualization functionality. In this paper, we describe the algorithm and implementation, and show the practicality of the algorithm by applying MIGSOM to a huge scale real data set: Wikipedia's hyperlink data.
From Actors, Politicians, to CEOs: Domain Adaptation of Relational Extractors Using a Latent Relational Mapping
We propose a method to adapt an existing relation extraction system to extract new relation types with minimum supervision. Our proposed method comprises two stages: learning a lower-dimensional projection between different relations, and learning a relational classifier for the target relation type with instance sampling.We evaluate the proposed method using a dataset that contains 2000 instances for 20 different relation types. Our experimental results show that the proposed method achieves a statistically significant macro-average F-score of 62.77. Moreover, the proposed method outperforms numerous baselines and a previously proposed weakly-supervised relation extraction method.
Harnessing the Wisdom of Crowds: Video Event Detection Based on Synchronous Comments
With the recent explosive growth of the number of videos on the Web, it becomes more important to facilitate users' demand for locating their preferred event clips in the lengthy and voluminous programs. Although there has been a great deal of study on generic event detection in recent years, the performance of existing approaches is still far from satisfactory. In this paper, we propose an integrated framework for general event detection. The key idea is that we utilize the synchronous comments to segment the video into clips with semantic text analysis, while taking into account the relationship between the users who write the comments. By borrowing the power of ``the wisdom of crowds'', we experimentally demonstrate that our approach can effectively detect video events.
Learning to Rank with Multiple Objective Functions
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.
A Distributed Framework for Reliable and Efficient Service Choreographies
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%.
20th International World Wide Web Conference
Companion Proceedings of the 20th World Wide Web Conference (WWW2011), Hyderabad, India
Social Event: High Tea with industry leaders
Social Event: Banquet Dinner with social event
Developers Track: Keynote: Cloud Computing - Different Cloud Models and Programming to them
Developers Track: Tutorial 1: Introduction to Windows Azure: Programming to a PaaS
Developers Track: Tutorial 2: Google Cloud services for Big Data
Developers Track: Tutorial 3: Scaling Hadoop to handle Big Data
Developers Track: Tutorial 4: Analytics on Hive
Developers Track: Tutorial 5: Cloud Security ‚Äì Developers’ Desiderata
Moderator: Chandra (CEO, Tata Consultancy Services) / Panelists: Kris Gopalakrishnan (CEO and MD, Infosys), N Ravishanker (IAS, Jt Secretary and CEO NIXI (National Internet Exchange of India)), Dr. Phatak (Indian Institute of Technology, Mumbai)
Industry Plenary Panel: A Universal, Inclusive WWW - The Next Frontier
Industry Track: Accessible Web (Accessibility for differently-abled and elderly)
Dr. R. Saravanan, Central Agricultural University
Industry Track: Web for Agricultural Extension
Moderator: Subu Goparaju (SVP, Infosys) / Panelists: Anil Bahuman (Promoter, Managing Director, Agrocom), Ananth Krishnan (CTO, TCS), Prof. Rajeev Sangal (IIIT Hyderabad), I. Vijaya Kumar, (CTO, Wipro)
Industry Panel: Collaborative and Social Web
Abhay Singavi, CEO - Preventive Health, Narayana Hrudayalaya
Industry Track: India development Gateway
Industry Track: Web for traffic management
The Computer Is the New Sewing Machine: Benefits and Perils of Crowdsourcing
Social Media: Source of Information or Bunch of Noise
Ranking on Large-Scale Graphs with Rich Metadata
Citizen Sensor Data Mining, Social Media Analytics and Development Centric Web Applications
Game Theoretic Models for Social Network Analysis
Speech and Multimodal Interaction in Mobile Search
Social Media Analytics: Tracking, Modeling and Predicting the Flow of Information Through Networks
Web-Based Open-Domain Information Extraction
WWW 2011 Invited Tutorial Overview: Latent Variable Models on the Internet
W3C-Day1: Accessible and multilingual Web
Dominique Hazael-Massieux and Francois Daoust
Demo: Visual Query System for Analyzing Social Semantic Web
Demo: Adapting a Map Query Interface for a Gesturing Touch Screen Interface
Demo: T-RecS: Team Recommendation System through Expertise and Cohesiveness
Demo: Blognoon: Exploring a Topic in the Blogosphere
Demo: Embedding MindMap As a Service for User-Driven Composition of Web Applications
Demo: Einstein: Physicist or Vegetarian? Summarizing Semantic Type Graphs for Knowledge Discovery
Demo: CATE: Context-Aware Timeline for Entity Illustration
Demo: OntoTrix: A Hybrid Visualization for Populated Ontologies
Demo: CoSi: Context-Sensitive Keyword Query Interpretation on RDF Databases
Demo: Accelerating Instant Question Search with Database Techniques
Demo: CONQUER: A System for Efficient Context-aware Query Suggestion
Demo: YAGO2: Exploring and Querying World Knowledge in Time, Space, Context, and Many Languages
Demo: DIDO: a Disease-Determinants Ontology from Web Sources
Demo: Automatically Building Probabilistic Databases from the Web
Demo: OXPath: Little Language, Little Memory, Great Value
Demo: Truthy: Mapping the Spread of Astroturf in Microblog Streams
Demo: Factal: Integrating Deep Web Based on Trust and Relevance
Demo: Exploratory search in multi-domain information spaces with Liquid Query
Demo: A User-Tunable Approach to Marketplace Search
Demo: A Tool for Fast Indexing and Querying of Graphs
Demo: LivePulse: Tapping Social Media for Sentiments in Real-Time
Demo: Filtering microblogging messages for Social TV
Keynote Address by Dr. A. P. J. Abdul Kalam
Keynote Address by Christos H. Papadimitriou
Paper Presentation: Cooperative Anti-Spam System Based On Multilayer Agents
Paper Presentation: Measurement and Analysis of Cyberlocker Services
Paper Presentation: Towards Liquid Service Oriented Architectures
Paper Presentation: Performance Enhancement of Scheduling Algorithms in Clusters and Grids using Improved Dynamic Load Balancing Techniques
Paper Presentation: Computational Advertising: Leveraging User Interaction & Contextual Factors for Improved Ad Retrieval & Ranking
Paper Presentation: Standing on the Shoulders of Ants: Stigmergy in the Web
Paper Presentation: Dynamic Learning-based Mechanism Design for Dependent Valued Exchange Economies
Paper Presentation: Fuzzy Associative Rule-based Approach for Pattern Mining and Identification and Pattern-based Classification
Paper Presentation: Ranked answer graph construction for keyword queries on RDF graphs without distance neighbourhood restriction
Paper Presentation: Application of Semantic Web Technologies for Multimedia Interpretation
Paper Presentation: The OXPath to Success in the Deep Web
Paper Presentation: Analysis and Tracking of Emotions in English and Bengali Texts: A Computational Approach
Paper Presentation: A Politeness Recognition Tool for Hindi: With Special Emphasis on Online Texts
Paper Presentation: Sentence-Level Contextual Opinion Retrieval
Paper Presentation: Summarization of Archived and Shared Personal Photo Collections
Paper Presentation: Wikipedia Vandalism Detection
Paper Presentation: Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter
Paper Presentation: Who Says What to Whom on Twitter
Paper Presentation: we.b: The web of short URLs
Paper Presentation: Sparse Hidden-Dynamics Conditional Random Fields for User Intent Understanding
Paper Presentation: Addressing People's Information Needs Directly in a Web Search Result Page
Paper Presentation: Here, There and Everywhere: Correlated Online Behaviors Can Lead to Overestimates of the Effects of Advertising
Paper Presentation: Adaptive Policies for Selecting Groupon Style Chunked Reward Ads in a Stochastic Knapsack Framework
Paper Presentation: A Game Theoretic Formulation of the Service Provisioning Problem in Cloud Systems
Paper Presentation: Learning to Re-Rank: Query-Dependent Image Re-Ranking Using Click Data
Paper Presentation: Towards Semantic Knowledge Propagation from Text Corpus to Web Images
Paper Presentation: Learning to Rank with Multiple Objective Functions
Paper Presentation: A Stochastic Learning-To-Rank Algorithm and Its Application to Contextual Advertising
Paper Presentation: Parallel Boosted Regression Trees for Web Search Ranking
Paper Presentation: A Unified Framework for Recommending Diverse and Relevant Queries
Paper Presentation: Improving recommendation for long-tail queries via templates
Paper Presentation: Learning to Model Relatedness for News Recommendation
Paper Presentation: Counting Triangles and the Curse of the Last Reducer
Paper Presentation: Network Bucket Testing
Paper Presentation: HyperANF: Approximating the Neighbourhood Function of Large Graphs on a Budget
Paper Presentation: Semi-Supervised Truth Discovery
Paper Presentation: SourceRank: Relevance and Trust Assessment for Deep Web Sources Based on Inter-Source Agreement
Paper Presentation: Search Result Diversity for Informational Queries
Paper Presentation: ARROW: Generating Signatures to Detect Drive-By Downloads
Paper Presentation: Prophiler: A fast filter for the large-scale detection of malicious web pages
Paper Presentation: Heat-seeking honeypots: design and experience
Paper Presentation: Pay as you Browse: Microcomputations as Micropayments in Web-based Services
Paper Presentation: Consideration Set Generation in Commerce Search
Paper Presentation: Towards a Theory Model for Product Search
Paper Presentation: Track Globally, Deliver Locally: Improving Content Delivery Networks by Tracking Geographic Social Cascades
Paper Presentation: Measuring a Commercial Content Delivery Network
Paper Presentation: Turkalytics: Analytics for Human Computation
Paper Presentation: Query Segmentation Revisited
Paper Presentation: Context-Sensitive Query Auto-Completion
Paper Presentation: Online Spelling Correction for Query Completion
Paper Presentation: Inverted Index Compression via Online Document Routing
Paper Presentation: Efficiently Evaluating Graph Constraints in Content-Based Publish/Subscribe
Paper Presentation: FACTO: A Fact Lookup Engine Based on Web Tables
Paper Presentation: A Word at a Time: Computing Word Relatedness using Temporal Semantic Analysis
Paper Presentation: Automatic Construction of a Context-Aware Sentiment Lexicon: An Optimization Approach
Paper Presentation: Web scale NLP: A case study on URL word breaking
Paper Presentation: Dynamics of Bidding in a P2P Lending Service: Effects of Herding and Predicting Loan Success
Paper Presentation: Finding Hierarchy in Directed Online Social Networks
Paper Presentation: Finding the bias and prestige of nodes in networks based on trust scores
Paper Presentation: Geographical topic discovery and comparison
Paper Presentation: The Web of Topics: Discovering the Topology of Topic Evolution in a Corpus
Paper Presentation: Unified Analysis of Streaming News
Paper Presentation: We Know Who You Followed Last Summer: Inferring Social Link Creation Times In Twitter
Paper Presentation: Modeling the Temporal Dynamics of Social Rating Networks using Bidirectional Effects of Social Relations and Rating Patterns
Paper Presentation: Like like alike -- Joint friendship and interest propagation in social networks
Paper Presentation: Model Characterization Curves for Federated Search Using Click-Logs: Predicting User Engagement Metrics for the Span of Feasible Operating Points
Paper Presentation: Generalized Link Suggestions via Web Site Clustering
Paper Presentation: Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures
Paper Presentation: Layered Label Propagation: A Multiresolution Coordinate-Free Ordering for Compressing Social Networks
Paper Presentation: Estimating Sizes of Social Networks via Biased Sampling
Paper Presentation: Evaluating New Search Engine Configurations with Pre-Existing Judgments and Clicks
Paper Presentation: On the Informativeness of Cascade and Intent-Aware Effectiveness Measures
Paper Presentation: Pragmatic Evaluation of Folksonomies
Paper Presentation: Limiting the Spread of Misinformation in Social Networks
Paper Presentation: Information Credibility on Twitter
Paper Presentation: SafeVchat: Detecting Obscene Content and Misbehaving Users in Online Video Chat Services
Paper Presentation: SEISA: Set Expansion by Iterative Similarity Aggregation
Paper Presentation: Highly Efficient Algorithms For Structural Clustering of Large Websites
Paper Presentation: SCAD: Collective Discovery of Attribute Values
Paper Presentation: Milgram-Routing in Social Networks
Paper Presentation: Information Spreading in Context
Paper Presentation: Mark my words! Linguistic style accommodation in social media
Paper Presentation: An Expressive Mechanism for Auctions on the Web
Paper Presentation: Incentivizing High-quality User-Generated Content
Paper Presentation: Buy-it-now or Take-a-chance: A simple sequential screening mechanism
Paper Presentation: Rewriting Queries on SPARQL Views
Paper Presentation: Supporting Synchronous Social Q&A Throughout the Question Lifecycle
Paper Presentation: The Design and Usage of Tentative Events for Time-based Social Coordination in the Enterprise
Paper Presentation: A Case for Query by Image and Text Content: Searching Computer Help using Screenshots and Keywords
Paper Presentation: A Distributed Framework for Reliable and Efficient Service Choreographies
Paper Presentation: Choreography Conformance via Synchronizability
Paper Presentation: Statically Locating Web Application Bugs Caused by Asynchronous Calls
Paper Presentation: Traffic Characterization and Internet Usage in Rural Africa
Paper Presentation: Low-Infrastructure Methods to Improve Internet Access for Mobile Users in Emerging Regions
Paper Presentation: Analyzing and Accelerating Web Access in a School in Peri-Urban India
Paper Presentation: The Lwazi Community Communication Service: Design and Piloting of a Voice-Based Information Service
Paper Presentation: Two-Stream Indexing for Spoken Web Search
Paper Presentation: Assistive Technology for vision-impairments: An agenda for the ICT4D community
Paper Presentation: Design and Implementation of Contextual Information Portals
Paper Presentation: Identifying Enrichment Candidates in Textbooks
Paper Presentation: Location Specific Summarization of Climatic and Agricultural Trends
First International Workshop on Knowledge Diversity on the Web
Eighth International workshop on Information Integration on the Web
First International Workshop on Social Media Engagement
1st International Temporal Web Analytics Workshop
1st International Workshop on Usage Analysis and the Web of Data
Joint WICOW/AIRWeb Workshop on Web Quality
2nd International Workshop on RESTful Design
Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter
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.
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 ex- amine the attention paid by the different user categories to different news topics.
Sparse Hidden-Dynamics Conditional Random Fields for User Intent Understanding
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).
Addressing People's Information Needs Directly in a Web Search Result Page
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.
Here, There, and Everywhere: Correlated Online Behaviors Can Lead to Overestimates of the Effects of Advertising
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.
Adaptive Policies for Selecting Groupon Style Chunked Reward Ads in a Stochastic Knapsack Framework
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.
A Game Theoretic Formulation of the Service Provisioning Problem in Cloud Systems
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.
Learning to Re-Rank: Query-Dependent Image Re-Ranking Using Click Data
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.
A Stochastic Learning-To-Rank Algorithm and Its Application to Contextual Advertising
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.
Parallel Boosted Regression Trees for Web Search Ranking
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.
A Unified Framework for Recommending Diverse and Relevant Queries
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.
Improving Recommendation for Long-Tail Queries Via Templates
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{<city> 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.
Learning to Model Relatedness for News Recommendation
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.
Counting Triangles and the Curse of the Last Reducer
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.
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.
HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget
The neighbourhood function N(t) of a graph G gives, for each t, 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 (e.g., it easily allows one to compute its diameter), but it is very expensive to compute it exactly. Recently, the ANF algorithm (approximate neighbourhood function) has been proposed with the purpose of approximating N(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 and combines them efficiently through broadword programming; our implementation uses overdecomposition 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 shortest paths 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.
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.
SourceRank: Relevance and Trust Assessment for Deep Web Sources Based on Inter-Source Agreement
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".
Search Result Diversity for Informational Queries
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.
ARROW: GenerAting SignatuRes to Detect DRive-By DOWnloads
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.
Prophiler: A Fast Filter for the Large-Scale Detection of Malicious Web Pages
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.
Heat-Seeking Honeypots: Design and Experience
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.
Pay as You Browse: Microcomputations as Micropayments in Web-Based Services
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.
Consideration Set Generation in Commerce Search
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.
Towards a Theory Model for Product Search
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.
Track Globally, Deliver Locally: Improving Content Delivery Networks by Tracking Geographic Social Cascades
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.
Measuring a Commercial Content Delivery Network
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.
Turkalytics: Analytics for Human Computation
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.
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 50000 human-annotated queries, it is two orders of magnitude larger than the corpus being used up to now.
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.
Online Spelling Correction for Query Completion
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.
Inverted Index Compression via Online Document Routing
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.
Efficiently Evaluating Graph Constraints in Content-Based Publish/Subscribe
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.
FACTO: A Fact Lookup Engine Based on Web Tables
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.
A Word at a Time: Computing Word Relatedness Using Temporal Semantic Analysis
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.
Automatic Construction of a Context-Aware Sentiment Lexicon: An Optimization Approach
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.
Web Scale NLP: A Case Study on URL Word Breaking
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 implementa-tion 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.
Dynamics of Bidding in A P2P Lending Service: Effects of Herding and Predicting Loan Success
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 bid- ding 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 ob- serve 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.
Finding Hierarchy in Directed Online Social Networks
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 de fine 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.
Finding the Bias and Prestige of Nodes in Networks based on Trust Scores
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.).
Geographical Topic Discovery and Comparison
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.
The Web of Topics: Discovering the Topology of Topic Evolution in a Corpus
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.
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.
We Know Who You Followed Last Summer: Inferring Social Link Creation Times in Twitter
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.
Modeling the Temporal Dynamics of Social Rating Networks Using Bidirectional Effects of Social Relations and Rating Patterns
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.
Like like alike - Joint Friendship and Interest Propagation in Social Networks
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.
Model Characterization Curves for Federated Search Using Click-Logs: Predicting User Engagement Metrics for the Span of Feasible Operating Points
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.
Generalized Link Suggestions Via Web Site Clustering
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.
Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures
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.
Layered Label Propagation: A Multiresolution Coordinate-Free Ordering for Compressing Social Networks
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.
Estimating Sizes of Social Networks via Biased Sampling
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.
Evaluating New Search Engine Configurations with Pre-Existing Judgments and Clicks
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.
On the Informativeness of Cascade and Intent-Aware Effectiveness Measures
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.
Limiting the Spread of Misinformation in Social Networks
In this work, we study the notion of competing campaigns in a social network and address the problem of in uence 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 de nitions 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 in uence 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.
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%.
SafeVchat: Detecting Obscene Content and Misbehaving Users in Online Video Chat Services
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.
SEISA: Set Expansion by Iterative Similarity Aggregation
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.
Highly Efficient Algorithms for Structural Clustering of Large Websites
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.
SCAD: Collective Discovery of Attribute Values
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.
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.
Mark My Words! Linguistic Style Accommodation in Social Media
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.
An Expressive Mechanism for Auctions on the Web
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 Aggarwal et al. (2009) 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.
Incentivizing High-Quality User-Generated Content
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.
Buy-It-Now or Take-a-Chance: A Simple Sequential Screening Mechanism
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.
Supporting Synchronous Social Q&A Throughout the Question Lifecycle
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 syn-chronous 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.
Choreography Conformance via Synchronizability
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.
Statically Locating Web Application Bugs Caused by Asynchronous Calls
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.
Most product search engines today build on models of relevance 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. We instantiate our research by building a demo search engine for hotels that takes into account consumer heterogeneous preferences, and also accounts for the varying hotel price. Moreover, we achieve this without explicitly asking the preferences or purchasing histories of individual consumers but by using aggregate demand data. This new ranking system is able to recommend consumers products with ``best value for money'' in a privacy-preserving manner. The demo is accessible at http://nyuhotels.appspot.com/
A Tool for Fast Indexing and Querying of Graphs
We present a tool called GiS for indexing and querying a large database of labeled, undirected graphs. Such graphs can model chemical compounds, represent contact maps constructed from 3D structure of proteins, and so forth. GiS supports exact subgraph matching and approximate graph matching queries. It adopts a suite of new techniques and algorithms for (a) fast construction of disk-based indexes with small index sizes, and (b) efficient query processing with high precision of matching. During the demo, the user can index real graph datasets using a recommendation facility in GiS, pose exact subgraph matching and approximate graph matching queries, and view matching graphs using the Jmol browser.
A User-Tunable Approach to Marketplace Search
The notion of relevance is key to the performance of search engines as they interpret the user queries and respond with matching results. Online search engines have used other features beyond pure IR features to return relevant matching documents. However, over-emphasis on relevance could lead to redundancy in search results. In document search, diversity is simply the variety of documents that span the result set. In an online marketplace the diversity in the result set is represented by items for sale by different sellers at different prices with different sales options. For such a marketplace, in order to minimize query abandonment and the risk of dissatisfaction to the average user, several factors like diversity, trust and value need to be taken into account. Previous work in this field [4] has shown an impossibility result that there exists no such function that can optimize for all these factors. Since these factors and the measures associated with the factors could be subjective we take an approach of giving the control back to the user. In this paper we describe an interface which enables users to have more control over the optimization function used to present the results. We demonstrate this for search on eBay - one of the largest online marketplaces with a vibrant user community and dynamic inventory. We use an algorithm based on bounded greedy selection [5] to construct the result set based on parameters specified by the user.
Accelerating Instant Question Search with Database Techniques
Distributed question answering services, like Yahoo Answer and Aardvark, are known to be useful for end users and have also opened up numerous topics ranging in many research fields. In this paper, we propose a user-support tool for composing questions in such services. Our system incrementally recommends similar questions while users are typing their question in a sentence, which gives the users opportunities to know that there are similar questions that have already been solved. A question database is semantically analyzed and searched in the semantic space by boosting the performance of similarity searches with database techniques such as server/client caching and LSH (Locality Sensitive Hashing). The more text the user enters, the more similar the recommendations will become to the ultimately desired question. This unconscious editing-as-a-sequence-of-searches approach helps users to form their question incrementally through interactive supplementary information. Not only askers nor repliers, but also service providers have advantages such as that the knowledge of the service will be autonomously refined by avoiding for novice users to repeat questions which have been already solved.
Automatically Building Probabilistic Databases from the Web
A relevant number of web sites publish structured data about recognizable concepts (such as stock quotes, movies, restau- rants, etc.). There is a great chance to create applications that rely on a huge amount of data taken from the Web. We present an automatic and domain independent system that performs all the steps required to benefit from these data: it discovers data intensive web sites containing information about an entity of interest, extracts and integrate the published data, and finally performs a probabilistic analysis to characterize the impreciseness of the data and the accuracy of the sources. The results of the processing can be used to populate a probabilistic database.
Blognoon: Exploring a Topic in the Blogosphere
We demonstrate Blognoon, a semantic blog search engine with the focus on topic exploration and navigation. Blognoon provides concept search instead of traditional keywords search and improves ranking by identifying main topics of posts. It enhances navigation over the Blogosphere with faceted interfaces and recommendations.
CATE: Context-Aware Timeline for Entity Illustration
Wikipedia has become one of the most authoritative information sources on the Web. Each article in Wikipedia provides a portrait of a certain entity. However, such a portrait is far from complete. An informative portrait of an entity should also reveal the context the entity belongs to. For example, for a person, major historical, political and cultural events that coincide with her life are important and should be included in that person s portrait. Similarly, the person s interactions with other people are also important. All this information should be summarized and presented in an appealing and interactive visual interface that enables users to quickly scan the entity s portrait. We demonstrate CATE which is a system that utilizes Wikipedia to create a portrait of a given entity of interest. We provide a visualization tool that summarizes the important events related to the entity . The novelty of our approach lies in seeing the portrait of an entity in a broader context, synchronous with its time.
CONQUER: A System for Efficient Context-Aware Query Suggestions
Many of today's search engines provide autocompletion while the user is typing a query string. This type of dynamic query suggestion can help users to formulate queries that better represent their search intent during Web search interactions. In this paper, we demonstrate our query suggestion system called CONQUER, which allows to efficiently suggest queries for a given partial query and a number of available query context observations. The context-awareness allows for suggesting queries tailored to a given context, e.g., the user location or the time of day. CONQUER uses a suggestion model that is based on the combined probabilities of sequential query patterns and context observations. For this, the weight of a context in a query suggestion can be adjusted online, for example, based on the learned user behavior or user profiles. We demonstrate the functionality of CONQUER based on 6 million queries from an AOL query log using the time of day and the country domain of the clicked URLs in the search result as context observations.
CoSi: Context-Sensitive Keyword Query Interpretation on RDF Databases
The demo will present CoSi, a system that enables context-sensitive interpretation of keyword queries on RDF databases. The techniques for representing, managing and exploiting query history are central to achieving this objective. The demonstration will show the effectiveness of our approach for capturing a user's querying context from their query history. Further, it will show how context is utilized to influence the interpretation of a new query. The demonstration is based on DBPedia, the RDF representation of Wikipedia.
DIDO: A Disease-Determinants Ontology from Web Sources
This paper introduces DIDO, a system providing convenient access to knowledge about factors involved in human diseases, automatically extracted from textual Web sources. The knowledge base is bootstrapped by integrating entities from hand-crafted sources like MeSH and OMIM. As these are short on relationships between dierent types of biomedical entities, DIDO employs exible and robust pattern learning and constraint-based reasoning methods to automatically extract new relational facts from textual sources. These facts can then be iteratively added to the knowledge base. The result is a semantic graph of typed entities and relations between diseases, their symptoms, and their factors, with emphasis on environmental factors but covering also molecular determinants. We demonstrate the value of DIDO for knowledge discovery about causal factors and properties of complex diseases, including factor-disease chains.
Einstein: Physicist or Vegetarian? Summarizing Semantic Type Graphs for Knowledge Discovery
The Web and, in particular, knowledge-sharing communities such as Wikipedia contain a huge amount of information encompassing disparate and diverse fields. Knowledge bases such as DBpedia or Yago represent the data in a concise and more structured way bearing the potential of bringing database tools to Web Search. The wealth of data, however, poses the challenge of how to retrieve important and valuable information, which is often intertwined with trivial and less important details. This calls for an efficient and automatic summarization method. In this demonstration proposal, we consider the novel problem of summarizing the information related to a given entity, like a person or an organization. To this end, we utilize the rich type graph that knowledge bases provide for each entity, and define the problem of selecting the best cost-restricted subset of types as summary with good coverage of salient properties. We propose a demonstration of our system which allows the user to specify the entity to summarize, an upper bound on the cost of the resulting summary, as well as to browse the knowledge base in a more simple and intuitive manner.
Embedding MindMap as a Service for User-Driven Composition of Web Applications
The World Wide Web is evolving towards a very large distributed platform allowing ubiquitous access to a wide range of Web applications with minimal delay and no installation required. Such Web applications range from having users undertake simple tasks, such as filling a form, to more complex tasks including collaborative work, project management, and more generally, creating, consulting, annotating, and sharing Web content. However, users are lacking a simple but yet powerful mechanism to compose Web applications, similarly to what desktop environments allowed for decades using the file explorer paradigm and the desktop metaphor. Attempts have been made to adapt the desktop metaphor to the Web environment giving birth to Webtops (Web desktops). It essentially consisted of embedding a desktop environment in a Web browser and provide access to various Web applications within the same User Interface. However, those attempts did not take into consideration to the radical differences between Web and desktop environments and applications. In this work, we introduce a new approach for Web application composition based on the mindmap metaphor. It allows browsing artifacts (Web resources) and enabling user-driven composition of their associated Web applications. Essentially, a mindmap is a graph of widgets representing artifacts created or used by Web applications and allow to list and launch all possible Web applications associated to each artifact. A tool has been developed to experiment the new metaphor and is provided as a service to be embedded in Web applications via a Web browser's plug-in. We demonstrate in this paper three case studies regarding the DBLP Web site, Wikipedia and Google Picasa Web applications.
Exploratory Search in Multi-Domain Information Spaces with Liquid Query
Search Computing (SeCo) aims at building search applications that bridge the gap between general-purpose and vertical search engines. SeCo queries extract ranked information about several interconnected domains, such as hotels , restaurants or concerts , by interacting with Web data sources which are wrapped as search services; an example of query is: "Find a good Jazz concert close to the user's current location, together with close-by good restaurants and hotels". The SeCo system supports the deployment of search applications, by providing a generic software architecture and the tools for service and query registration, for query formulation and execution, and for result browsing. In this demo paper, we focus on the Liquid Query (LQ) interface which supports the iteration over query formulation, result visualization and query refinement, with commands for perusing the result set, changing the visualization of data based on their type (e.g., geographical or temporal) and interacting with the remote search services. It also supports an exploratory search approach, where the user starts by accessing one data source (e.g., an event listing for finding interesting concerts), then is assisted in progressively joining other correlated sources in an interactive exploration of the search space. The exploration paths can be chosen on the fly and the navigation history can be browsed back and forth for cross-checking the retrieved options.
Factal: Integrating Deep Web Based on Trust and Relevance
We demonstrate "Factal"---a system for integrating deep web sources. Factal is based on the recently introduced source selection method "SourceRank"; which is a measure of trust and relevance based on the agreement between the sources. SourceRank selects popular and trustworthy sources from autonomous and open collections like the deep web. This trust and popularity awareness distinguishes Factal from the existing systems like Google Product Search. Factal selects and searches active online databases on multiple domains. The demonstration scenarios include improved trustworthiness, relevance of results, and comparison shopping. We believe that by incorporating effective source selection based on the SourceRank, Factal demonstrates a significant step towards a deep-web-scale integration system.
LivePulse: Tapping Social Media for Sentiments in Real-Time
The rise of Twitter, blogs, review sites and social sites has motivated people to express their opinions publicly and more frequently than ever before. This has fueled the emerging field known as sentiment analysis whose goal is to translate the vagaries of human emotion into hard data. LivePulse is a tool that taps into the growing business interest in what is being said online with the particular characteristic of doing so in real-time. LivePulse integrates novel algorithms for sentiment analysis and a configurable dashboard with different kinds of dynamic charts that change as new data is ingested. It also provides support to drill down and visually explore the sentiment scores to understand how they were computed and what are the emotions expressed about a given aspect or topic. Our tool has been researched and prototyped at HP Labs in close interaction with internal and external customers whose valuable feedback has been crucial for improving the tool. This paper presents an overview of LivePulse s architecture and functionality, and illustrates how it would be demoed.
OntoTrix: A Hybrid Visualization for Populated Ontologies
Most Semantic Web data visualization tools structure the representation according to the concept definitions and interrelations that constitute the ontology's vocabulary. Instances are often treated as somewhat peripheral information, when considered at all. These instances, that populate ontologies, represent an essential part of any knowledge base, and are often orders of magnitude more numerous than the concept definitions that give them machine-processable meaning. We present a visualization technique designed to enable users to visualize large instance sets and the relations that connect them. This hybrid visualization uses both node-link and adjacency matrix representations of graphs to visualize different parts of the data depending on their semantic and local structural properties, exploiting ontological knowledge to drive the graph layout. The representation is embedded in an environment that features advanced interaction techniques for easy navigation, including support for smooth continuous zooming and coordinated views.
OXPath: Little Language, Little Memory, Great Value
Data about everything is readily available on the web-but often only accessible through elaborate user interactions. For automated decision support, extracting that data is essential, but infeasible with existing heavy-weight data extraction systems. In this demonstration, we present OXPath, a novel approach to web extraction, with a system that supports informed job selection and integrates information from several different web sites. By carefully extending XPath, OXPath exploits its familiarity and provides a light-weight interface, which is easy to use and embed. We highlight how OXPath guarantees optimal page buffering, storing only a constant number of pages for non-recursive queries.
T-RecS: Team Recommendation System Through Expertise and Cohesiveness
Searching for people by exploration of social networks structure is an interesting problem which has recently gathered a lot of attention. Expert recommendation is an important but also extensively researched problem. In contrast, the generalized problem of team recommendation has not been studied a lot. The purpose of this demo is to show a multidisciplinary team search and recommendation prototype. While the current demo uses specific (NTU academic) data-set, the framework is generic, and can be extended for other domains subject to availability of suitable information.
Truthy: Mapping the Spread of Astroturf in Microblog Streams
Online social media are complementing and in some cases replacing person-to-person social interaction and redefining the diffusion of information. In particular, microblogs have become crucial grounds on which public relations, marketing, and political battles are fought. We demonstrate a web service that tracks political memes in Twitter and helps detect astroturfing, smear campaigns, and other misinformation in the context of U.S. political elections. We also present some cases of abusive behaviors uncovered by our service. Our web service is based on an extensible framework that will enable the real-time analysis of meme diffusion in social media by mining, visualizing, mapping, classifying, and modeling massive streams of public microblogging events.
Visual Query System for Analyzing Social Semantic Web
The social web is becoming increasingly popular and important, because it creates the collective intelligence, which can produce more value than the sum of individuals. The social web uses the Semantic Web technology RDF to describe the social data in a machine-readable way. RDF query languages play certainly an important role in the social data analysis for extracting the collective intelligence. However, constructing such queries is not trivial since the social data is often quite large and assembled from a large number of different sources. In order to solve these challenges, we develop a Visual Query System (VQS) for helping the analysts of social data and other semantic data to formulate such queries easily and exactly. In this VQS, we suggest a condensed data view, a browser-like query creation system for absolute beginners and a Visual Query Language (VQL) for beginners and experienced users. Using the browser-like query creation or the VQL, the analysts of social data and other semantic data can construct queries with no or little syntax knowledge; using the condensed view, they can determine easily what queries should to be used. Furthermore, our system also supports precise suggestions to extend and refine existing queries.
YAGO2: Exploring and Querying World Knowledge in Time, Space, Context, and Many Languages
We present YAGO2, an extension of the YAGO knowledge base with focus on temporal and spatial knowledge. It is automatically built from Wikipedia, GeoNames, and WordNet, and contains nearly 10 million entities and events, as well as 80 million facts representing general world knowledge. An enhanced data representation introduces time and location as first-class citizens. The wealth of spatio-temporal information in YAGO can be explored either graphically or through a special time- and space-aware query language.
Analyzing and Accelerating Web Access in a School in Peri-Urban India
While computers and Internet access have growing penetration amongst schools in the developing world, intermittent connectivity and limited bandwidth often prevent them from being fully utilized by students and teachers. In this paper, we make two contributions to help address this problem. First, we characterize six weeks of HTTP traffic from a primary school outside of Bangalore, India, illuminating opportunities and constraints for improving performance in such settings. Second, we deploy an aggressive caching and prefetching engine and show that it accelerates a user s overall browsing experience (apart from video content) by 2.8x. Our accelerator leverages innovative techniques that have been proposed, but not evaluated in detail, including the effectiveness of serving stale pages, cached page highlighting, and client-side prefetching. Unlike proxy-based techniques, our system is bundled as an open-source Firefox plugin and runs directly on client machines. This allows easy installation and configuration by end users, which is especially important in developing regions where a lack of permissions or technical expertise often prevents modification of internal network settings.
Assistive Technology for vision-impairments: An agenda for the ICT4D community
In recent years, ICTD (Information Communications Technology and Development) has grown in significance as an area of engineering research that has focused on low-cost appropriate technologies for the needs of a developing world largely underserved by the dominant modes of technology design. Assistive Technologies (AT) used by people with disabilities facilitate greater equity in the social and economic public sphere. However, by and large such technologies are designed in the industrialized world, for people living in those countries. This is especially true in the case of AT for people with vision impairments market-prevalent technologies are both very expensive and are built to support the language and infrastructure typical in the industrialized world. While the community of researchers in the Web Accessibility space have made significant strides, the operational concerns of networks in the developing world, as well as challenges in support for new languages and contexts raises a new set of challenges for technologists in this space. We discuss the state of various technologies in the context of the developing world and propose directions in scientific and community-contributed efforts to increase the relevance and access to AT and accessibility in the developing world.
Design and Implementation of Contextual Information Portals
This paper presents a system for enabling offline web use to satisfy the information needs of disconnected communities. We describe the design, implementation, evaluation, and pilot deployment of an automated mechanism to construct Contextual Information Portals (CIPs). CIPs are large searchable information repositories of web pages tailored to the information needs of a target population. We combine an efficient classifier with a focused crawler to gather the web pages for the portal for any given topic. Given a set of topics of interest, our system constructs a CIP containing the most relevant pages from the web across these topics. Using several secondary school course syllabi, we demonstrate the effectiveness of our system for constructing CIPs for use as an education resource. We evaluate our system across several metrics: classification accuracy, crawl scalability, crawl accuracy and harvest rate. We describe the utility and usability of our system based on a preliminary deployment study at an after-school program in India, and also outline our ongoing larger-scale pilot deployment at five schools in Kenya.
Identifying Enrichment Candidates in Textbooks
Many textbooks written in emerging countries lack clear and adequate coverage of important concepts. We propose a technological solution for algorithmically identifying those sections of a book that are not well written and could benefit from better exposition. We provide a decision model based on the syntactic complexity of writing and the dispersion of key concepts. The model parameters are learned using a tune set which is algorithmically generated using a versioned authoritative web resource as a proxy. We evaluate the proposed methodology over a corpus of Indian textbooks which demonstrates its effectiveness in identifying enrichment candidates.
Location Specific Summarization of Climatic and Agricultural Trends
Climate change can directly impact agriculture. Failure in different aspects of agriculture due to climate change and other influencing factors, are extremely rampant in several agrarian economies, most of which go unnoticed. In this paper, we describe the design of a system that mines disparate information sources on the Web to automatically summarize important climatic and agricultural trends for any specific location and construct a location-specific climatic and agricultural information portal. We have evaluated the system across 605 different districts in India. The results revealed a pan-India scenario of different problem affected areas. The key findings from this work include, around 64.58% of the districts of India suffer from soil related issues and 76.02% have water related problems. We have also manually validated the authenticity of our information sources and validated our summarized results for specific locations with findings in reputed journals and authoritative sources.
Low-Infrastructure Methods to Improve Internet Access for Mobile Users in Emerging Regions
As information technology supports more aspects of modern life, digital access has become an important tool for developing regions to lift themselves from poverty. Though broadband internet connectivity will not be universally available in the short-term, widely-employed mobile devices coupled with novel delay-tolerant networking do allow limited forms of connectivity. This paper explores the design space for internet access systems operating with constrained connectivity. Our starting point is C-LINK, a collaborative caching system that enhances the performance of interactive web access over DTN and cellular connectivity. We discuss our experiences and results from deploying C-LINK in Nicaragua, before moving on to a broader design study of other issues that further influence operation. We consider the impact of (i) storing web content collaboratively cached across all user nodes, (ii) hybrid transport layers exploiting the best attributes of limited cellular and DTN-style connectivity. We also explore the behavior of future systems under a range of usage and mobility scenarios. Even under adverse conditions, our techniques can improve average service latency for page requests by a factor of 2X. Our results point to the considerable power of leveraging user mobility and collaboration in providing very-low-infrastructure internet access to developing regions.
The Lwazi Community Communication Service: Design and Piloting of a Voice-Based Information Service
We present the design, development and pilot process of the Lwazi Community Communication Service (LCCS), a multilingual automated telephone-based information service. The service acts as a communication and dissemination tool that enables managers at local community centres to broadcast information (e.g. health, employment, social grants) to community workers and the communities they serve. The LCCS allows the recipients to obtain up-to-date, relevant information in a timely and efficient manner, overcoming the obstacles of transportation, time and costs incurred in trying to physically obtain information from the community centres. We discuss our experiences and fieldwork in piloting the LCCS at six locations nationally in the eleven official South African languages. We analyze the usage pattern from the pilot call logs and thereafter discuss the implications of these findings for future projects that design similar automated services for serving rural communities in developing world regions.
Traffic Characterization and Internet Usage in Rural Africa
While Internet connectivity has reached a significant part of the world's population, those living in rural areas of the developing world are still largely disconnected. Recent efforts have provided Internet connectivity to a growing number of remote locations, yet Internet traffic demands cause many of these networks to fail to deliver basic quality of service needed for simple applications. For an in-depth investigation of the problem, we gather and analyze network traces from a rural wireless network in Macha, Zambia. We supplement our analysis with on-site interviews from Macha, Zambia and Dwesa, South Africa, another rural community that hosts a local wireless network. The results reveal that Internet traffic in rural Africa differs significantly from the developed world. We observe dominance of web-based traffic, as opposed to peer-to-peer traffic common in urban areas. Application-wise, online social networks are the most popular, while the majority of bandwidth is consumed by large operating system updates. Our analysis also uncovers numerous network anomalies, such as significant malware traffic. Finally, we find a strong feedback loop between network performance and user behavior. Based on our findings, we conclude with a discussion of new directions in network design that take into account both technical and social factors.
Cooperative Anti-Spam System Based on Multilayer Agents
Spam is unsolicited bulk email which is extremely annoying to the recipients and the ISPs. However, most of the traditional spam filtering methods commonly neglect the bulk character of spam. This paper proposes a model of cooperative anti-spam system based on multilayer agents. We compared our model to the state-of-the-art and found that our model achieved better performance and robustness on several known corpora.
Measurement and Analysis of Cyberlocker Services
Cyberlocker Services (CLS) such as RapidShare and Megaupload have recently become popular. The decline of Peer-to-Peer (P2P) file sharing has prompted various services including CLS to replace it. We propose a comprehensive multi-level characterization of the CLS ecosystem. We answer three research questions: (a) what is a suitable measurement infrastructure for gathering CLS workloads; (b) what are the characteristics of the CLS ecosystem; and (c) what are the implications of CLS on Web 2.0 (and the Internet). To the best of our knowledge, this work is the first to characterize the CLS ecosystem. The work will highlight the content, usage, performance, infrastructure, quality of service, and evolution characteristics of CLS.
Towards Liquid Service Oriented Architectures
The advent of Cloud computing platforms, and the growing pervasiveness of Multicore processor architectures have revealed the inadequateness of traditional programming models based on sequential computations, opening up many challenges for research on parallel programming models for building distributed, service-oriented systems. More in detail, the dynamic nature of Cloud computing and its virtualized infrastructure pose new challenges in term of application design, deployment and dynamic reconfiguration. An application developed to be delivered as a service in the Cloud has to deal with poorly understood issues such as elasticity, infinite scalability and portability across heterogeneous virtualized environments. In this position paper we define the problem of providing a novel parallel programming model for building application services that can be transparently deployed on multicore and cloud execution environments. To this end, we introduce and motivate a research plan for the definition of a novel programming framework for Web service-based applications. Our vision called "Liquid Architecture" is based on a programming model inspired by core ideas tied to the REST architectural style coupled with a self-configuring runtime that allows transparent deployment of Web services on a broad range of heterogeneous platforms, from multicores to clouds.
Performance Enhancement of Scheduling Algorithms in Clusters and Grids Using Improved Dynamic Load Balancing Techniques
This paper describes the research work done for during PhD study. Cluster computing, grid computing and cloud computing are distributed computing environments (DCEs) widely accepted for the next generation Web based commercial and scientific applications. These applications work around the globally distributed data of petabyte scale that can only be processed by the aggregating the capability of globally distributed resources. The resource management and process scheduling in large scale distributed computing environment are a challenging task. In this research work we have devised new scheduling algorithms and resource management strategies specially designed for the cluster and grid cloud and peer-to-peer computing. The research work finally presented the distributed computing solutions to one scientific and one commercial application viz. e-Learning and data mining.
Computational Advertising: Leveraging User Interaction & Contextual Factors for Improved Ad Retrieval & Ranking
Computational advertising, popularly known as Online advertising or Web advertising, refers to finding the most relevant ads matching a particular context on the web. It is a scientific sub-discipline at the intersection of information retrieval, statistical modeling, machine learning, optimization, large scale search and text analysis. The core problem attacked in computational advertising (CA) is of the match making between the ads and the context. Based on the context, CA can be broadly compartmentalized into following three areas: Sponsored search, Contextual advertising and Social advertising. Sponsored search refers to the placement of ads on search results page. Contextual advertising deals with matching advertisements to the third party web pages. We refer the placements of ads on a social networking page, leveraging user's social contacts as social advertising. My research work aims at leveraging various user interactions, ad and advertiser related information and contextual information for these three areas of advertising. The research work focuses on the identification of various factors that contribute in retrieving and ranking the most relevant set of ads that match best with the context. Specifically, information associated with the user, publisher and advertiser is leveraged for this purpose.
Standing on the Shoulders of Ants: Stigmergy in the Web
Stigmergy is a biological term used when discussing insect or swarm behaviour, and describes a model supporting environmental communication separately from artefacts or agents. This phenomenon is demonstrated in the behavior of ants and their food gathering process when following pheromone trails, or similarly termites and their termite mound building process. What is interesting with this mechanism is that highly organized societies are achieved without an apparent management structure. Stigmergic behavior is implicit in the Web where the volume of users provides a self-organizing and self-contextualization of content in sites which facilitate collaboration. However, the majority of content is generated by a minority of the Web participants. A significant contribution from this research would be to create a model of Web stigmergy, identifying virtual pheromones and their importance in the collaborative process. This paper explores how exploiting stigmergy has the potential of providing a valuable mechanism for identifying and analyzing online user behavior recording actionable knowledge otherwise lost in the existing web interaction dynamics. Ultimately this might assist our building better collaborative Web sites.
Dynamic Learning-Based Mechanism Design for Dependent Valued Exchange Economies
Learning private information from multiple strategic agents poses challenge in many Internet applications. Sponsored search auctions, crowdsourcing, Amazon's mechanical turk, various online review forums are examples where we are interested in learning true values of the advertisers or true opinion of the reviewers. The common thread in these decision problems is that the optimal outcome depends on the private information of all the agents, while the decision of the outcome can be chosen only through reported information which may be manipulated by the strategic agents. The other important trait of these applications is their dynamic nature. The advertisers in an online auction or the users of mechanical turk arrive and depart, and when present, interact with the system repeatedly, giving the opportunity to learn their types. Dynamic mechanisms, which learn from the past interactions and make present decisions depending on the expected future evolution of the game, has been shown to improve performance over repeated versions of static mechanisms. In this paper, we will survey the past and current state-of-the-art dynamic mechanisms and analyze a new setting where the agents consist of buyers and sellers, known as exchange economies, and agents having value interdependency, which are relevant in applications illustrated through examples. We show that known results of dynamic mechanisms with independent value settings cannot guarantee certain desirable properties in this new significantly different setting. In the future work, we propose to analyze similar settings with dynamic types and population.
Fuzzy Associative Rule-Based Approach for Pattern Mining and Identification and Pattern-Based Classification
Associative Classification leverages Association Rule Mining (ARM) to train Rule-based classifiers. The classifiers are built on high quality Association Rules mined from the given dataset. Associative Classifiers are very accurate because Association Rules encapsulate all the dominant and statistically significant relationships between items in the dataset. They are also very robust as noise in the form of insignificant and low-frequency itemsets are eliminated during the mining and training stages. Moreover, the rules are easy-to-comprehend, thus making the classifier transparent. Conventional Associative Classification and Association Rule Mining (ARM) algorithms are inherently designed to work only with binary attributes, and expect any quantitative attributes to be converted to binary ones using ranges, like Age = [25, 60] . In order to mitigate this constraint, Fuzzy logic is used to convert quantitative attributes to fuzzy binary attributes, like Age = Middle-aged , so as to eliminate any loss of information arising due to sharp partitioning, especially at partition boundaries, and then generate Fuzzy Association Rules using an appropriate Fuzzy ARM algorithm. These Fuzzy Association Rules can then be used to train a Fuzzy Associative Classifier. In this paper, we also show how Fuzzy Associative Classifiers so built can be used in a wide variety of domains and datasets, like transactional datasets and image datasets.
Ranked Answer Graph Construction for Keyword Queries on RDF Graphs without Distance Neighbourhood Restriction
Abstract--- RDF and RDFS have recently become very popular as frameworks for representing data and meta-data in form of a domain description, respectively. RDF data can also be thought of as graph data. In this paper, we focus on keyword-based querying of RDF data. In the existing approaches for answering such keyword queries, keywords are mapped to nodes in the graph and their neighborhoods are explored to extract subgraph(s) of the data graph that contain(s) information relevant to the query. In order to restrict the computational effort, a fixed distance bound is used to define the neighborhoods of nodes. In this paper we present an elegant algorithm for keyword query processing on RDF data that does not assume such a fixed bound. The approach adopts a pruned exploration mechanism where closely related nodes are identified, subgraphs are pruned and joined using suitable hook nodes. The system dynamically manages the distance depending on the closeness between the keywords. The working of the algorithm is illustrated using a fragment of AIFB institute data represented as an RDF graph.
Application of Semantic Web Technologies for Multimedia Interpretation
Despite numerous outstanding results, highly complex and specialized multimedia algorithms have not been able to fulfill the promise of fully automated multimedia interpretation. An essential problem is that they are insufficiently aware of the context they operate in. Algorithms that do take a form of context in consideration, often function in a domain-specific environment. The generic framework proposed in this paper stimulates algorithm collaboration on an interpretation task by continuously actualizing the context of the multimedia item under interpretation. Semantic Web knowledge, combined with reasoning methods, forms the corner stone of the integration of these various interacting agents. We believe that this framework will enable an advanced interpretation of multimedia data that goes beyond the capabilities of individual algorithms. A basic platform implementation already indicates the potential of the concept, clearing the path for even more complex interpretation scenarios.
The world wide web provides access to a wealth of data. Collecting and maintaining such large amounts of data necessitates automated processing for extraction, since appropriate automation can perform extraction tasks that would be otherwise infeasible. Modern web interfaces, however, are generally designed primarily for human users, delivering sophisticated interactions through the use of client-side scripting and asynchronous server communication. To this end, we introduce OXPath, a careful extension of XPath that facilitates data extraction from the deep web. OXPath exploits XPath's familiarity and theoretical foundations. OXPath, then, achieves favourable evaluation complexity and optimal page buffering, storing only a constant number of pages for non-recursive queries. Further, OXPath provides a lightweight interface, which is easy to use and embed. This paper outlines the motivation, theoretical framework, current implementation, and preliminary results obtained so far. We conclude with proposed future work on OXPath, including an investigation of how to deploy OXPath efficiently in a highly elastic computing framework (cloud).
Analysis and Tracking of Emotions in English and Bengali Texts: A Computational Approach
The present discussion highlights the aspects of an ongoing doctoral thesis grounded on the analysis and tracking of emotions from English and Bengali texts. Development of lexical resources and corpora meets the preliminary urgencies. The research spectrum aims to identify the evaluative emotional expressions at word, phrase, sentence, and document level granularities along with their associated holders and topics. Tracking of emotions based on topic or event was carried out by employing sense based affect scoring techniques. The labeled emotion corpora are being prepared from unlabeled examples to cope with the scarcity of emotional resources, especially for the resource constraint language like Bengali. Different unsupervised, supervised and semi-supervised strategies, adopted for coloring each outline of the research spectrum produce satisfactory outcomes
A Politeness Recognition Tool for Hindi: With Special Emphasis on Online Texts
This paper gives an overview of a politeness recognition tool (PoRT) for Hindi that is currently under preparation. It describes the the kind of problems that need to be tackled with before developing the tool, the approach and the methodology that will be adopted for the development and testing of the tool, the current progress and the future plan to achieve this goal.
Sentence-Level Contextual Opinion Retrieval
Existing opinion retrieval techniques do not provide context-dependent relevant results. Most of the approaches used by state-of-the-art techniques are based on frequency of query terms, such that all documents containing query terms are retrieved, regardless of contextual relevance to the intent of the human seeking the opinion. However, in a particular opinionated document, words could occur in different contexts, yet meet the frequency attached to a certain opinion threshold, thus explicitly creating a bias in overall opinion retrieved. In this paper we propose a sentence-level contextual model for opinion retrieval using grammatical tree derivations and approval voting mechanism. Model evaluation performed between our contextual model, BM25, and language model shows that the model can be effective for contextual opinion retrieval such as faceted opinion retrieval.
Summarization of Archived and Shared Personal Photo Collections
The volume of personal photos hosted on photo archives and social sharing platforms has been increasing exponentially. It is difficult to get an overview of a large collection of personal photos without browsing though the entire database manually. In this research, we propose a framework to generate representative subset summaries from photo collections hosted on web archives or social networks. We define salient properties of an effective photo summary and model summarization as an optimization of these properties, given the size constraints. We also introduce metrics for evaluating photo summaries based on their information content and the ability to satisfy user's information needs. Our experiments show that our summarization framework performs better than baseline algorithms.
Wikipedia is an online encyclopedia that anyone can access and edit. It has become one of the most important sources of knowledge online and many third party projects rely on it for a wide-range of purposes. The open model of Wikipedia allows pranksters, lobbyists and spammers to attack the integrity of the encyclopedia and this endangers it as a public resource. This is known in the community as vandalism. A plethora of methods have been developed within the Wikipedia and the scientific community to tackle this problem. We have participated in this effort and developed one of the leading approaches. Our research aims to create a fully-working antivandalism system and get it working in the real world.
A Classification Based Framework for Concept Summarization
In this paper we propose a novel classification based framework for finding a small number of images summarizing a concept. Our method exploits metadata information available with the images to get the category information using Latent Dirichlet Allocation. We modify the import vector machine formulation based on kernel logistic regression to solve the underlying classification problem. We show that the import vectors provide a good summary satisfying important properties such as coverage, diversity and balance. Furthermore, the framework allows users to specify desired distributions over category, time etc, that a summary should satisfy. Experimental results show that the proposed method performs better than state-of-the-art summarization methods in terms of satisfying important visual and semantic properties.
A Feature-Pair-Based Associative Classification Approach to Look-Alike Modeling for Conversion-Oriented User-Targeting in Tail Campaigns
Online advertising offers significantly finer granularity, which has been leveraged in state-of-the-art targeting methods, like Behavioral Targeting (BT). Such methods have been further complemented by recent work in Look-alike Modeling (LAM) which helps in creating models which are customized according to each advertiser s requirements and each campaign s characteristics, and which show ads to users who are most likely to convert on them, not just click them. In Look-alike Modeling given data about converters and nonconverters, obtained from advertisers, we would like to train models automatically for each ad campaign. Such custom models would help target more users who are similar to the set of converters the advertiser provides. The advertisers get more freedom to define their preferred sets of users which should be used as a basis to build custom targeting models. In behavioral data, the number of conversions (positive class) per campaign is very small (conversions per impression for the advertisers in our data set are much less than 10e 4), giving rise to a highly skewed training dataset, which has most records pertaining to the negative class. Campaigns with very few conversions are called as tail campaigns, and those with many conversions are called head campaigns. Creation of Look-alike Models for tail campaigns is very challenging and tricky using popular classifiers like Linear SVM and GBDT, because of the very few number of positive class examples such campaigns contain. In this paper, we present an Associative Classification (AC) approach to LAM for tail campaigns. Pairs of features are used to derive rules to build a Rule-based Associative Classifier, with the rules being sorted by frequency-weighted log-likelihood ratio (F-LLR). The top k rules, sorted by F-LLR, are then applied to any test record to score it. Individual features can also form rules by themselves, though the number of such rules in the top k rules and the whole rule-set is very small. Our algorithm is based on Hadoop, and is thus very efficient in terms of speed.
A FineGrained Digestion of News Webpages Through Event Snippet Extraction
We describe a framework to digest news webpages in finer granularity: to extract event snippets from contexts. Events are atomic text snippets and a news article is constituted by more than one event snippet. Event Snippet Extraction (ESE) aims to mine these snippets out. The problem is important because its solutions may be applied to many information mining and retrieval tasks. The challenge is to exploit rich features to detect snippet boundaries, including various semantic, syntactic and visual features. We run experiments to present the effectiveness of our approaches.
A Framework for Evaluating Network Measures for Functional Importance
Many metrics such as degree, closeness, and PageRank have been introduced to determine the relative importance of a node within a network. The desired function of a network, however, is domain-specific. For example, the robustness can be crucial for a communication network, while efficiency is more preferred for fast spreading of advertisements in viral marketing. The information provided by some widely used measures are often conflicting under such varying demands. In this paper, we present a novel framework for evaluating network metrics regarding typical functional requirements. We also propose an analysis of five well established measures to compare their performance of ranking nodes on functional importance in a real-life network.
A Kernel Approach to Addressing Term Mismatch
This paper addresses the problem of dealing with term mismatch in web search using `blending'. In blending, the input query as well as queries similar to it are used to retrieve documents, the ranking results of documents with respect to the queries are combined to generate a new ranking list. We propose a principled approach to blending, using a kernel method and click-through data. Our approach consists of three elements: a way of calculating query similarity using click-through data, a mixture model for combination of rankings using relevance, query similarity, and document similarity scores, and an algorithm for learning the weights of blending model based on the kernel method. Large scale experiments on web search and enterprise search data sets show that our approach can effectively solve term mismatch problem and significantly outperform the baseline methods of query expansion and heuristic blending.
A Middleware for Securing Mobile Mashups
Mashups on traditional desktop devices are a well-known source of security risks. In this paper, we examine how these risks translate to mobile mashups and identify new risks caused by mobile-specific characteristics such as access to device features or offline operation. We describe the design of SCCM, a platform independent approach to handle the various mobile mashup security risks in a consistent and systematic manner. Evaluating an SCCM implementation for Android, we find that SCCM successfully protects against common attacks such as inserting a malicious widget from the outside.
A Non-Syntactic Approach for Text Sentiment Classification with Stopwords
The present approach uses stopwords and the gaps that occur between successive stopwords formed by contentwords as features for sentiment classification.
A Probabilistic Model for Opinionated Blog Feed Retrieval
In this poster, we study the problem of Opinionated Blog Feed Retrieval which can be considered as a particular type of the faceted blog distillation introduced by TREC 2009. It is a task of finding blogs not only having a principle and recurring interest in a given topic but also having a clear inclination towards expressing opinions on it. We propose a novel probabilistic model for this task which combines its two factors, topical relevance and opinionatedness, in a unified probabilistic framework. Experiments conducted in the context of the TREC 2009 & 2010 Blog Track show the effectiveness of the proposed model.
A Study on the Impact of Product Images on User Clicks for Online Shopping
In this paper we study the importance of image based features on the click-through rate (CTR) in the context of a large scale product search engine. Typically product search engines use text based features in their ranking function. We present a novel idea of using image based features, common in the photography literature, in addition to text based features. We used a stochastic gradient boosting based regression model to learn relationships between features and CTR. Our results indicate statistically significant correlations between the image features and CTR. We also see improvements to NDCG and mean standard regression.
Allocating Inverted Index into Flash Memory for Search Engines
Automatic Sanitization of Social Network Data to Prevent Inference Attacks
As the privacy concerns related to information release in social networks become a more mainstream concern, data owners will need to utilize a variety of privacy-preserving methods of examining this data. Here, we propose a method of data generalization that applies to social networks and present some initial findings for the utility/privacy tradeoff required for its use.
Casting a Web of Trust Over Wikipedia: An Interaction-Based Approach
We report in this short paper results on inferring a signed network (a "web of trust") from user interactions. On the Wikipedia network of contributors, from a collection of articles in the politics domain and their revision history, we investigate mechanisms by which relationships between contributors - in the form of signed directed links - can be inferred from their interactions. Our preliminary study provides valuable insight into principles underlying a signed network of Wikipedia contributors that is captured by social interaction. We look into whether this network (called hereafter WikiSigned) represents indeed a plausible configuration of link signs. We assess connections to social theories such as structural balance and status, which have already been considered in online communities. We also evaluate on this network the accuracy of a learned predictor for edge signs. Equipped with learning techniques that have been applied before on three explicit signed networks, we obtain good accuracy over the WikiSigned edges. Moreover, by cross training-testing we obtain strong evidence that our network does reveal an implicit signed configuration and that it has similar characteristics to the explicit ones, even though it is inferred from interactions. We also report on an application of the resulting signed network that impacts Wikipedia readers, namely the classification of Wikipedia articles by importance and quality.
CELF++: Optimizing the Greedy Algorithm for Influence Maximization in Social Networks
Kempe et al. (KKT) showed the problem of influence maximization is NP-hard and a simple greedy algorithm guarantees the best possible approximation factor in PTIME. However, it has two major sources of inefficiency. First, finding the expected spread of a node set is #P-hard. Second, the basic greedy algorithm is quadratic in the number of nodes. The first source is tackled by estimating the spread using Monte Carlo simulation or by using heuristics. Leskovec et al. proposed the CELF algorithm for tackling the second. In this work, we propose CELF++ and empirically show that it is 35-55% faster than CELF.
Comparative Study of Clustering Techniques for Short Text Documents
We compare various document clustering techniques including K-means, SVD-based method and a graph-based approach and their performance on short text data collected from Twitter. We define a measure for evaluating the cluster error with these techniques. Observations show that graph-based approach using affinity propagation performs best in clustering short text data with minimal cluster error.
Coverage Patterns for Efficient Banner Advertisement Placement
In an online banner advertising scenario, an advertiser expects that the banner advertisement should be displayed to certain percentage of web site visitors. In this context, to generate more revenue for a given web site, the publisher has to meet the demands of several advertisers by providing appropriate sets of web pages. To help the publishers and advertisers, in this paper, we propose a model of coverage patterns and a methodology to extract potential coverage patterns by analyzing click stream data. Given web pages of a site, a coverage pattern is a set of web pages visited by a certain percentage of visitors. The proposed approach has the potential to enable the publisher in meeting the demands of several advertisers. The efficiency and advantages of the proposed approach is shown by conducting experiments on real world data sets.
It is well-known that many online reviews are not written by genuine users of products, but by spammers who write fake reviews to promote or demote some target products. Although some existing works have been done to detect fake reviews and individual spammers, to our knowledge, no work has been done on detecting spammer groups. This paper focuses on this task and proposes an effective technique to detect such groups.
Domain-Independent Entity Extraction from Web Search Query Logs
Query logs of a Web search engine have been increasingly used as a vital source for data mining. This paper presents a study on large-scale domain-independent entity extraction from search query logs. We present a completely unsupervised method to extract entities by applying pattern-based heuristics and statistical measures. We compare against existing techniques that use Web documents as well as search logs, and show that we improve over the state of the art. We also provide an in-depth qualitative analysis outlining differences and commonalities between these methods.
Effective Summarization of Large Collections of Personal Photos
Efficient Diversification of Search Results Using Query Logs
We study the problem of diversifying search results by exploiting the knowledge mined from query logs. Our proposal exploits the presence of different "specializations" of queries in query logs to detect the submission of ambiguous/faceted queries, and manage them by diversifying the search results returned in order to cover the different possible interpretations of the query. We present an original formulation of the results diversification problem in terms of an objective function to be maximized that admits the finding of an optimal solution in linear time.
EntityTagger: Automatically Tagging Entities with Descriptive Phrases
We consider the problem of entity tagging: given one or more named entities from a specific domain, the goal is to automatically associate descriptive phrases, referred to as etags (entity tags), to each entity. Consider a product catalog containing product names and possibly short descriptions. For a product in the catalog, say Ricoh G600 Digital Camera, we want to associate etags such as ``water resistant'', ``rugged'' and ``outdoor'' to it, even though its name or description does not mention those phrases. Entity tagging can enable more effective search over entities. We propose to leverage signals in web documents to perform such tagging. We develop techniques to perform such tagging in a domain independent manner while ensuring high precision and high recall.
Evaluation of Valuable User Generated Content on Social News Web Sites
Social news websites have gained significant popularity in the last few years. The participants of such websites are not only allowed to share news links but also to annotate, to evaluate and to comment them. To quantify interestingness and attractiveness of the user-generated content in respect to the original link source we introduce the User Generated Content add-on (UGC_+) index. Based on the definition of UGC_+ we also propose a concept for comparing groups of links filtered by different properties, e.g. authorship or topic-categories. We apply the proposed measure on the Spanish Digg-clone MenÈame.
Extracting Events and Event Descriptions from Twitter
This paper describes methods for automatically detecting events involving known entities from Twitter and understanding both the events as well as the audience reaction to them. We show that NLP techniques can be used to extract events, their main actors and the audience reactions with encouraging results.
Finding Influential Mediators in Social Networks
Given a social network, who are the key players controlling the bottlenecks of influence propagation if some persons would like to activate specific individuals? In this paper, we tackle the problem of selecting a set of k mediator nodes as the influential gateways whose existence determines the activation probabilities of targeted nodes from some given seed nodes. We formally define the k-Mediators problem. To have an effective and efficient solution, we propose a three-step greedy method by considering the probabilistic influence and the structural connectivity on the pathways from sources to targets. To the best of our knowledge, this is the first work to consider the k-Mediators problem in networks. Experiments on the DBLP co-authorship graph show the effectiveness and efficiency of the proposed method.
Finding Our Way on the Web: Exploring the Role of Waypoints in Search Interaction
Information needs are rarely satisfied directly on search engine result pages. Searchers usually need to click through to search results (landing pages) and follow search trails beyond those pages to fulfill information needs. We use the term waypoints to describe pages visited by searchers between the trail origin (the landing page) and the trail destination. The role that waypoints play in search interaction is poorly understood yet can be vital in determining search success. In this poster we analyze log data to determine the arrangement and function of waypoints, and study how these are affected by variations in information goals. Our findings have implications for understanding search behavior and for the design of interactive search support based on waypoints.
Once information retrieval has located a document, and information extraction has provided its contents, how do we know whether we should actually believe it? Fact-finders are a state-of-the-art class of algorithms that operate in a manner analogous to Kleinberg's Hubs and Authorities, iteratively computing the trustworthiness of an information source as a function of the believability of the claims it makes, and the believability of a claim as a function of the trustworthiness of those sources asserting it. However, as fact-finders consider only ``who claims what", they ignore a great deal of relevant background and contextual information. We present a framework for ``lifting" (generalizing) the fact-finding process, allowing us to elegantly incorporate knowledge such as the confidence of the information extractor and the attributes of the information sources. Experiments demonstrate that leveraging this information significantly improves performance over existing, ``unlifted" fact-finding algorithms.
GeoVisualRank: A Ranking Method of Geotagged Images Considering Visual Similarity and Geo-Location Proximity
Growing Parallel Paths for Entity-Page Discovery
In this paper, we use the structural and relational information on the Web to find entity-pages. Specifically, given a Web site and an entity-page (e.g., department and faculty member homepage) we seek to find all of the entity-pages of the same type (e.g., all faculty members in the department). To do this, we propose a web structure mining method which grows parallel paths through the web graph and DOM trees. We show that by utilizing these parallel paths we can efficiently discover all entity-pages of the same type. Finally, we demonstrate the accuracy of our method with a case study on various domains.
Hierarchical Organization of Unstructured Consumer Reviews
In this paper, we propose to organize the aspects of a specific product into a hierarchy by simultaneously taking advantages of domain structure knowledge as well as consumer reviews. Based on the derived hierarchy, we generate a hierarchical organization of the consumer reviews based on various aspects of the product, and aggregate consumer opinions on the aspects. With such hierarchical organization, people can easily grasp the overview of consumer reviews and opinions on various aspects, as well as seek consumer reviews and opinions on any specific aspect by navigating through the hierarchy. We conduct evaluation on two product review data sets: Liu et al.'s data set containing 314 reviews for five products, and our review corpus which is collected from forum Web sites containing 60,786 reviews for five popular products. The experimental results demonstrate the effectiveness of our approach.
How to Choose Combinations in a Join of Search Results
We present novel measures for estimating the effectiveness of duplication-removal operations over a join of ranked lists. We introduce a duplication-removal approach, namely optimality rank, that outperforms existing approaches, according to the new measures.
HyLiEn: A Hybrid Approach to General List Extraction on the Web
We consider the problem of automatically extracting general lists from the web. Existing approaches are mostly depen- dent upon either the underlying HTML markup or the visual structure of the Web page. We present HyLiEn an un- supervised, Hybrid approach for automatic List discovery and Extraction on the Web. It employs general assump- tions about the visual rendering of lists, and the structural representation of items contained in them. We show that our method significantly outperforms existing methods.
Hypergraph-Based Inductive Learning for Generating Implicit Key Phrases
This paper presents a novel approach to generate implicit key phrases which are ignored in previous researches. Recent researches prefer to extract key phrases with semi-supervised transductive learning methods, which avoid the problem of training data. In this paper, based on a transductive learning method, we formulate the phrases in the document as a hypergraph and expand the hypergraph to include implicit phrases, which are ranked by an inductive learning approach. The highest ranked phrases are seen as implicit key phrases, and experimental results demonstrate the satisfactory performance of this approach.
Identifying Overlapping Communities in Folksonomies or Tripartite Hypergraphs
Online folksonomies are modeled as tripartite hypergraphs, and detecting communities from such networks is a challenging and well-studied problem. However, almost every existing algorithm known to us for community detection in hypergraphs assign unique communities to nodes, whereas in reality, nodes in folksonomies belong to multiple overlapping communities e.g. users have multiple topical interests, and the same resource is often tagged with semantically different tags. In this paper, we propose an algorithm to detect overlapping communities in folksonomies by customizing a recently proposed edge-clustering algorithm (that is originally for traditional graphs) for use on hypergraphs.
Identifying Primary Content From Web Pages and Its Application to Web Search Ranking
Web pages are usually highly structured documents. In some documents, content with different functionality is laid out in blocks, some merely supporting the main discourse. In other documents, there may be several blocks of unrelated main content. Indexing a web page as if it were a linear document can cause problems because of the diverse nature of its content. If the retrieval function treats all blocks of the web page equally without attention to structure, it may lead to irrelevant query matches. In this paper, we describe how content quality of different blocks of a web page can be utilized to improve a retrieval function. Our method is based on segmenting a web page into semantically coherent blocks and learning a predictor of segment content quality. We also describe how to use segment content quality estimates as weights in the BM25F formulation. Experimental results show our method improves relevance of retrieved results by as much as 4.5% compared to BM25F that treats the body of a web page as a single section, and by a larger margin of over 9% for difficult queries.
The ever-increasing amount of information flowing through Social Media forces the members of these networks to compete for attention and influence by relying on other people to spread their message. A large study of information propagation within Twitter reveals that the majority of users act as passive information consumers and do not forward the content to the network. Therefore, in order for individuals to become influential they must not only obtain attention and thus be popular, but also overcome user passivity. We propose an algorithm that determines the influence and passivity of users based on their information forwarding activity. An evaluation performed with a 2.5 million user dataset shows that our influence measure is a good predictor of URL clicks, outperforming several other measures that do not explicitly take user passivity into account. We demonstrate that high popularity does not necessarily imply high influence and vice-versa.
Investigating Topic Models for Social Media User Recommendation
This paper presents a user recommendation system that recommends to a user new friends having similar interests. We automatically discover users interests using Latent Dirichlet Allocation (LDA), a linguistic topic model that represents users as mixtures of topics. Our system is able to recommend friends for 4 million users with high recall, outperforming existing strategies based on graph analysis.
Language Independent Identification of Parallel Sentences Using Wikipedia
This paper details a novel classification based approach to identify parallel sentences between two languages in a language independent way. We substitute the required language specific resources by the richly structured multilingual content, Wikipedia. Our approach is particularly useful to extract parallel sentences for under-resourced languages like most Indian and African languages, where resources are not readily available with necessary accuracies. We extract various statistics based on the cross lingual links present in Wikipedia and use them to generate feature vectors for each sentence pair. Binary classification of each pair of sentences into parallel or non-parallel has been done using these feature vectors. We achieved a precision upto 78% which is encouraging when compared to other state-of-art approaches.These results support our hypothesis of using Wikipedia to evaluate the parallel coefficient between sentences that can be used to build bilingual dictionaries.
Learning Facial Attributes by Crowdsourcing in Social Media
Facial attributes such as gender, race, age, hair style, etc., carry rich information for locating designated persons and pro ling the communities from image/video collections (e.g., surveillance videos or photo albums). For plentiful facial attributes in photos and videos, collecting costly manual annotations for training detectors is time-consuming. We propose an automatic facial attribute detection method by exploiting the great amount of weakly labelled photos in social media. Our work can (1) automatically extract training images from the semantic-consistent user groups and (2) filter out noisy training photos by multiple mid-level features (by voting). Moreover, we introduce a method to harvest less-biased negative data for preventing uneven distribution of certain attributes. The experiments show that our approach can automatically acquire training photos for facial attributes and is on par with that by manual annotations.
Domain Match is an Internet monetization product offered by web companies like Yahoo! The product offers display of ads and search results, when a user requests a webpage from a domain which is non-existent or does not have any content. This product earns significant amount of advertising revenue for major internet companies like Yahoo! Hence it is an important product receiving millions of queries per day. Domain Match (DM) works by tokenizing the input domains and sub-folders into keywords and then displaying ads and search results queried on the keywords. In this poster, we describe a machine learning based solution, which automatically learns to tokenize new domains, given a training dataset containing a set of domains and their tokenizations. We use positional frequency and parts of speech as features for scoring tokens. Tokens are scored combined using various scoring models. We compare two ways of training the models: a simple gain function based training and a large margin training. Experimental results are encouraging.
Leveraging Auxiliary Text Terms for Automatic Image Annotation
This paper proposes a novel algorithm to annotate web images by automatically aligning the images with their most relevant auxiliary text terms. First, the DOM-based web page segmentation is performed to extract images and their most relevant auxiliary text blocks. Second, automatic image clustering is used to partition the web images into a set of groups according to their visual similarity contexts, which significantly reduces the uncertainty on the relatedness between the images and their auxiliary terms. The semantics of the visually-similar images in the same cluster are then described by the same ranked list of terms which frequently co-occur in their text blocks. Finally, a relevance re-ranking process is performed over a term correlation network to further refine the ranked term list. Our experiments on a large-scale database of web pages have provided very positive results.
Location Relevance Classification for Travelogue Digests
In this paper, we aim to develop a travelogue service to discover and convey various travelogue digests, in form of theme locations and geographical scope to their readers. In this service, theme locations in a travelogue are the core information to discover. Due to the inherent ambiguity of location relevance, we explore the textual (e.g., surrounding words) and geographical (e.g., geographical relationship among locations) features of locations to perform location relevance classification for theme location discovery. Finally, we conduct comprehensive experiments on collected travelogues to evaluate the performance of our location relevance classification technique and demonstrate the effectiveness of the travelogue service.
Measuring the Effectiveness of Display Advertising: A Time Series Approach
We develop an approach for measuring the effectiveness of online display advertising at the campaign level. We present a Kalman filtering approach to deseasonalize and estimate the percentage changes of online sales on a daily basis. For this study, we analyze 3828 campaigns for 961 products on the Advertising.com network.
Mining Collective Local Knowledge from Google MyMaps
The emerging popularity of location-aware devices and location-based services has generated a growing archive of digital traces of people's activities and opinions in physical space. In this study, we leverage geo-referenced user-generated content from Google MyMaps to discover collective local knowledge and understand the differing perceptions of urban space. Working with the large collection of publicly available, annotation-rich MyMaps data, we propose a highly parallelizable approach in order to merge identical places, discover landmarks, and recommend places. Additionally, we conduct interviews with New York City residents/visitors to validate the quantitative findings.
Mobile Search Pattern Evolution: The Trend and the Impact of Voice Queries
In this paper we study the characteristics of search queries submitted from mobile devices using Yahoo! Search for Mobile during a 2 months period in early of 2010, and compare the results with a similar study conducted in late 2007. The major findings include 1) mobile search queries have become much more diverse, and 2) user interest and information needs have been substantially changed at least in some areas of search topics, including adult and local intent queries. In addition we investigate the impact of voice query search interface offered by Yahoo!'s mobile search service. We examine how unstructured spoken queries differ from conventional search queries.
Mobile Topigraphy: Large-Scale Tag Cloud Visualization for Mobiles
We introduce a new mobile topigraphy system that uses the contour map metaphor to display large-scale tag clouds. We introduce the technical issues for topigraphy, and recent requirements for and developments in mobile interfaces. We also present some applications for our mobile topigraphy system and describe the assessment on two initial applications.
Networked Hierarchies for Web Directories
The hierarchical nature of existing Web directories, ontologies, and folksonomies, are known to provide meaningful information that guide users and applications. We hypothesize that such hierarchical structures provide richer information if they are further enriched by incorporating additional links besides parents, and siblings, namely, between non-sibling nodes. We call such structure a networked hierarchy. Our empirical results indicate that such a networked hierarchy introduces interesting links between nodes (non-sibling) that otherwise in a hierarchical structure are not evident.
On Using the Real-Time Web for News Recommendation & Discovery
In this work we propose that the high volumes of data on real-time networks like Twitter can be harnessed as a useful source of recommendation knowledge. We describe Buzzer, a news recommendation system that is capable of adapting to the conversations that are taking place on Twitter. Buzzer uses a content-based approach to ranking RSS news stories by mining trending terms from both the public Twitter timeline and from the timeline of tweets generated by a user's own social graph (friends and followers). We also describe the result of a live-user trial which demonstrates how these ranking strategies can add value to conventional RSS ranking techniques, which are largely recency-based.
Open and Decentralized Access Across Location-Based Services
Users now interact with multiple Location-Based Services (LBS) through a myriad set of location-aware devices and interfaces. However, current LBS tend to be centralized silos with ad-hoc APIs, which limits potential for information sharing and reuse. Further, LBS subscriptions and user experiences are not easily portable across devices. We propose a general architecture for providing open and decentralized access to LBS, based on Tiled Feeds - a RESTful protocol for access and interactions with LBS using feeds, and Feed Subscription Management (FSM) - a generalized feed-based service management protocol. We describe two client designs, and demonstrate how they enable standardized access to LBS services, promote information sharing and mashup creation, and offer service management across various types of location-enabled devices.
Personalized Search on Flickr Based on Searcher's Preference Prediction
In this paper, we propose a personalized search model to assist users in obtaining interested photos on Flickr, which exploits the favorite marks of the searcher s friends to predict the searcher s preference on the returned photos. The proposed model utilizes a co-clustering method to extract latent interest dimensions from users implicit interests, and employs a discriminative learning method to predict searcher s preference on the returned photos. Preliminary experiments demonstrate the improvement of the proposed model compared to existing one-fit-all methods and a user-based collaborative filtering method.
Query Completion without Query Logs for Song Search
We describe a new method for query completion for Bollywood song search without using query logs. Since song titles in non-English languages (Hindi in our case) are mostly present as Roman transliterations of the native script, both the queries and documents have a large number of valid variations. We address this problem by using a Roman to Hindi transliteration engine coupled with appropriate ranking and implementation strategies. Out of 100 test cases, our system could generate the correct suggestion for 91 queries.
Ranking in Context-Aware Recommender Systems
As context is acknowledged as an important factor that can affect users' preferences, many researchers have worked on improving the quality of recommender systems by utilizing users' context. However, incorporating context into recommender systems is not a simple task in that context can influence users' item preferences in various ways depending on the application. In this paper, we propose a novel method for context-aware recommendation, which incorporates several features into the ranking model. By decomposing a query, we propose several types of ranking features that reflect various contextual effects. In addition, we present a retrieval model for using these features, and adopt a learning to rank framework for combining proposed features. We evaluate our approach on two real-world datasets, and the experimental results show that our approach outperforms several baseline methods.
Ranking Related Entities for Web Search Queries
Entity ranking is a recent paradigm that refers to retrieving and ranking related objects and entities from different structured sources in various scenarios. Entities typically have associated categories and relationships with other entities. In this work, we present an extensive analysis of Web-scale entity ranking, based on machine learned ranking models using an ensemble of pairwise preference models. Our proposed system for entity ranking uses structured knowledge bases, entity relationship graphs and user data to derive useful features to facilitate semantic search with entities directly within the learning to rank framework. The experimental results are validated on a large-scale graph containing millions of entities and hundreds of millions of entity relationships. We show that our proposed ranking solution clearly improves a simple user behavior based ranking model.
ReadAlong: Reading Articles and Comments Together
We propose a new paradigm for displaying comments: showing comments alongside parts of the article they correspond to. We evaluate the effectiveness of various approaches for this task and show that a combination of bag of words and topic models performs the best.
Recommendations for the Long Tail by Term-Query Graph
We define a new approach to the query recommendation problem. In particular, our main goal is to design a model enabling the generation of query suggestions also for rare and previously unseen queries. In other words we are targeting queries in the long tail. The model is based on a graph having two sets of nodes: Term nodes, and Query nodes. The graph induces a Markov chain on which a generic random walker starts from a subset of Term nodes, moves along Query nodes, and restarts (with a given probability) only from the same initial subset of Term nodes. Computing the stationary distribution of such a Markov chain is equivalent to extracting the so-called Center-piece Subgraph from the graph associated with the Markov chain itself. Given a query, we extract its terms and we set the restart subset to this term set. Therefore, we do not require a query to have been previously observed for the recommending model to be able to generate suggestions.
Rolling Boles, Optimal XML Structure Integrity for Updating Operations
While multiple techniques exist to utilize the tree structure of the Extensible Markup Language(XML) regarding integrity checks, they all rely on adaptions of the Merkle Tree: All children are acting as one slice regarding the check-sum of one node with the help of an one-way hash concatenation. This results in postorder traversals regarding the (re-)computation of the integrity structure within modification operations. With our approach we perform nearly in-time updates of the entire integrity structure. We therefore equipped an XHash-based approach with an incremental hash function. This replaces postorder traversals by adapting only the incremental modifications to the check-sums of a node and its ancestors. With experimental results we prove that our approach only generates a constant overhead depending on the depth of the tree while native DOMHash implementations produce an overhead based on the depth and the number of all nodes in the tree. Consequently, our approach called Rolling Boles generates sustainable impact since it facilitates instant integrity updates in constant time.
Scalable Spatio-Temporal Knowledge Harvesting
Knowledge harvesting enables the automated construction of large knowledge bases. In this work, we made a first attempt to harvest spatio-temporal knowledge from news archives to construct trajectories of individual entities for spatio-temporal entity tracking. Our approach consists of an entity extraction and disambiguation module and a fact generation module which produce pertinent trajectory records from textual sources. The evaluation on the 20 years' New York Times news article corpus showed that our methods are effective and scalable.
Smart News Feeds for Social Networks Using Scalable Joint Latent Factor Models
Social networks such as Facebook and Twitter offer a huge opportunity to tap the collective wisdom (both published and yet to be published) of all the participating users in order to address the information needs of individual users in a highly contextualized fashion using rich user-specific information. Realizing this opportunity, however, requires addressing two key limitations of current social networks: (a) difficulty in discovering relevant content beyond the immediate neighborhood, (b) lack of support for information filtering based on semantics, content source and linkage. We propose a scalable framework for constructing smart news feeds based on predicting user-post relevance using multiple signals such as text content and attributes of users and posts, and various user-user, post-post and user-post relations (e.g. friend, comment, author relations). Our solution comprises of two steps where the first step ensures scalability by selecting a small set of user-post dyads with potentially interesting interactions using inverted feature indexes. The second step models the interactions associated with the selected dyads via a joint latent factor model, which assumes that the user/post content and relationships can be effectively captured by a common latent representation of the users and posts. Experiments on a Facebook dataset using the proposed model lead to improved precision/recall on relevant posts indicating potential for constructing superior quality news feeds.
SmartInt: Using Mined Attribute Dependencies to Integrate Fragmented Web Databases
Many web databases can be seen as providing partial and overlapping information about entities in the world. To answer queries effectively, we need to integrate the information about the individual entities that are fragmented over multiple sources. At first blush this is just the inverse of traditional database normalization problem - rather than go from a universal relation to normalized tables, we want to reconstruct the universal relation given the tables (sources). The standard way of reconstructing the entities will involve joining the tables. Unfortunately, because of the autonomous and decentralized way in which the sources are populated, they often do not have Primary Key - Foreign Key relations. While tables do share attributes, direct joins over these shared attributes can result in reconstruction of many spurious entities thus seriously compromising precision. We present a unified approach that supports intelligent retrieval over fragmented web databases by mining and using inter-table dependencies. Experiments with the prototype implementation, SmartInt, show that its retrieval strikes a good balance between precision and recall.
Spammers' Networks Within Online Social Networks: A Case-Study on Twitter
We analyze the strategies employed by contemporary spammers in Online Social Networks (OSNs) by identifying a set of spam-accounts in Twitter and monitoring their link-creation strategies. Our analysis reveals that spammers adopt intelligent `collaborative' strategies of link-formation to avoid detection and to increase the reach of their generated spam, such as forming `spam-farms' and creating large number of links with targeted legitimate users. The observations are verified through the analysis of a giant `spam-farm' embedded within the Twitter OSN.
Survivability-Oriented Self-Tuning of Web Systems
Running in a highly uncertain and changing environment, Web systems cannot always provide full set of services with optim¨al quality, especially when the workload is high or failures in subsys-tems occur frequently. It is thus desirable to continuously maintain a high satisfaction level of the system value proposition, hereafter survivability assurance, while relaxing/sacrificing certain quality/functional requirements that are not crucial to the survival of the Web systems. In this paper, we propose a requirements-driven self-tuning method for survivability assurance of Web systems. Using a value-based feedback controller plus a requirements-oriented reasoner, our method makes both quality and functional requirements tradeoffs decisions at runtime.
The Freshman Handbook: A Hint for the Server Placement of Social Networks
There has been a recent unprecedented increase in the use of Online Social Networks (OSNs) to expand our social life, exchange information and share common interests. Many popular OSNs today attract hundreds of millions of users who share tremendous amount of data on it such as Facebook, Twitter, and Buzz. Given the huge business opportunities OSNs may bring, more and more new social applications has emerged on the Internet. For these newcomers in the social network business, one of the first key decisions to make is to where to deploy the computational resources to best accommodate future client requests. In this work, we aim at providing useful suggests to the new born social network providers (freshman) on the intelligent server placement, by exploring available public information from existing social network communities. In this work, we first propose three scalable server placement strategies for OSNs. Our solution can scalably select server locations among all the possible locations, at the same time reducing the cost for inter-user data sharing.
Timestamp-Based Cache Invalidation for Search Engines
We propose a new mechanism to predict stale queries in the result cache of a search engine. The novelty of our approach is in the use of timestamps in staleness predictions. We show that our approach incurs very little overhead on the system while its prediction accuracy is comparable to earlier works.
Toward Optimal Vaccination Strategies for Probabilistic Models
Epidemic outbreaks such as the recent H1N1 influenza show how susceptible large communities are toward the spread of such outbreaks. The occurrence of a widespread disease transmission raises the question of vaccination strategies that are appropriate and close to optimal. The seemingly different problem of viruses disseminating through email networks, shares a common structure with disease epidemics. While it is not possible to vaccinate every individual during a virus outbreak, due to economic and logistical constraints, fortunately, we can leverage the structure and properties of face-to-face social networks to identify individuals whose vaccination would result in a lower number of infected people. The models that have been studied so far assume that once an individual is infected all its adjacent individuals would be infected with probability 1. However, this assumption is not realistic. In reality, if an individual is infected by a virus, the neighboring individuals would get infected with some probability (depending on the type of the disease and the contact). This modification to the model makes the problem more challenging as the simple version is already NP-complete. Here we consider the following epidemiological model computationally: A number of individuals in the community get vaccinated which makes them immune to the disease. The disease then outbreaks and a number of nodes that are not vaccinated get infected at random. These nodes can transmit the infection to their friends with some probability. In this work we consider the optimization problem in which the number of nodes that get vaccinated is limited to k and our objective is to minimize the number of infected people overall. We design various algorithms that take into account the properties of social networks to select k nodes for vaccination in order to achieve the goal. We perform experiments on a real dataset of 34,546 vertices and 421,578 edges and assess their effectiveness and scalability.
Towards Automatic Quality Assurance in Wikipedia
Featured articles in Wikipedia stand for high information quality, and it has been found interesting to researchers to analyze whether and how they can be distinguished from "ordinary" articles. Here we point out that article discrimination falls far short of writer support or automatic quality assurance: Featured articles are not identified, but are made. Following this motto we compile a comprehensive list of information quality flaws in Wikipedia, model them according to the latest state of the art, and devise one-class classification technology for their identification.
Towards Identifying Arguments in Wikipedia Pages
Wikipedia is one of the most widely used repositories of human knowledge today, contributed mostly by a few hundred thousand regular editors. In this open environment, inevitably, differences of opinion arise among editors of the same article. Especially for polemical topics such as religion and politics, difference of opinions among editors may lead to intense edit wars in which editors compete to have their opinions and points of view accepted. While such disputes can compromise the reliability of the article (or at least portions of it), they are recorded in the edit history of the articles. We posit that exposing such disputes to the reader, and pointing to the portions of the text where they manifest most prominently can be beneficial in helping concerned readers in understanding such topics. In this paper, we discuss our initial efforts towards the problem of automatic evaluation of extracting controversial points in Wikipedia pages.
Web provides rich information about a variety of objects. Trustability is a major concern on the web. Truth establishment is an important task so as to provide the right information to the user from the most trustworthy source. Trustworthiness of information provider and the confidence of the facts it provides are inter-dependent on each other and hence can be expressed iteratively in terms of each other. However, a single information provider may not be the most trustworthy for all kinds of information. Every information provider has its own area of competence where it can perform better than others. We derive a model that can evaluate trustability on objects and information providers based on clusters (groups). We propose a method which groups the set of objects for which similar set of providers provide "good" facts, and provides better accuracy in addition to high quality object clusters.
Understanding the Functions of Business Accounts on Twitter
This paper performs an initial exploration of business Twitter accounts in order to start understanding how businesses interact with their users and viceversa. We provide an analysis of business tweet types and topics and show that specific business tweet classes such as deals and events can be reliably identi ed for customer use.
Unsupervised Query Segmentation Using Only Query Logs
We introduce an unsupervised query segmentation scheme that uses query logs as the only resource and can effectively capture the structural units in queries. We believe that Web search queries have a unique syntactic structure which is distinct from that of English or a bag-of-words model. The segments discovered by our scheme help understand this underlying grammatical structure. We apply a statistical model based on Hoeffding s Inequality to mine significant word n-grams from queries and subsequently use them for segmenting the queries. Evaluation against manually segmented queries shows that this technique can detect rare units that are missed by our Pointwise Mutual Information (PMI) baseline.
Using Complex Network Features for Fast Clustering in the Web
Applying graph clustering algorithms in real world networks needs to overcome two main challenges: the lack of prior knowledge and the scalability issue. This paper proposes a novel method based on the topological features of complex networks to optimize the clustering algorithms in real-world networks. More specifically, the features are used for parameter estimation and performance optimization. The proposed method is evaluated on real-world networks extracted from the web. Experimental results show improvement both in terms of Adjusted Rand index values as well as runtime efficiency.
Web Information Extraction Using Markov Logic Networks
In this paper, we consider the problem of extracting structured data from web pages taking into account both the content of individual attributes as well as the structure of pages and sites. We use Markov Logic Networks (MLNs) to capture both content and structural features in a single unified framework, and this enables us to perform more accurate inference. We show that inference in our information extraction scenario reduces to solving an instance of the maximum weight subgraph problem. We develop specialized procedures for solving the maximum subgraph variants that are far more efficient than previously proposed inference methods for MLNs that solve variants of MAX-SAT. Experiments with real-life datasets demonstrate the effectiveness of our approach.
Web-Scale Entity-Relation Search Architecture
Enabling entity search and ranking at Web-scale is fraught with many challenges: annotating the corpus with entities and types, query language design, index design, query processing logic, and answer consolidation. We describe a Web-scale entity search engine we are building to handle over a billion Web pages, over 200,000 types, over 1,500,000 entities, and hundreds of entity annotations per page. We describe the design of compressed, token span oriented indices for entity and type annotations. Our prototype demonstrates the practicality of Web-scale entity-relation search.
WonderWhat: Real-Time Event Determination from Photos
How often did you feel disappointed in a foreign country, when you had been craving for participating in authentic native events but miserably ended up with being lost in the crowd, due to ignorance of the local culture? Have you ever imagined that with merely a simple click, a tool can identify the events that are right in front of you? As a step in this direction, in this paper, we propose a system that provides users with information of the public events that they are attending by analyzing in real time their photos taken at the event, leveraging both spatio-temporal context and photo content. To fulfill the task, we designed the system to collect event information, maintain dedicated event database, build photo content model for event types, and rank the final results. Extensive experiments were conducted to prove the effectiveness of each component.
Hong Kong University of Science and Technology
University of Illinois at Urbana-Champaign
Technion - Israel Institute of Technology
Graz University of Technology and Know-Center Graz
Universidad Técnica Federico Santa María
Ecole Polytechnique Fédérale de Lausanne
International Institute of Information Technology, Hyderabad
Laboratoire PRiSM Université de Versailles
IBM T.J. Watson Research Center & University of Toronto
Polytechnic Institute of New York University
University of North Carolina, Greensboro
CSIR Meraka Institute & North-West University
International Institute of Information Technology
National Institute of Advanced Industrial Science and Technology
The University of Electro-Communications, Tokyo
Indian Institute of Technology Kharagpur
École Polytechnique Fédérale de Lausanne
University of North Carolina at Charlotte
Institute of Automation, Chinese Academy of Sciences
National Laboratory for Parallel and Distributed Processing
National University of Defense Technology