waashk/dblp huggingface dataset:
rule-based data quality. in the business intelligence/data warehouse user community, there is a growing confusion as to the difference between data cleansing and data quality. while many data cleansing products can help in applying data edits to name and address data, or help in transforming data during an etl process, there is usually no persistence in this cleansing. this paper describes how we have implemented a business rules approach to build a data validation engine, called guardianiq, that transforms declarative data quality rules into code that objectively measures and reports levels of data quality based on user expectations.
text document clustering based on frequent word sequences. in this paper, we propose a new text clustering algorithm, named clustering based on frequent word sequences (cfws). a word sequence is frequent if it occurs in more than certain percentage of the documents in the text database. in the past, the vector space model was commonly used for information retrieval, but it treats documents as bags of words, ignoring the sequential pattern of word occurrences in the documents. however, the meaning of natural languages strongly depends on the word sequences, and the frequent word sequences can provide compact and valuable information about the text database. bisecting k-means and fihc algorithms are evaluated on the performance of text clustering, and are compared with the proposed cfws algorithm. it has been shown that cfws has much better performance.
boosting to correct inductive bias in text classification. this paper studies the effects of boosting in the context of different classification methods for text categorization, including decision trees, naive bayes, support vector machines (svms) and a rocchio-style classifier. we identify the inductive biases of each classifier and explore how boosting, as an error-driven resampling mechanism, reacts to those biases. our experiments on the reuters-21578 benchmark show that boosting is not effective in improving the performance of the base classifiers on common categories. however, the effect of boosting for rare categories varies across classifiers: for svms and decision trees, we achieved a 13-17% performance improvement in macro-averaged f1 measure, but did not obtain substantial improvement for the other two classifiers. this interesting finding of boosting on rare categories has not been reported before.
novelty detection based on sentence level patterns. the detection of new information in a document stream is an important component of many potential applications. in this paper, a new novelty detection approach based on the identification of sentence level patterns is proposed. given a user's information need, some patterns in sentences such as combinations of query words, named entities and phrases, may contain more important and relevant information than single words. therefore, the proposed novelty detection approach focuses on the identification of previously unseen query-related patterns in sentences. specifically, a query is preprocessed and represented with patterns that include both query words and required answer types. these patterns are used to retrieve sentences, which are then determined to be novel if it is likely that a new answer is present. an analysis of patterns in sentences was performed with data from the trec 2002 novelty track and experiments on novelty detection were carried out on data from the trec 2003 and 2004 novelty tracks. the experimental results show that the proposed pattern-based approach significantly outperforms all three baselines in terms of precision at top ranks.
personalized web search by mapping user queries to categories. current web search engines are built to serve all users, independent of the needs of any individual user. personalization of web search is to carry out retrieval for each user incorporating his/her interests. we propose a novel technique to map a user query to a set of categories, which represent the user's search intention. this set of categories can serve as a context to disambiguate the words in the user's query. a user profile and a general profile are learned from the user's search history and a category hierarchy respectively. these two profiles are combined to map a user query into a set of categories. several learning and combining algorithms are evaluated and found to be effective. among the algorithms to learn a user profile, we choose the rocchio-based method for its simplicity, efficiency and its ability to be adaptive. experimental results indicate that our technique to personalize web search is both effective and efficient.
a new approach to intranet search based on information extraction. this paper is concerned with 'intranet search'. by intranet search, we mean searching for information on an intranet within an organization. we have found that search needs on an intranet can be categorized into types, through an analysis of survey results and an analysis of search log data. the types include searching for definitions, persons, experts, and homepages. traditional information retrieval only focuses on search of relevant documents, but not on search of special types of information. we propose a new approach to intranet search in which we search for information in each of the special types, in addition to the traditional relevance search. information extraction technologies can play key roles in such kind of 'search by type' approach, because we must first extract from the documents the necessary information in each type. we have developed an intranet search system called 'information desk'. in the system, we try to address the most important types of search first - finding term definitions, homepages of groups or topics, employees' personal information and experts on topics. for each type of search, we use information extraction technologies to extract, fuse, and summarize information in advance. the system is in operation on the intranet of microsoft and receives accesses from about 500 employees per month. feedbacks from users and system logs show that users consider the approach useful and the system can really help people to find information. this paper describes the architecture, features, component technologies, and evaluation results of the system.
discovering the representative of a search engine. given a large number of search engines on the internet, it is difficult for a person to determine which search engines could serve his/her information needs. a common solution is to construct a metasearch engine on top of the search engines. upon receiving a user query, the metasearch engine sends it to those underlying search engines which are likely to return the desired documents for the query. the selection algorithm used by a metasearch engine to determine whether a search engine should be sent the query typically makes the decision based on the search-engine representative, which contains characteristic information about the database of a search engine. however, an underlying search engine may not be willing to provide the needed information to the metasearch engine. this paper shows that the needed information can be estimated from an uncooperative search engine with good accuracy. two pieces of information which permit accurate search engine selection are the number of documents indexed by the search engine and the maximum weight of each term. in this paper, we present techniques for the estimation of these two pieces of information.
efficient prediction of web accesses on a proxy server. web access prediction is an active research topic with many applications. various approaches have been proposed for web access prediction in the domain of individual web servers but they have to be tailored to the domain of proxy servers to satisfy its special requirements in prediction efficiency and scalability. in this paper, the design and implementation of proxy-based prediction service (pps) is presented. for prediction efficiency, pps applies a new prediction scheme which employs a two-layer navigation model to capture both inter-site and intra-site access patterns, incorporated with a bottom-up prediction mechanism that exploits reference locality in proxy logs. for system scalability, pps manages the navigation model in disk database and adopts a predictive cache replacement strategy for data shipping between the model database and cache. we show the superiority of our prediction scheme over existing approaches and validate our model management and caching strategies, with a detailed performance study using real-world data.
pruning long documents for distributed information retrieval. query-based sampling is a method of discovering the contents of a text database by submitting queries to a search engine and observing the documents returned. in prior research sampled documents were used to build resource descriptions for automatic database selection, and to build a centralized sample database for query expansion and result merging. an unstated assumption was that the associated storage costs were acceptable.when sampled documents are long, storage costs can be large. this paper investigates methods of pruning long documents to reduce storage costs. the experimental results demonstrate that building resource descriptions and centralized sample databases from the pruned contents of sampled documents can reduce storage costs by 54-93% while causing only minor losses in the accuracy of distributed information retrieval.
mining community structure of named entities from free text. although community discovery has been studied extensively in the web environment, limited research has been done in the case of free text. co-occurrence of words and entities in sentences and documents usually implies connections among them. in this paper, we investigate the co-occurrences of named entities in text, and mine communities among these entities. we show that identifying communities from free text can be transformed into a graph clustering problem. a hierarchical clustering algorithm is then proposed. our experiment shows that the algorithm is effective to discover named entity communities from text documents.
word sense disambiguation in queries. this paper presents a new approach to determine the senses of words in queries by using wordnet. in our approach, noun phrases in a query are determined first. for each word in the query, information associated with it, including its synonyms, hyponyms, hypernyms, definitions of its synonyms and hyponyms, and its domains, can be used for word sense disambiguation. by comparing these pieces of information associated with the words which form a phrase, it may be possible to assign senses to these words. if the above disambiguation fails, then other query words, if exist, are used, by going through exactly the same process. if the sense of a query word cannot be determined in this manner, then a guess of the sense of the word is made, if the guess has at least 50% chance of being correct. if no sense of the word has 50% or higher chance of being used, then we apply a web search to assist in the word sense disambiguation process. experimental results show that our approach has 100% applicability and 90% accuracy on the most recent robust track of trec collection of 250 queries. we combine this disambiguation algorithm to our retrieval system to examine the effect of word sense disambiguation in text retrieval. experimental results show that the disambiguation algorithm together with other components of our retrieval system yield a result which is 13.7% above that produced by the same system but without the disambiguation, and 9.2% above that produced by using lesk's algorithm. our retrieval effectiveness is 7% better than the best reported result in the literature.
qed: a novel quaternary encoding to completely avoid re-labeling in xml updates. the method of assigning labels to the nodes of the xml tree is called a labeling scheme. based on the labels only, both ordered and un-ordered queries can be processed without accessing the original xml file. one more important point for the labeling scheme is the label update cost in inserting or deleting a node into or from the xml tree. all the current labeling schemes have high update cost, therefore in this paper we propose a novel quaternary encoding approach for the labeling schemes. based on this encoding approach, we need not re-label any existing nodes when the update is performed. extensive experimental results on the xml datasets illustrate that our qed works much better than the existing labeling schemes on the label updates when considering either the number of nodes or the time for re-labeling.
on reducing redundancy and improving efficiency of xml labeling schemes. the basic relationships to be determined in xml query processing are ancestor-descendant (a-d), parent-child (p-c), sibling and ordering relationships. the containment labeling scheme can determine the a-d, p-c and ordering relationships fast, but it is very expensive in determining the sibling relationship. the prefix labeling scheme can determine all the four basic relationships fast if the xml tree is shallow. however, if the xml tree is deep, the prefix scheme is inefficient since the prefix is long. furthermore, the prefix label is repeated by all the siblings (only the self labels of these siblings are different). thus in this paper, we propose the p-containment and p-prefix schemes which can determine all the four basic relationships faster no matter what the xml structure is; meanwhile p-prefix can reduce the redundancies in the prefix labeling scheme.
content-based retrieval in hybrid peer-to-peer networks. hybrid peer-to-peer architectures use special nodes to provide directory services for regions of the network ("regional directory services"). hybrid peer-to-peer architectures are a potentially powerful model for developing large-scale networks of complex digital libraries, but peer-to-peer networks have so far tended to use very simple methods of resource selection and document retrieval. in this paper, we study the application of content-based resource selection and document retrieval to hybrid peer-to-peer networks. the directory nodes that provide regional directory services construct and use the content models of neighboring nodes to determine how to route query messages through the network. the leaf nodes that provide information use content-based retrieval to decide which documents to retrieve for queries. the experimental results demonstrate that using content-based retrieval in hybrid peer-to-peer networks is both more accurate and more efficient for some digital library environments than more common alternatives such as gnutella 0.6.
relational computation for mining association rules from xml data. we develop a fixpoint operator for computing large item sets and demonstrate three query paradigm solutions for association rule mining that use the idea of least fixpoint computation and indicates some optimisation issues. the results of our research provide theoretical foundation for relational computation of association rules and its application on xml mining.
on combining multiple clusterings. many problems can be reduced to the problem of combining multiple clusterings. in this paper, we first summarize different application scenarios of combining multiple clusterings and provide a new perspective of viewing the problem as a categorical clustering problem. we then show the connections between various consensus and clustering criteria and discuss the complexity results of the problem. finally we propose a new method to determine the final clustering. experiments on kinship terms and clustering popular music from heterogeneous feature sets show the effectiveness of combining multiple clusterings.
efficient processing of xml twig patterns with parent child edges: a look-ahead approach. with the growing importance of semi-structure data in information exchange, much research has been done to provide an effective mechanism to match a twig query in an xml database. a number of algorithms have been proposed recently to process a twig query holistically. those algorithms are quite efficient for quires with only ancestor-descendant edges. but for queries with mixed ancestor-descendant and parent-child edges, the previous approaches still may produce large intermediate results, even when the input and output size are more manageable. to overcome this limitation, in this paper, we propose a novel holistic twig join algorithm, namely <i>twigstacklist</i>. our main technique is to look-ahead read some elements in input data steams and cache limited number of them to <i>lists</i> in the main memory. the number of elements in any list is bounded by the length of the longest path in the xml document. we show that <i>twigstacklist</i> is i/o optimal for queries with only ancestor-descendant relationships below branching nodes. further, even when queries contain parent-child relationship below branching nodes, the set of intermediate results in <i>twigstacklist</i> is guaranteed to be a subset of that in previous algorithms. we complement our experimental results on a range of real and synthetic data to show the significant superiority of <i>twigstacklist</i> over previous algorithms for queries with <i>parent</i>-<i>child</i> relationships.
learning similarity measures in non-orthogonal space. many machine learning and data mining algorithms crucially rely on the similarity metrics. the cosine similarity, which calculates the inner product of two normalized feature vectors, is one of the most commonly used similarity measures. however, in many practical tasks such as text categorization and document clustering, the cosine similarity is calculated under the assumption that the input space is an orthogonal space which usually could not be satisfied due to <i>synonymy</i> and <i>polysemy</i>. various algorithms such as latent semantic indexing (lsi) were used to solve this problem by projecting the original data into an orthogonal space. however lsi also suffered from the high computational cost and data sparseness. these shortcomings led to increases in computation time and storage requirements for large scale realistic data. in this paper, we propose a novel and effective similarity metric in the non-orthogonal input space. the basic idea of our proposed metric is that the similarity of features should affect the similarity of objects, and vice versa. a novel iterative algorithm for computing non-orthogonal space similarity measures is then proposed. experimental results on a synthetic data set, a real msn search click-thru logs, and 20ng dataset show that our algorithm outperforms the traditional cosine similarity and is superior to lsi.
using micro information units for internet search. internet search is one of the most important applications of the web. a search engine takes the user's keywords to retrieve and to rank those pages that contain the keywords. one shortcoming of existing search techniques is that they do not give due consideration to the micro-structures of a web page. a web page is often populated with a number of small information units, which we call micro information units (miu). each unit focuses on a specific topic and occupies a specific area of the page. during the search, if all the keywords in the user query occur in a single miu of a page, the top ranking results returned by a search engine are generally relevant and useful. however, if the query words scatter at different mius in a page, the pages returned can be quite irrelevant (which causes low precision). the reason for this is that although a page has information on individual mius, it may not have information on their intersections. in this paper, we propose a technique to solve this problem. at the off-line pre-processing stage, we segment each page to identify the mius in the page, and index the keywords of the page according to the mius in which they occur. in searching, our retrieval and ranking algorithm utilizes this additional information to return those most relevant pages. experimental results show that this method is able to significantly improve the search precision.
text classification using esc-based stochastic decision lists. we propose a new method of text classification using stochastic decision lists. a stochastic decision list is an ordered sequence of if-then-else rules, and our method can be viewed as a rule-based method for text classification having advantages of readability and refinability of acquired knowledge. our method is unique in that decision lists are automatically constructed on the basis of the principle of minimizing extended stochastic complexity (esc), and with it we are able to construct decision lists that have fewer errors in classification. the accuracy of classification achieved with our method appears better than or comparable to those of existing rule-based methods. we have empirically demonstrated that rule-based methods like ours result in high classification accuracy when the categories to which texts are to be assigned are relatively specific ones and when the texts tend to be short. we have also empirically verified the advantages of rule-based methods over non-rule-based ones.
applying cosine series to join size estimation. this paper provides a general overview of two innovative applications of cosine series in xml joins and data stream joins.
analysis of pre-computed partition top method for range top-k queries in olap data cubes. in decision support systems, having knowledge on the top k values is more informative and crucial than the maximum value. unfortunately, the naive method involves high computational cost and the existing methods for range-max query are inefficient if applied directly. in this paper, we propose a pre-computed partition top method (ppt) to partition the data cube and pre-store a number of top values for improving query performance. the main focus of this study is to find the optimum values for two parameters, i.e., the partition factor (b) and the number of pre-stored values (r), through analytical approach. a cost function based on poisson distribution is used for the analysis. the analytical results obtained are verified against simulation results. it is shown that the ppt method outperforms other alternative methods significantly when proper b and r are used.
efficient multi-way text categorization via generalized discriminant analysis. text categorization is an important research area and has been receiving much attention due to the growth of the on-line information and of internet. automated text categorization is generally cast as a multi-class classification problem. much of previous work focused on binary document classification problems. support vector machines (svms) excel in binary classification, but the elegant theory behind large-margin hyperplane cannot be easily extended to multi-class text classification. in addition, the training time and scaling are also important concerns. on the other hand, other techniques naturally extensible to handle multi-class classification are generally not as accurate as svm. this paper presents a simple and efficient solution to multi-class text categorization. classification problems are first formulated as optimization via discriminant analysis. text categorization is then cast as the problem of finding coordinate transformations that reflects the inherent similarity from the data. while most of the previous approaches decompose a multi-class classification problem into multiple independent binary classification tasks, the proposed approach enables direct multi-class classification. by using generalized singular value decomposition (gsvd), a coordinate transformation that reflects the inherent class structure indicated by the generalized singular values is identified. extensive experiments demonstrate the efficiency and effectiveness of the proposed approach.