waashk/dblp huggingface dataset:
sigma encoded inverted files. compression of term frequency lists and very long document-id lists within an inverted file search engine are examined. several compression schemes are compared including elias γ and δ codes, golomb encoding, variable byte encoding, and a class of word-based encoding schemes including simple-9, relative-10 and carryover-12. it is shown that these compression methods are not well suited to compressing these kinds of lists of numbers. of those tested, carryover-12 is preferred because it is both effective at compression and fast at decompression. a novel technique, sigma encoding prior to compression, is proposed and tested. sigma encoding utilizes a parameterized dictionary to reduce the number of bits necessary to store an integer. this method shows an about 0.3 bit per integer improvement over carryover-12 while costing only about 3 extra clock cycles per integer to decompress.
dynamic index pruning for effective caching. ram and dynamic pruning schemes to reduce query evaluation times. while only a small portion of lists are processed with dynamic pruning, current systems still store the entire inverted list in cache. in this paper we investigate caching only the pieces of the inverted lists that are actually used to answer a query during dynamic pruning. we examine an lru cache model, and two recently proposed models. we also introduce a new dynamic pruning scheme for impact-ordered inverted lists. using two large web collections and corresponding query logs we show that, using an lru cache, our new pruning scheme reduces the number of disk accesses during query processing time by 7%-15% over the state-of-the-art impact-ordered baseline, without reducing answer quality. surprisingly, however, we discover that using our new pruning scheme makes little difference to disk traffic when the more sophisticated caching schemes are employed.
improve retrieval accuracy for difficult queries using negative feedback. how to improve search accuracy for difficult topics is an under-addressed, yet important research question. in this paper, we consider a scenario when the search results are so poor that none of the top-ranked documents is relevant to a user's query, and propose to exploit negative feedback to improve retrieval accuracy for such difficult queries. specifically, we propose to learn from a certain number of top-ranked non-relevant documents to rerank the rest unseen documents. we propose several approaches to penalizing the documents that are similar to the known non-relevant documents in the language modeling framework. to evaluate the proposed methods, we adapt standard trec collections to construct a test collection containing only difficult queries. experiment results show that the proposed approaches are effective for improving retrieval accuracy of difficult queries.
probabilistic correlation-based similarity measure of unstructured records. computing the similarity between unstructured records is a fundamental function in multiple applications. approximate string matching and full text retrieval techniques do not show the best performance when applied directly, since the information are limited in unstructured records of short record length. in this paper, we propose a novel probabilistic correlation-based similarity measure. rather than simply conducting the exact matching tokens of two records, our similarity evaluation enriches the information of records by considering the correlations of tokens. we define the probabilistic correlation between tokens as the probability that these tokens appear in the same records. then we compute the weight of tokens and discover the correlations of records based on the probabilistic correlations of tokens. finally, we present extensive experimental results to demonstrate the effectiveness of our approach.
matching task profiles and user needs in personalized web search. personalization has been deemed one of the major challenges in information retrieval with a significant potential for providing better search experience to individual users. especially, the need for enhanced user models better capturing elements such as users' goals, tasks, and contexts has been identified. in this paper, we introduce a statistical language model for user tasks representing different granularity levels of a user profile, ranging from very specific search goals to broad topics. we propose a personalization framework that selectively matches the actual user information need with relevant past user tasks, and allows to dynamically switch the course of personalization from re-finding very precise information to biasing results to general user interests. in the extreme, our model is able to detect when the user's search and browse history is not appropriate for aiding the user in satisfying her current information quest. instead of blindly applying personalization to all user queries, our approach refrains from undue actions in these cases, accounting for the user's desire of discovering new topics, and changing interests over time. the effectiveness of our method is demonstrated by an empirical user study.
association thesaurus construction methods based on link co-occurrence analysis for wikipedia. wikipedia, a huge scale web based encyclopedia, attracts great attention as an invaluable corpus for knowledge extraction because it has various impressive characteristics such as a huge number of articles, live updates, a dense link structure, brief anchor texts and url identification for concepts. we have already proved that we can use wikipedia to construct a huge scale accurate association thesaurus. the association thesaurus we constructed covers almost 1.3 million concepts and its accuracy is proved in detailed experiments. however, we still need scalable methods to analyze the huge number of web pages and hyperlinks among articles in the web based encyclopedia. in this paper, we propose a scalable method for constructing an association thesaurus from wikipedia based on link co-occurrences. link co-occurrence analysis is more scalable than link structure analysis because it is a one-pass process. we also propose integration method of tfidf and link co-occurrence analysis. experimental results show that both our proposed methods are more accurate and scalable than conventional methods. furthermore, the integration of tfidf achieved higher accuracy than using only link co-occurrences.
evaluating partial tree-pattern queries on xml streams. the streaming evaluation is a popular way of evaluating queries on xml documents. besides its many advantages, it is also the only option for a number of important xml applications. unfortunately, existing algorithms focus almost exclusively on tree-pattern queries (tpqs). requirements for flexible querying of xml data have motivated recently the introduction of query languages that are more general and flexible than tpqs. we consider a partial tree-pattern query (ptpq) language which generalizes and strictly contains tpqs. ptpqs can express a fragment of xpath which comprises reverse axes and the node identity equality ($is$) operator, in addition to forward axes, wildcards and predicates. we outline an original streaming algorithm for ptpqs. our algorithm is the first one to support the streaming evaluation of such a broad fragment of xpath.
dr. searcher and mr. browser: a unified hyperlink-click graph. we introduce a unified graph representation of the web, which includes both structural and usage information. we model this graph using a simple union of the web's hyperlink and click graphs. the hyperlink graph expresses link structure among web pages, while the click graph is a bipartite graph of queries and documents denoting users' searching behavior extracted from a search engine's query log. our most important motivation is to model in a unified way the two main activities of users on the web: searching and browsing, and at the same time to analyze the effects of random walks on this new graph. the intuition behind this task is to measure how the combination of link structure and usage data provide additional information to that contained in these structures independently. our experimental results show that both hyperlink and click graphs have strengths and weaknesses when it comes to using their stationary distribution scores for ranking web pages. furthermore, our evaluation indicates that the unified graph always generates consistent and robust scores that follow closely the best result obtained from either individual graph, even when applied to "noisy" data. it is our belief that the unified web graph has several useful properties for improving current web document ranking, as well as for generating new rankings of its own. in particular stationary distribution scores derived from the random walks on the combined graph can be used as an indicator of whether structural or usage data are more reliable in different situations.
cache-aware load balancing for question answering. the need for high performance and throughput question answering (qa) systems demands for their migration to distributed environments. however, even in such cases it is necessary to provide the distributed system with cooperative caches and load balancing facilities in order to achieve the desired goals. until now, the literature on qa has not considered such a complex system as a whole. currently, the load balancer regulates the assignment of tasks based only on the cpu and i/o loads without considering the status of the system cache. this paper investigates the load balancing problem proposing two novel algorithms that take into account the distributed cache status, in addition to the cpu and i/o load in each processing node. we have implemented, and tested the proposed algorithms in a fully fledged distributed qa system. the two algorithms show that the choice of using the status of the cache was determinant in achieving good performance, and high throughput for qa systems.
key blog distillation: ranking aggregates. searchers on the blogosphere often have a need to identify other key bloggers with similar interests to their own. however, a main difference of this blog distillation task from normal adhoc or web document retrieval is that each blog can be seen as an aggregate of its constituent posts. on the other hand, we show that the task is similar to the expert search task, where a person's expertise is derived from the aggregate of their publications or emails. in this paper, we investigate several aspects of blog retrieval: firstly, we experiment whether a blog should be represented as a whole unit, or as by considering each of its posts as indicators of its relevance, showing that expert search techniques can be adapted for blog search; secondly, we examine whether indexing only the xml feed provided by each blog (and which is often incomplete) is sufficient, or whether the full-text of each blog post should be downloaded; lastly, we use approaches to detect the central or recurring interests of each blog to increase the retrieval effectiveness of the system. using the trec 2007 blog dataset, the results show that our proposed expert search paradigm is indeed useful in identifying key bloggers, achieving high retrieval effectiveness.
anomaly-free incremental output in stream processing. continuous queries enable alerts, predictions, and early warning in various domains such as health care, business process monitoring, financial applications, and environment protection. currently, the consistency of the result cannot be assessed by the application, since only the query processor has enough internal information to determine when the output has reached a consistent state. to our knowledge, this is the first paper that addresses the problem of consistency under the assumptions and constraints of a continuous query model. in addition to defining an appropriate consistency notion, we propose techniques for guaranteeing consistency. we implemented the proposed techniques in our existing stream engine, and we report on the characteristics of the observed performance. as we show, these methods are practical as they impose only a small overhead on the system.
non-local evidence for expert finding. the task addressed in this paper, finding experts in an enterprise setting, has gained in importance and interest over the past few years. commonly, this task is approached as an association finding exercise between people and topics. existing techniques use either documents (as a whole) or proximity-based techniques to represent candidate experts. proximity-based techniques have shown clear precision-enhancing benefits. we complement both document and proximity-based approaches to expert finding by importing global evidence of expertise, i.e., evidence obtained using information that is not available in the immediate proximity of a candidate expert's name occurrence or even on the same page on which the name occurs. examples include candidate priors, query models, as well as other documents a candidate expert is associated with. using the cerc data set created for the trec 2007 enterprise track we identify examples of non-local evidence of expertise. we then propose modified expert retrieval models that are capable of incorporating both local (either document or snippet-based) evidence and non-local evidence of expertise. results show that our refined models significantly outperform existing state-of-the-art approaches.
translating topics to words for image annotation. one of the classic techniques for image annotation is the language translation model. it views an image as a document, i.e., a set of visual words which are obtained by vector quatitizing the image regions generated by unsupervised image segmentation. annotating images are achieved by translating visual words to textual words, just like translating a document in english to a document in french. in this paper, we also view an image as a document, but we view the annotation processes as two consecutive processes, i.e., document summarization and translation. in the document summarization process, an image document is firstly summarized into its own visual language, which we called visual topics. the translation process translates these visual topics to textual words. compared to the original translation model, our visual topics learned by the probabilistic latent semantic analysis (plsa) approach provide an intermediate abstract level of visual description. we show improved annotation performance on the corel image dataset.
learning query-biased web page summarization. query-biased web page summarization is the summarization of a web page reflecting the relevance of it to a specific query. it plays an important role in search results representation of web search engines. in this paper, we propose a learning-based query-biased web page summarization method. the summarization problem is solved within the typical sentence selection framework. different from existing web page summarization methods that use page content or link context alone, both of them are considered as the sources of sentences in this work. most of existing learning-based summarization methods treat summarization as a sentence classification problem and train a classifier to discriminate between extracted sentences and non-extracted sentences of all training documents. the basic assumption of these methods is that sentences from different documents are comparable with respect to the class information. in contrast to the classification scheme, a ranking scheme is introduced to rank extracted sentences higher than non-extracted sentences of each training document. the underlying assumption that sentences within a document are comparable is weaker and more reasonable than the assumption of classification-based scheme. extensive results using intrinsic evaluation metrics gauge many aspects of the proposed method.
reconstructing ddc for interactive classification. the automated text categorization (tc) has made prominent progress in recent years. however, seldom work is done on automatic classification with library classification systems, the largest and most sophisticated classification systems people ever built, such as the dewey decimal classification (ddc). the library classification is a very laborious and time-consuming job that requires qualification and good training. the large-scale classification schemes, such as the ddc, impose several obstacles to the state-of-art tc technologies, including very deep hierarchy, data sparseness, and skewed category distribution. these problems characterize large corpora of real-world applications and it is very hard, if not impossible, to obtain satisfactory results. in this paper, we propose a novel algorithm to reconstruct classification schemes according to the document density and category distribution, and to transform the category hierarchy into a balanced virtual taxonomy by merging sparse categories, lopping dense branches and flattening the hierarchy. to make the classification performance acceptable to real-world applications, we also propose an interactive classification model that only needs two or three times of user interaction. extensive experiments are conducted on a 10-year bibliographic data collection of the library of congress to verify the proposed methodology.
shine: search heterogeneous interrelated entities. heterogeneous entities or objects are very common and are usually interrelated with each other in many scenarios. for example, typical web search activities involve multiple types of interrelated entities such as end users, web pages, and search queries. in this paper, we define and study a novel problem: <ul>s</ul>earch <ul>h</ul>eterogeneous <ul>in</ul>terrelated <ul>e</ul>ntities (shine). given a shine-query which can be any type(s) of entities, the task of shine is to retrieve multiple types of related entities to answer this query. this is in contrast to the traditional search,which only deals with a single type of entities (e.g., web pages). the advantages of shine include: (1) it is feasible for end users to specify their information need along different dimensions by accepting queries with different types. (2) answering a query by multiple types of entities provides informative context for users to better understand the search results and facilitate their information exploration. (3) multiple relations among heterogeneous entities can be utilized to improve the ranking of any particular type of entities. to attain the goal of shine, we propose to represent all entities in a unified space through utilizing their interaction relationships. two approaches, m-lsa and e-vsm, are discussed and compared in this paper. the experiments on 3 data sets (i.e., a literature data set, a search engine log data set, and a recommendation data set) show the effectiveness and flexibility of our proposed methods.
mining redundancy in candidate-bearing snippets to improve web question answering. conventional question answering (qa) techniques independently process candidate-bearing snippets to select an exact answer to a question from candidate answers. this paper presents two novel ways of utilizing redundancy in candidate-bearing snippets to help select an exact answer to a question in our web qa system, i.e., cluster-based language model (clm-m) and unsupervised svm classifier (u-svm) techniques. the comparative experiments demonstrate that the proposed methods significantly outperform the language model-based (lm-m) and supervised svm-based (s-svm) techniques that do not utilize this redundancy in the candidate-bearing snippets. using the clm-m, the top_1 score is increased from 36.03% (lm-m) to 46.96%; and the top_1 improvement in the u-svm over the s-svm is about 23%. moreover, a cross-model comparison shows that the performance ranking of these models is: u-svm > clm-lm > lm-m > s-svm > r-m (the retrieval-based model).
using social annotations to improve language model for information retrieval. this poster is concerned with the problem of exploring the use of social annotations for improving language models for information retrieval (denoted as lmir). two properties of social annotations, namely keyword property and structure property are studied for this aim. the keyword property improves lmir by concatenating all the annotations of a document to generate a summary of the document. the structure property can boost lmir further when similarity among annotations and similarity among documents are taken into consideration simultaneously. the two properties of social annotations are leveraged for the use of language modeling with a mixture model named as "language annotation model" (denoted as lam). evaluations using del.icio.us data show that lam outperforms the traditional lmir approaches significantly.
query expansion using probabilistic local feedback with application to multimedia retrieval. as one of the most effective query expansion approaches, local feedback is able to automatically discover new query terms and improve retrieval accuracy for different retrieval models. however, the performance of local feedback is heavily dependent on the assumption that most top-ranked documents are relevant to the query topic. although this assumption might be sensible for ad-hoc text retrieval, it is usually violated in many other retrieval tasks such as multimedia retrieval. in this paper, we develop a robust local analysis approach called probabilistic local feedback (plf) based on a discriminative probabilistic retrieval framework. the proposed model is effective for improving retrieval accuracy without assuming the most top-ranked documents are relevant. it also provides a sound probabilistic interpretation and a convergence guarantee on the iterative result updating process. although derived from variational techniques, this approach only involves an iterative process of simple operations on ranking features and thus can be computed efficiently in practice. our multimedia retrieval experiments on trecvid'03-'05 collections have demonstrated the advantage of the proposed plf approaches which can achieve noticeable gains in terms of mean average precision over various baseline methods and prf-augmented results.
link analysis using time series of web graphs. link analysis is a key technology in contemporary web search engines. most of the previous work on link analysis only used information from one snapshot of web graph. since commercial search engines crawl the web periodically, they will naturally obtain time series data of web graphs. the historical information contained in the series of web graphs can be used to improve the performance of link analysis. in this paper, we argue that page importance should be a dynamic quantity, and propose defining page importance as a function of both pagerank of the current web graph and accumulated historical page importance from previous web graphs. specifically, a novel algorithm named temporalrank is designed to compute the proposed page importance. we try to use a kinetic model to interpret this page importance and show that it can be regarded as the solution to an ordinary differential equation. experiments on link analysis using web graph data in five snapshots show that the proposed algorithm can outperform pagerank in many measures, and can effectively filter out newly appeared link spam websites.