waashk/dblp huggingface dataset:
iloc: a framework for incremental location-state acquisition and prediction based on mobile sensors. much research focuses on predicting a person's geo-spatial traversal patterns using a history of recorded geo-coordinates. in this paper, we focus on the problem of predicting location-state transitions. location-states for a user refer to a set of anchoring points/regions in space, and the prediction task produces a sequence of predicted location states for a given query time window. if this problem can be solved accurately and efficiently, it may lead to new location based services (lbs) that can smartly recommend information to a user based on his current and future location states. the proposed iloc (incremental (location-state acquisition and prediction) framework solves the prediction problem by utilizing the sensor information provided by a user's mobile device. it incrementally learns the location states by constantly monitoring the signal environment of the mobile device. further, the framework tightly integrates the learning and prediction modules, allowing iloc to update location-states continuously and predict future location-states at the same time. our extensive experiments show that the quality of the location-states learned by iloc are better than the state-of-the-art. we also show that when other learners failed to produce reasonable predictions, iloc provides good forecasts. as for the efficiency, iloc processes the data in a single pass, which fits well to many data stream processing models.
demonstration of an rfid middleware: lit ale manager. the sharp increase of rfid tags and readers require dedicated middleware solutions that manage readers and process event data. in this paper, we demonstrate a rfid middleware called lit ale manager system with key features and also illustrate overall functional components of the middleware system with implementation techniques.
learning document aboutness from implicit user feedback and document structure. capturing the "aboutness" of documents has been a key research focus throughout the history of automated textual information processing. in this work, we represent aboutness using words and phrases that best reflect the central topics of a document. we present a machine learning approach that learns to score and rank words and phrases in a document according to their relevance to the document. we use implicit user feedback available in search engine click logs to characterize the user-perceived notion of term relevance. using a small set of manually generated training data, we show that the surrogate training data from click logs correlates well with this data, thus eliminating the need to create data for training manually which is both expensive and fundamentally difficult to obtain for such a task. further, we use a diverse set of features in our learning model that capitalize heavily on the structural and visual properties of web documents. in our extensive experimentation, we pay particular attention to tail web pages and show that our approach trained on mainly head web pages generalizes and performs well on all kinds of documents. in several evaluation methods using manually generated summaries and term relevance judgments, our system shows 25% improvement over other aboutness solutions.
efficient feature weighting methods for ranking. feature weighting or selection is a crucial process to identify an important subset of features from a data set. removing irrelevant or redundant features can improve the generalization performance of ranking functions in information retrieval. due to fundamental differences between classification and ranking, feature weighting methods developed for classification cannot be readily applied to feature weighting for ranking. a state of the art feature selection method for ranking, called gas, has been recently proposed, which exploits importance of each feature and similarity between every pair of features. however, gas must compute the similarity scores of all pairs of features, thus it is not scalable for high-dimensional data and its performance degrades on nonlinear ranking functions. this paper proposes novel algorithms, rankwrapper and rankfilter, which is scalable for high-dimensional data and also performs reasonably well on nonlinear ranking functions. rankwrapper and rankfilter are designed based on the key idea of relief algorithm. relief is a feature selection algorithm for classification, which exploits the notions of hits (data points within the same class) and misses (data points from different classes) for classification. however, there is no such notion of hits or misses in ranking. the proposed algorithms instead utilize the ranking distances of nearest data points in order to identify the key features for ranking. our extensive experiments show that rankwrapper and rankfilter generate higher accuracy overall than the gas and traditional relief algorithms adapted for ranking, and run substantially faster than the gas on high dimensional data.
comparative document summarization via discriminative sentence selection. given a collection of document groups, a quick question is what are the differences in these groups. in this paper, we study a novel problem of summarizing the differences between document groups. a discriminative sentence selection method is proposed to extract the most discriminative sentences which represent the specific characteristics of each document group. experiments on real world data sets demonstrate the effectiveness of our proposed method.
a hybrid index structure for geo-textual searches. the efficient execution of multi-criteria queries has gained increasing interest over the last years. in the present paper we propose an r-tree based approach for queries addressing textual as well as geographic filter conditions. whereas most previous approaches use an index structure optimised for a single criterion adding special treatment for the other criterion at the leaf nodes or end points of this index structure, our approach uses a deeper integration. in short, r-trees are maintained for certain subsets of the whole term set. furthermore, in each of these r-trees bit sets are used within the nodes to indicate whether entries for the terms associated with the single bits can be found in the corresponding sub-tree. our index structure aims to be both, time and space efficient. the paper investigates the efficiency and applicability of the proposed index structure via practical experiments based on real-world and synthetic data.
learning to rank from bayesian decision inference. ranking is a key problem in many information retrieval (ir) applications, such as document retrieval and collaborative filtering. in this paper, we address the issue of learning to rank in document retrieval. learning-based methods, such as ranknet, ranksvm, and rankboost, try to create ranking functions automatically by using some training data. recently, several learning to rank methods have been proposed to directly optimize the performance of ir applications in terms of various evaluation measures. they undoubtedly provide statistically significant improvements over conventional methods; however, from the viewpoint of decision-making, most of them do not minimize the bayes risk of the ir system. in an attempt to fill this research gap, we propose a novel framework that directly optimizes the bayes risk related to the ranking accuracy in terms of the ir evaluation measures. the results of experiments on the letor collections demonstrate that the framework outperforms several existing methods in most cases.
discovering matching dependencies. matching dependencies (mds) are recently proposed for various data quality applications such as detecting the violation of integrity constraints and duplicate object identification. in this paper, we study the problem of discovering matching dependencies for a given database instance. first, we formally define the measures, support and confidence, for evaluating the utility of mds in the given database instance. then, we study the discovery of mds with certain utility requirements of support and confidence. exact algorithms are developed, together with pruning strategies to improve the time performance. finally, our experimental evaluation demonstrates the efficiency of the proposed methods.
towards a universal wordnet by learning from combined evidence. lexical databases are invaluable sources of knowledge about words and their meanings, with numerous applications in areas like nlp, ir, and ai. we propose a methodology for the automatic construction of a large-scale multilingual lexical database where words of many languages are hierarchically organized in terms of their meanings and their semantic relations to other words. this resource is bootstrapped from wordnet, a well-known english-language resource. our approach extends wordnet with around 1.5 million meaning links for 800,000 words in over 200 languages, drawing on evidence extracted from a variety of resources including existing (monolingual) wordnets, (mostly bilingual) translation dictionaries, and parallel corpora. graph-based scoring functions and statistical learning techniques are used to iteratively integrate this information and build an output graph. experiments show that this wordnet has a high level of precision and coverage, and that it can be useful in applied tasks such as cross-lingual text classification.
the effect of negation on sentiment analysis and retrieval effectiveness. we investigate the problem of determining the polarity of sentiments when one or more occurrences of a negation term such as "not" appear in a sentence. the concept of the scope of a negation term is introduced. by using a parse tree and typed dependencies generated by a parser and special rules proposed by us, we provide a procedure to identify the scope of each negation term. experimental results show that the identification of the scope of negation improves both the accuracy of sentiment analysis and the retrieval effectiveness of opinion retrieval.
a risk minimization framework for domain adaptation. supervised learning algorithms usually require high quality labeled training set of large volume. it is often expensive to obtain such labeled examples in every domain of an application. domain adaptation aims to help in such cases by utilizing data available in related domains. however transferring knowledge from one domain to another is often non trivial due to different data distributions among the domains. moreover, it is usually very hard to measure and formulate these distribution differences. hence we introduce a new concept of label-relation function to transfer knowledge among different domains without explicitly formulating the data distribution differences. a novel learning framework, domain transfer risk minimization (dtrm), is proposed based on this concept. dtrm simultaneously minimizes the empirical risk for the target and the regularized empirical risk for source domain. under this framework, we further derive a generic algorithm called domain adaptation by label relation (dalr) that is applicable to various applications in both classification and regression settings. dalr iteratively updates the target hypothesis function and outputs for the source domain until it converges. we provide an in-depth theoretical analysis of dtrm and establish fundamental error bounds. we also experimentally evaluate dalr on the task of ranking search results using real-world data. our experimental results show that the proposed algorithm effectively and robustly utilizes data from source domains under various conditions: different sizes for source domain data; different noise levels for source domain data, and different difficulty levels for target domain data.
confucius and "its" intelligent disciples. confucius is a great teacher in ancient china. his theories and principles were effectively spread throughout china by his disciples. confucius is the product code name of google knowledge search product, which is built at google beijing lab by my team. in this talk, i present knowledge search key disciples, which are machine learning subroutines that generates labels for questions, that matches existing answers to a question, that evaluates quality of answers, that ranks users based on their contributions, that distills high-quality answers for search engines to index, etc. i will also present the scalable machine learning services that we built to make these disciples effective and efficient. the acm portal is published by the association for computing machinery. copyright © 2010 acm, inc. terms of usage privacy policy code of ethics contact us useful downloads: adobe acrobat quicktime windows media player real player
the impact of document structure on keyphrase extraction. keyphrases are short phrases that reflect the main topic of a document. because manually annotating documents with keyphrases is a time-consuming process, several automatic approaches have been developed. typically, candidate phrases are extracted using features such as position or frequency in the document text. document structure may contain useful information about which parts or phrases of a document are important, but has rarely been considered as a source of information for keyphrase extraction. we address this issue in the context of keyphrase extraction from scientific literature. we introduce a new, large corpus that consists of full-text journal articles, where the rich collection and document structure available at the publishing stage is explicitly annotated. we explore features based on the xml tags contained in the documents, and based on generic section types derived using position and cue words in section titles. for xml tags we find sections, abstract, and title to perform best, but many smaller elements may be beneficial in combination with other features. of the generic section types, the discussion section is found to be most useful for keyphrase extraction.
smoothing document language model with local word graph. smoothing document model with word graph is a new and effective method in information retrieval. word graph can naturally incorporate the dependency between the words; random walk algorithm based on the graph can be used to estimate the weight of each vertex. in this paper, we present a new way to construct a local word graph for smoothing document model, which exploits the document's k nearest neighbors: the vertices represent the words in the document and its k nearest neighbors, and the weights of the edges are estimated through word co-occurrence in the local document set. we argue that word graph is a key factor to the performance in graph-based smoothing method. by using the local document set, we can obtain a document specific word graph, and achieve better retrieval performance. experimental results on three trec collections show that our proposed approach is effective.
space-economical partial gram indices for exact substring matching. exact substring matching queries on large data collections can be answered using q-gram indices, that store for each occurring q-byte pattern an (ordered) posting list with the positions of all occurrences. such gram indices are known to provide fast query response time and to allow the index to be created quickly even on huge disk-based datasets. their main drawback is relatively large storage space, that is a constant multiple (typically >2) of the original data size, even when compression is used. in this work, we study methods to conserve the scalable creation time and efficient exact substring query properties of gram indices, while reducing storage space. to this end, we first propose a partial gram index based on a reduction from the problem of omitting indexed q-grams to the set cover problem. while this method is successful in reducing the size of the index, it generates false positives at query time, reducing efficiency. we then increase the accuracy of partial grams by splitting posting lists of frequent grams in a frequency-tuned set of signatures that take the bytes surrounding the grams into account. the resulting qs-gram scheme is tested on huge collections (up to 426gb) and is shown to achieve an almost 1:1 data:index size, and query performance even faster than normal gram methods, thanks to the reduced size and access cost.
data extraction from the web using wild card queries. this paper presents an overview of our work for searching and retrieving facts and relationships within natural language text sources. in this work, an extraction task over a text collection is expressed as a query that combines text fragments with wild cards, and the query result is a set of facts in the form of unary, binary and general n-ary tuples. despite being both simple and declarative, the framework can be applied to a wide range of extraction tasks. this paper presents an overview of the work and its various components. we also report some of our experiments and an evaluation of the proposed querying framework in extracting relevant information to a task.
learning from past queries for resource selection. federated text search provides a unified search interface for multiple search engines of distributed text information sources. resource selection is an important component for federated text search, which selects a small number of information sources that contain the largest number of relevant documents for a user query. most prior research of resource selection focused on selecting information sources by analyzing static information of available information sources that is sampled in the offline manner. on the other hand, most prior research ignored a large amount of valuable information like the results from past queries. this paper proposes a new resource selection technique (which is called qsim) that utilizes the search results of past queries for estimating the utilities of available information sources for a specific user query. experiment results demonstrate the effectiveness of the new resource selection algorithm.
density-based clustering using graphics processors. during the last few years, gpus have evolved from simple devices for the display signal preparation into powerful coprocessors that do not only support typical computer graphics tasks but can also be used for general numeric and symbolic computation tasks. as major advantage gpus provide extremely high parallelism combined with a high bandwidth in memory transfer at low cost. we want to exploit these dvantages in density-based clustering, an important paradigm in clustering since typical algorithms of this category are noise and outlier robust and search for clusters of an arbitrary shape in metric and vector spaces. moreover, with a time complexity ranging from o(n log n) to o(n2) these algorithms are scalable to large data sets in a database system. in this paper, we propose cuda-dclust, a massively parallel algorithm for density-based clustering for the use of a graphics processing unit (gpu). while the result of this algorithm is guaranteed to be equivalent to that of dbscan, we demonstrate a high speed-up, particularly in combination with a novel index structure for use in gpus.
graph classification based on pattern co-occurrence. subgraph patterns are widely used in graph classification, but their effectiveness is often hampered by large number of patterns or lack of discrimination power among individual patterns. we introduce a novel classification method based on pattern co-occurrence to derive graph classification rules. our method employs a pattern exploration order such that the complementary discriminative patterns are examined first. patterns are grouped into co-occurrence rules during the pattern exploration, leading to an integrated process of pattern mining and classifier learning. by taking advantage of co-occurrence information, our method can generate strong features by assembling weak features. unlike previous methods that invoke the pattern mining process repeatedly, our method only performs pattern mining once. in addition, our method produces a more interpretable classifier and shows better or competitive classification effectiveness in terms of accuracy and execution time.
an improved feedback approach using relevant local posts for blog feed retrieval. blog feed search aims to identify a blog feed with a recurring interest in a given topic. in this paper, we investigate the "pseudo-relevance feedback" for blog feed search task, where its unit of relevance judgment is not based on a blog post but a blog feed (the collection of all its constituent posts). this paper focuses on two characteristics of feed search task, blog feed's topical diversity and multifaceted property of query. we propose a novel feed-level selection of local posts which uses only highly relevant local posts in each top-ranked feed, in order to capture the correct and diverse relevant information to a given topic. experimental results show that the proposed approach outperforms traditional feedback approaches. especially, the proposed approach gives 2% further increase of ndcg over the best performing result of trec '08 blog distillation task.
user interests in social media sites: an exploration with micro-blogs. recent technological advances in mobile-based access to social networking platforms and facilities to update information in real{time (e.g. in facebook) have allowed an individual's online presence to be as ephemeral and dynamic in nature, as her very thoughts and interests. in this context, micro-blogging has been widely adopted by users as an effective means to capture and disseminate their thoughts and actions to a larger audience on a daily basis. interestingly, daily chatters of a user obtained from her micro-blogs offer a unique information source to analyze and interpret her context in real-time - i.e. interests, intentions,and activities. in this paper, we gather data from the public timeline of twitter spanning across ten worldwide cities over a period of four weeks. we use this dataset to (a) explore how users express interests in real-time through micro-blogs, and (b) understand how text mining techniques can be applied to interpret real-time context of a user based on her tweets. initial findings reported herein suggest that social media sites like twitter constitute a promising source for extracting user context that can be exploited by novel social networking applications.
improving search engines using human computation games. work on evaluating and improving the relevance of web search engines typically use human relevance judgments or clickthrough data. both these methods look at the problem of learning the mapping from queries to web pages. in this paper, we identify some issues with this approach, and suggest an alternative approach, namely, learning a mapping from web pages to queries. in particular, we use human computation games to elicit data about web pages from players that can be used to improve search. we describe three human computation games that we developed, with a focus on page hunt, a single-player game. we describe experiments we conducted with several hundred game players, highlight some interesting aspects of the data obtained and define the 'findability' metric. we also show how we automatically extract query alterations for use in query refinement using techniques from bitext matching. the data that we elicit from players has several other applications including providing metadata for pages and identifying ranking issues.
a query language for analyzing networks. with more and more large networks becoming available, mining and querying such networks are increasingly important tasks which are not being supported by database models and querying languages. this paper wants to alleviate this situation by proposing a data model and a query language for facilitating the analysis of networks. key features include support for executing external tools on the networks, flexible contexts on the network each resulting in a different graph, primitives for querying subgraphs (including paths) and transforming graphs. the data model provides for a closure property, in which the output of every query can be stored in the database and used for further querying.