waashk/dblp huggingface dataset:
improving query i/o performance by permuting and refining block request sequences. the i/o performance of query processing can be improved using two complementary approaches: improve the buffer and the file system management policies of the db buffer manager and the os file system manager (e.g. page replacement), or improve the sequence of requests that are submitted to a file system manager and that lead to actual i/o's (block request sequences). this paper takes the latter approach. exploiting common file system practices as found in linux, we propose four techniques for permuting and refining block request sequences: block-level i/o grouping, file-level i/o grouping, i/o ordering, and block recycling. to manifest these techniques, we create two new plan operations, mms and shj, each of which adopts some of the block request refinement techniques above. we implement the new plan operations on top of postgres running on linux, and show experimental results that demonstrate up to a factor of 4 performance benefit from the use of these techniques.
effective keyword search for valuable lcas over xml documents. in this paper, we study the problem of effective keyword search over xml documents. we begin by introducing the notion of valuable lowest common ancestor (vlca) to accurately and effectively answer keyword queries over xml documents. we then propose the concept of compact vlca (cvlca) and compute the meaningful compact connected trees rooted as cvlcas as the answers of keyword queries. to efficiently compute cvlcas, we devise an effective optimization strategy for speeding up the computation, and exploit the key properties of cvlca in the design of the stack-based algorithm for answering keyword queries. we have conducted an extensive experimental study and the experimental results show that our proposed approach achieves both high efficiency and effectiveness when compared with existing proposals.
an efficient one-phase holistic twig join algorithm for xml data. in view of the inefficiency of the traditional two-phase twig-stack algorithm, we propose a single-phase holistic twig pattern matching method based on the twigstack algorithm by applying a novel stack structure.
on progressive sequential pattern mining. when sequential patterns are generated, the newly arriving patterns may not be identified as frequent sequential patterns due to the existence of old data and sequences. in practice, users are usually more interested in the recent data than the old ones. to capture the dynamic nature of data addition and deletion, we propose a general model of sequential pattern mining with a progressive database. in addition, we present a progressive concept to progressively discover sequential patterns in recent time period of interest.
predictive user click models based on click-through history. web search engines consistently collect information about users interaction with the system: they record the query they issued, the url of presented and selected documents along with their ranking. this information is very valuable: it is a poll over millions of users on the most various topics and it has been used in many ways to mine users interests and preferences. query logs have the potential to partially alleviate the search engines from thousand of searches by providing a way to predict answers for a subset of queries and users without knowing the content of a document. even if the predicted result is at rank one, this analysis might be of interest: if there is enough confidence on a user's click, we might redirect the user directly to the page whose link would be clicked. in this paper, we present three different models for predicting user clicks, ranging from most specific ones (using only past user history for the query) to very general ones (aggregating data over all users for a given query). the former model has a very high precision at low recall values, while the latter can achieve high recalls. we show that it is possible to combine the different models to predict with high accuracy (over 90%) a high subset of query sessions (24% of all the sessions).
annotation propagation revisited for key preserving views. this paper revisits the analysis of annotation propagation from source databases to views defined in terms of conjunctive (spj) queries. given a source database d, an spj query q, the view q(d) and a tuple δv in the view, the view (resp. source) side-effect problem is to find a minimal set δd of tuples such that the deletion of δd from d results in the deletion of δv from q(d) while minimizing the side effects on the view (resp. the source). a third problem, referred to as the annotation placement problem, is to find a single base tuple δd such that annotation in a field of δd propagates to δv while minimizing the propagation to other fields in the view q(d). these are important for data provenance and the management of view updates. however important, these problems are unfortunately np-hard for most subclasses of spj views [5].to make the annotation propagation analysis feasible in practice, we propose a key preserving condition on spj views, which requires that the projection fields of an spj view q retain a key of each base relation involved in q. while this condition is less restrictive than other proposals [11, 14], it often simplifies the annotation propagation analysis. indeed, for key-preserving spj views the annotation placement problem coincides with the view side-effect problem, and the view and source side-effect problems become tractable. in addition we generalize the setting of [5] by allowing δv to be a group of tuples to be deleted, and investigate the insertion of tuples to the view. we show that group updates make the analysis harder: these problems become np-hard for several subclasses of spj views. we also show that for spj views the source and view side-effect problems are np-hard for single-tuple insertion, but are tractable for some subclasses of spj for group insertions, in the presence or in the absence of the key preservation condition.
discovering and exploiting keyword and attribute-value co-occurrences to improve p2p routing indices. peer-to-peer (p2p) search requires intelligent decisions for query routing: selecting the best peers to which a given query, initiated at some peer, should be forwarded for retrieving additional search results. these decisions are based on statistical summaries for each peer, which are usually organized on a per-keyword basis and managed in a distributed directory of routing indices. such architectures disregard the possible correlations among keywords. together with the coarse granularity of per-peer summaries, which are mandated for scalability, this limitation may lead to poor search result quality.this paper develops and evaluates two solutions to this problem, sk-stat based on single-key statistics only, and mk-stat based on additional multi-key statistics. for both cases, hash sketch synopses are used to compactly represent a peer's data items and are efficiently disseminated in the p2p network to form a decentralized directory. experimental studies with gnutella and web data demonstrate the viability and the trade-offs of the approaches.
introduction to a new farsi stemmer. in this poster, a new farsi (also called persian) stemmer which works without dictionary is introduced. evaluation results show significant improvement in performance (precision/recall) of the information retrieval (ir) system using this stemmer.
window join approximation over data streams with importance semantics. load shedding techniques generate approximate sliding window join results when memory constraints prevent exact computation. the previously proposed random load shedding method drops input tuples without consideration for the number of outputs created, while the recently proposed semantic load shedding technique aims to produce the largest possible result set. we consider a new model in which data stream tuples contain numerical importance values relevant to the query source and seek to maximize the importance of the approximate join result. we show that both random load shedding and semantic load shedding are sub-optimal in this situation, while the techniques presented in this paper satisfy the objective function by considering both tuple importance and join attribute distributions. we extend the existing offline semantic approximation technique to make it compatible with our objective function and show that it is less space and time efficient than our new optimal offline algorithm for small and large join memory allotments. we also introduce four efficient online algorithms, which are quite promising in maximizing the importance of the approximate join result without foreknowledge of input streams.
efficiently clustering transactional data with weighted coverage density. it is widely recognized that developing efficient and fully automated algorithms for clustering large transactional datasets is a challenging problem. in this paper, we propose a fast, memory-efficient, and scalable clustering algorithm for analyzing transactional data. our approach has three unique features. first, we use the concept of weighted coverage density as a categorical similarity measure for efficient clustering of transactional datasets. the concept of weighted coverage density is intuitive and allows the weight of each item in a cluster to be changed dynamically according to the occurrences of items. second, we develop two transactional data clustering specific evaluation metrics based on the concept of large transactional items and the coverage density respectively. third, we implement the weighted coverage density clustering algorithm and the two clustering validation metrics using a fully automated transactional clustering framework, called scale (sampling, clustering structure assessment, clustering and domain-specific evaluation). the scale framework is designed to combine the weighted coverage density measure for clustering over a sample dataset with self-configuring methods that can automatically tune the two important parameters of the clustering algorithms: (1) the candidates of the best number k of clusters; and (2) the application of two domain-specific cluster validity measures to find the best result from the set of clustering results. we have conducted experimental evaluation using both synthetic and real datasets and our results show that the weighted coverage density approach powered by the scale framework can efficiently generate high quality clustering results in a fully automated manner.
ontology module extraction for ontology reuse: an ontology engineering perspective. problems resulting from the management of shared, distributed knowledge has led to ontologies being employed as a solution, in order to effectively integrate information across applications. this is dependent on having ways to share and reuse existing ontologies; with the increased availability of ontologies on the web, some of which include thousands of concepts, novel and more efficient methods for reuse are being devised. one possible way to achieve efficient ontology reuse is through the process of ontology module extraction. a novel approach to ontology module extraction is presented that aims to achieve more efficient reuse of very large ontologies; the motivation is drawn from an ontology engineering perspective. this paper provides a definition of ontology modules from the reuse perspective and an approach to module extraction based on such a definition. an abstract graph model for module extraction has been defined, along with a module extraction algorithm. the novel contribution of this paper is a module extraction algorithm that is independent of the language in which the ontology is expressed. this has been implemented in modtool; a tool that produces ontology modules via extraction. experiments were conducted to compare modtool to other modularisation methods.
the visual funding navigator: analysis of the nsf funding information. this paper presents an interactive visualization toolkit for navigating and analyzing the national science foundation (nsf) funding information. our design builds upon an improved 2.5d treemap layout and the stacked graph to contribute customized techniques for visually navigating and interacting with the hierarchical data of nsf programs and proposals. furthermore, an incremental layout method is adopted to handle information on a large scale. the improved treemap visualization will help to visually analyze the static funding related data and the stacked graph is utilized to analyze the time-series data. through these visual analysis techniques, research trends of nsf, popular nsf programs are quickly identified.
utilizing a geometry of context for enhanced implicit feedback. implicit feedback algorithms utilize interaction between searchers and search systems to learn more about users' needs and interests than expressed in query statements alone. this additional information can be used to formulate improved queries or directly improve retrieval performance. in this paper we present a geometric framework that utilizes multiple sources of evidence present in this interaction context (e.g., display time, document retention) to develop enhanced implicit feedback models personalized for each user and tailored for each search task. we use rich interaction logs (and associated metadata such as relevance judgments), gathered during a longitudinal user study, as relevance stimuli to compare an implicit feedback algorithm developed using the framework with alternative algorithms. our findings demonstrate both the effectiveness of our proposed algorithm and the potential value of incorporating multiple sources of interaction evidence when developing implicit feedback algorithms.
incorporating query difference for learning retrieval functions in world wide web search. we discuss information retrieval methods that aim at serving a diverse stream of user queries such as those submitted to commercial search engines. we propose methods that emphasize the importance of taking into consideration of query difference in learning effective retrieval functions. we formulate the problem as a multi-task learning problem using a risk minimization framework. in particular, we show how to calibrate the empirical risk to incorporate query difference in terms of introducing nuisance parameters in the statistical models, and we also propose an alternating optimization method to simultaneously learn the retrieval function and the nuisance parameters. we work out the details for both l1 and l2 regularization cases, and provide convergence analysis for the alternating optimization method for the special case when the retrieval functions belong to a reproducing kernel hilbert space. we illustrate the effectiveness of the proposed methods using modeling data extracted from a commercial search engine. we also point out how the current framework can be extended in future research.
genre identification and goal-focused summarization. in this paper, we present a novel technique of first performing document genre identification, then utilizing the genre for producing tailored summaries based on a user's information seeking needs - genre oriented goal-focused summarization - such as a plot or opinion summary of a movie review. we create a test corpus to determine genre classification accuracy for 16 genres, and examine performance on various amounts of training data for machine learning algorithms - random forests, svm light and naïve bayes. results show that random forests outperforms svm light and naïve bayes. the genre tag is used to inform a downstream summarization engine. we define types of summaries for 7 genres, create a ground truth corpus and analyze the results of genre oriented goal-focused summarization, showing that this type of user based summarization requires different algorithms than the leading sentence baseline which is known to perform well in the case of news articles.
incremental hierarchical clustering of text documents. incremental hierarchical text document clustering algorithms are important in organizing documents generated from streaming on-line sources, such as, newswire and blogs. however, this is a relatively unexplored area in the text document clustering literature. popular incremental hierarchical clustering algorithms, namely cobweb and classit, have not been widely used with text document data. we discuss why, in the current form, these algorithms are not suitable for text clustering and propose an alternative formulation that includes changes to the underlying distributional assumption of the algorithm in order to conform with the data. both the original classit algorithm and our proposed algorithm are evaluated using reuters newswire articles and ohsumed dataset.
hypothesis testing with incomplete relevance judgments. information retrieval experimentation generally proceeds in a cycle of development, evaluation, and hypothesis testing. ideally, the evaluation and testing phases should be short and easy, so as to maximize the amount of time spent in development. there has been recent work on reducing the amount of assessor effort needed to evaluate retrieval systems, but it has not, for the most part, investigated the effects of these methods on tests of significance. in this work, we explore in detail the effects of reduced sets of judgments on the sign test. we demonstrate both analytically and empirically the relationship between the power of the test, the number of topics evaluated, and the number of judgments available. using these relationships, we can determine the number of topics and judgments needed for the least-cost but highest-confidence significance evaluation. specifically, testing pairwise significance over 192 topics with fewer than 5 judgments for each is as good as testing significance over 25 topics with an average of 166 judgments for each - 85% less effort producing no additional errors.
processing relaxed skylines in pdms using distributed data summaries. peer data management systems (pdms) are a natural extension of heterogeneous database systems. one of the main tasks in such systems is efficient query processing. insisting on complete answers, however, leads to asking almost every peer in the network. relaxing these completeness requirements by applying approximate query answering techniques can significantly reduce costs. since most users are not interested in the exact answers to their queries, rank-aware query operators like top-k or skyline play an important role in query processing. in this paper, we present the novel concept of relaxed skylines that combines the advantages of both rank-aware query operators and approximate query processing techniques. furthermore, we propose a strategy for processing relaxed skylines in distributed environments that allows for giving guarantees for the completeness of the result using distributed data summaries as routing indexes.
filtering or adapting: two strategies to exploit noisy parallel corpora for cross-language information retrieval. noisy parallel corpora have been widely used for cross-language information retrieval (clir). however, the previous studies only focus on truly parallel corpus. in this paper, we examine two possible approaches to exploit noisy corpora: filtering out noise from the corpora or adapting the training process of translation model to the noise corpora. our experiments show that the second approach is better suited to clir.
towards practically feasible answering of regular path queries in lav data integration. regular path queries (rpq's) are given by means of regular expressions and ask for matching patterns on labeled graphs. rpq's have received great attention in the context of semistructured data, which are data whose structure is irregular, partially known, or subject to frequent changes. one of the most important problems in databases today is the integration of semistructured data from multiple sources modeled as views. the well-know paradigm of computing first a view-based rewriting of the query, and then evaluating the rewriting on the view extensions is indeed possible for rpq's. however, computing the rewriting is computationally hard as it can only be done (in the worst case) in not less than 2exptime. in this paper, we provide practical evidence that computing the rewriting is hard on the average as well. on the positive side, we propose automata-theoretic techniques, which efficiently compute and utilize instead the complement of the rewriting. notably using the latter, it is possible to answer a query, and this makes the view-based answering of rpq's fairly feasible in practice.
text classification improved through multigram models. classification algorithms and document representation approaches are two key elements for a successful document classification system. in the past, much work has been conducted to find better ways to represent documents. however, most of the attempts rely on certain extra resources such as wordnet, or they face the problem of extremely high dimension. in this paper, we propose a new document representation approach based on n-multigram language models. this approach can automatically discover the hidden semantic sequences in the documents under each category. based on n-multigram language models and n-gram language models, we put forward two text classification algorithms. the experiments on rcv1 show that our proposed algorithm based on n-multigram models alone can achieve the similar or even better classification performance compared with the classifier based on n-gram models but the model size of our algorithm is much smaller than that of the latter. another proposed algorithm based on the combination of n-multigram models and n-gram models improves the micro-f1 and macro-f1 values from 89.5% to 92.6% and 87.2% to 91.1% respectively. all these observations support the validity of our proposed document representation approach.
predicting individual priorities of shared activities using support vector machines. activity-centric collaboration environments help knowledge workers to manage the context of their shared work activities by providing a representation for an activity and its resources. activity management systems provide more structure and organization than email to execute the shared activity but, as the number of shared activities increases, it becomes more and more difficult for users to focus on important activities that need their attention. this paper describes a personalized activity prioritization approach implemented on top of the lotus connections activities management system. our prototype implementation allows each user to view activities ordered by her/his predicted priorities. the predictions are made using a ranking support vector machine model trained with the user's past interactions with the activities system. we describe the prioritization interface and the results of an offline experiment based on data from 13 users over 6-months. our results show that our feature set derived from shared activity structures can significantly increase prediction accuracy compared to a recency baseline.
combining feature selectors for text classification. we introduce several methods of combining feature selectors for text classification. results from a large investigation of these combinations are summarized. easily constructed combinations of feature selectors are shown to improve peak r-precision and f1 at statistically significant levels.