waashk/dblp huggingface dataset:
a unified model for metasearch, pooling, and system evaluation. we present a unified model which, given the ranked lists of documents returned by multiple retrieval systems in response to a given query, simultaneously solves the problems of (1) fusing the ranked lists of documents in order to obtain a high-quality combined list (metasearch); (2) generating document collections likely to contain large fractions of relevant documents (pooling); and (3) accurately evaluating the underlying retrieval systems with small numbers of relevance judgments (efficient system assessment). our approach is based on the hedge algorithm for on-line learning. in effect, our proposed system "learns" which documents are likely to be relevant from a sequence of on-line relevance judgments. in experiments using trec data, our methodology is shown to outperform standard methods for metasearch, pooling, and system evaluation, often remarkably so.
real time user context modeling for information retrieval agents. the success of personal information agents depends on their ability to provide task-relevant information. this paper presents wordsieve, a new algorithm that generates context descriptions to guide document indexing and retrieval. wordsieve exploits information about the sequence of accessed documents to identify words which indicate a shift in context. we have tested wordsieve in a personal information agent, calvin, which monitors a user's document access, generates a representation of the user's task context, indexes the resources consulted, and presents recommendations for other resources that were consulted in similar prior contexts. in initial experiments, wordsieve outperforms term frequency/inverse document frequency at matching documents to hand-coded vector representations of the task contexts in which they were originally consulted, where the task context representations are term vectors representing a specific search task given to the user.
hierarchical graph indexing. traffic analysis, in the context of telecommunications or internet and web data, is crucial for large network operations. data in such networks is often provided as large graphs with hundreds of millions of vertices and edges. we propose efficient techniques for managing such graphs at the storage level in order to facilitate its processing at the interface level(visualization). the methods are based on a hierarchical decomposition of the graph edge set that is inherited from a hierarchical decomposition of the vertex set. real time navigation is provided by an efficient two level indexing schema called the gkd*-tree. the first level is a variation of a kd-tree index that partitions the edge set in a way that conforms to the hierarchical decomposition and the data distribution (the gkd-tree). the second level is a redundant r-tree that indexes the leaf pages of the gkd-tree. we provide computational results that illustrate the superiority of the gkd-tree against conventional indexes like the kd-tree and the r*-tree both in creation as well as query response times.
managing trust in a peer-2-peer information system. managing trust is a problem of particular importance in peer-to-peer environments where one frequently encounters unknown agents. existing methods for trust management, that are based on reputation, focus on the semantic properties of the trust model. they do not scale as they either rely on a central database or require to maintain global knowledge at each agent to provide data on earlier interactions. in this paper we present an approach that addresses the problem of reputation-based trust management at both the data management and the semantic level. we employ at both levels scalable data structures and algorithms that require no central control and allow to assess trust by computing an agents reputation from its former interactions with other agents. thus the meethod can be implemented in a peer-to-peer environment and scales well for very large numbers of participants. we expect that scalable methods for trust management are an important factor, if fully decentralized peer-to-peer systems should become the platform for more serious applications than simple file exchange.
using titles and category names from editor-driven taxonomies for automatic evaluation. evaluation of ir systems has always been difficult because of the need for manually assessed relevance judgments. the advent of large editor-driven taxonomies on the web opens the door to a new evaluation approach. we use the odp (open directory project) taxonomy to find sets of pseudo-relevant documents via one of two assumptions: 1) taxonomy entries are relevant to a given query if their editor-entered titles exactly match the query, or 2) all entries in a leaf-level taxonomy category are relevant to a given query if the category title exactly matches the query. we compare and contrast these two methodologies by evaluating six web search engines on a sample from an america online log of ten million web queries, using mrr measures for the first method and precision-based measures for the second. we show that this technique is stable with respect to the query set selected and correlated with a reasonably large manual evaluation.
building xml statistics for the hidden web. there have been several techniques proposed for building statistics for static xml data. however, very little work has been done in the area of building xml statistics for data sources that export xml views of data that is stored in relational or other databases. for such data sources, we need statistics that are built in an on-line manner, by observing the xml queries to the data sources and their results. in this paper, we present a technique for building on-line xml statistics by observing the xpath queries issued to a data source and their result sizes. these xpath queries select parts of the virtual xml document representing the xml view of the data at the data source. we convert these xpath queries to a more abstract and generalized form that we call annotated path expressions. we present a technique for storing these annotated path expressions and information about their selectivity for use in estimating the selectivity of future xpath queries. we also present an experimental evaluation of our proposed approach.
a system for knowledge management in bioinformatics. the emerging biochip technology has made it possible to simultaneously study expression (activity level) of thousands of genes or proteins in a single experiment in the laboratory. however, in order to extract relevant biological knowledge from the biochip experimental data, it is critical not only to analyze the experimental data, but also to cross-reference and correlate these large volumes of data with information available in external biological databases accessible online. we address this problem in a comprehensive system for knowledge management in bioinformatics called e2e. to the biologist or biological applications, e2e exposes a common semantic view of inter-relationship among biological concepts in the form of an xml representation called expressml, while internally, it can use any data integration solution to retrieve data and return results corresponding to the semantic view. we have implemented an e2e prototype that enables a biologist to analyze her gene expression data in geml or from a public site like stanford, and discover knowledge through operations like querying on relevant annotated data represented in expressml using pathways data from kegg, publication data from medline and protein data from swiss-prot.
bootstrapping for hierarchical document classification. managing the hierarchical organization of data is starting to play a key role in the knowledge management community due to the great amount of human resources needed to create and maintain these organized repositories of information. machine learning community has in part addressed this problem by developing hierarchical supervised classifiers that help maintainers to categorize new resources within given hierarchies. although such learning models succeed in exploiting relational knowledge, they are highly demanding in terms of labeled examples, because the number of categories is related to the dimension of the corresponding hierarchy. hence, the creation of new directories or the modification of existing ones require strong investments.this paper proposes a semi-automatic process (interleaved with human suggestions) whose aim is to minimize (simplify) the work required to the administrators when creating, modifying, and maintaining directories. within this process, bootstrapping a taxonomy with examples represents a critical factor for the effective exploitation of any supervised learning model. for this reason we propose a method for the bootstrapping process that makes a first hypothesis of categorization for a set of unlabeled documents, with respect to a given empty hierarchy of concepts. based on a revision of self-organizing maps, namely taxsom, the proposed model performs an unsupervised classification, exploiting the a-priori knowledge encoded in a taxonomy structure both at the terminological and topological level. the ultimate goal of taxsom is to create the premise for successfully training a supervised classifier.
redundant documents and search effectiveness. the web contains a great many documents that are content-equivalent, that is, informationally redundant with respect to each other. the presence of such mutually redundant documents in search results can degrade the user search experience. previous attempts to address this issue, most notably the trec novelty track, were characterized by difficulties with accuracy and evaluation. in this paper we explore syntactic techniques --- particularly document fingerprinting --- for detecting content equivalence. using these techniques on the trec gov1 and gov2 corpora revealed a high degree of redundancy; a user study confirmed that our metrics were accurately identifying content-equivalence. we show, moreover, that content-equivalent documents have a significant effect on the search experience: we found that 16.6% of all relevant documents in runs submitted to the trec 2004 terabyte track were redundant.
haystack: per-user information environments. traditional information retrieval (ir) systems are designed to provide uniform access to centralized corpora by large numbers of people. the haystack project emphasizes the relationship between a particular individual and his corpus. an individual's own haystack priviliges information with which that user interacts, gathers data about those interactions, and uses this metadata to further personalize the retrieval process. this paper describes the prototype haystack system.
swam: a family of access methods for similarity-search in peer-to-peer data networks. peer-to-peer data networks (pdns) are large-scale, self-organizing, distributed query processing systems. familiar examples of pdn are peer-to-peer file-sharing networks, which support exact-match search queries to locate user-requested files. in this paper, we formalize the more general problem of <i>similarity-search</i> in pdns, and propose a <i>family</i> of distributed access methods, termed <i>small-world access methods (swam)</i>, for efficient execution of various similarity-search queries, namely exact-match, range, and k-nearest-neighbor queries. unlike its predecessors, i.e., lh* and dhts, swam does not control the assignment of data objects to pdn nodes; each node autonomously stores its own data. besides, swam supports all similarity-search queries on multiple attributes. swam guarantees that the query object will be found (if it exists in the network) in average time logarithmically proportional to the network size. moreover, once the query object is found, all the similar objects would be in its proximate network neighborhood and hence enabling efficient range and k-nearest-neighbor queries. as a specific instance of swam, we propose <i>swam-v</i>, a voronoi-based swam that indexes pdns with multi-attribute data objects. for a pdn with <i>n</i> nodes swam-v has query time, communication cost, and computation cost of <i>o</i>(log <i>n</i>) for exact-match queries, and <i>o</i>(log <i>n</i> + <b>s</b><i>n</i>) and <i>o</i>(log <i>n</i> + <b>k</b>) for range queries (with selectivity <b>s</b>) and <b>k</b>nn queries, respectively. our experiments show that swam-v consistently outperforms a similarity-search enabled version of can in query time and communication cost by a factor of 2 to 3.
internet scale string attribute publish/subscribe data networks. with this work we aim to make a three-fold contribution. we first address the issue of supporting efficiently queries over string-attributes involving prefix, suffix, containment, and equality operators in large-scale data networks. our first design decision is to employ distributed hash tables (dhts) for the data network's topology, harnessing their desirable properties. our next design decision is to derive dht-independent solutions, treating dht as a black box. second, we exploit this infrastructure to develop efficient content based publish/subscribe systems. the main contribution here are algorithms for the efficient processing of queries (subscriptions) and events (publications). specifically, we show that our subscription processing algorithms require o(logn) messages for a n-node network, and our event processing algorithms require o(l x logn) messages (with l being the average string length).third, we develop algorithms for optimizing the processing of multi-dimensional events, involving several string attributes. further to our analysis, we provide simulation-based experiments showing promising performance results in terms of number of messages, required bandwidth, load balancing, and response times.
approximate searches: k-neighbors + precision. it is known that all multi-dimensional index structures fail to accelerate content-based similarity searches when the feature vectors describing images are high-dimensional. it is possible to circumvent this problem by relying on approximate search-schemes trading-off result quality for reduced query execution time. most approximate schemes, however, provide none or only complex control on the precision of the searches, especially when retrieving the k nearest neighbors (nns) of query points.in contrast, this paper describes an approximate search scheme for high-dimensional databases where the precision of the search can be probabilistically controlled when retrieving the k nns of query points. it allows a fine and intuitive control over this precision by setting at run time the maximum probability for a vector that would be in the exact answer set to be missed in the approximate set of answers eventually returned. this paper also presents a performance study of the implementation using real datasets showing its reliability and efficiency. it shows, for example, that our method is 6.72 times faster than the sequential scan when it handles more than 5 106 24-dimensional vectors, even when the probability of missing one of the true nearest neighbors is below 0.01.
answering aggregation queries on hierarchical web sites using adaptive sampling. we study how to answer aggregation queries over hierarchical web sites using adaptive sampling.
using speculation to reduce server load and service time on the www. abstract speculative service implies that a client''s request for a document is serviced by sending, in addition to the document requested, a number of other documents that the server speculates will be requested by the client in the near future. this speculation is based on statistical information that the server maintains for each document it serves. the notion of speculative service is analogous to prefetching, which is used to improve cache performance in distributed/parallel shared memory systems, with the exception that servers (not clients) control when and what to prefetch. using trace simulations based on the logs of our departmental http server http://cs-www.bu.edu, we show that both server load and service time could be reduced considerably, if speculative service is used. this is above and beyond what is currently achievable using client-side caching and server-side dissemination. we identify a number of parameters that could be used to fine-tune the level of speculation performed by the server based on the level of lookahead, the state of the network, the tradeoffs between bulk and individual transmission of documents, and the relative popularity of documents, among other factors.
protein structure alignment using geometrical features. a novel approach for similarity search on protein structure databases is proposed which incorporates the three dimensional coordinates of the main atoms of each amino acid and extracts a geometrical signature along with the direction of the given amino acid. as a result, each protein is presented by a series of feature vectors representing local geometry, shape, direction, and secondary structure assignment of its amino acid constituents. furthermore, a residue-to-residue distance matrix is calculated and is incorporated into a local alignment dynamic programming algorithm to find the similar portions of two given proteins and finally a sequence alignment step is used as the last filtration step. the optimal superimposition of the detected similar regions is used to assess the quality of the results. the proposed algorithm is fast and accurate and hence could be used for the analysis of large protein structure similarity.
predicting accuracy of extracting information from unstructured text collections. exploiting lexical and semantic relationships in large unstructured text collections can significantly enhance managing, integrating, and querying information locked in unstructured text. most notably, named entities and relations between entities are crucial for effective question answering and other information retrieval and knowledge management tasks. unfortunately, the success in extracting these relationships can vary for different domains, languages, and document collections. predicting extraction performance is an important step towards scalable and intelligent knowledge management, information retrieval and information integration. we present a general language modeling method for quantifying the difficulty of information extraction tasks. we demonstrate the viability of our approach by predicting performance of real world information extraction tasks, named entity recognition and relation extraction.
mining all maximal frequent word sequences in a set of sentences. we present an efficient algorithm for finding all maximal frequent word sequences in a set of sentences. a word sequence s is considered frequent, if all its words occur in at least σ sentences and the words occur in each of these sentences in the same order as in s, given a frequency threshold σ. hence, the words of a sequence s do not have to occur consecutively in the sentences.
hyperthesis: the grna spell on the curse of bioinformatics applications integration. in this paper, we describe a graphical workflow management system called hyperthesis to address the challenges of integrating bioinformatics applications. hyperthesis is an integral component of the genomics research network architecture (grna). the grna was designed and developed to address the challenges of developing new bioinformatics applications. specifically, hyperthesis makes constructing workflows (pipelines of execution of applications) in the grna fast and intuitive for biologists and bio-programmers alike. it provides a large repository of interconnectable, parameterized workflow components for processing and relating diverse biological data and software programs. it also enables us to add new workflow components as new algorithms develop in ones area of interest. hyperthesis has been fully implemented using java.
modeling behavior, a step towards defining functionally correct views of complex objects in concurrent engineering. multidisciplinary concurrent engineering needs to model and manage different views of complex designs. previous attempts to address the problem of creating views of complex objects in object oriented database systems focus on the structure of complex objects; little attention is paid to how complex object behavior is effected when creating views. we believe that designing functionally correct behavior for a complex object should be a major consideration when defining a view to guarantee correctness of the derived classes.in this paper, we study the problem for designing functionally correct views of complex objects in concurrent engineering. view behavioral modeling requirements are presented. a behavior model that satisfies these requirements is presented. this model is demonstrated on an example complex object that represents process management.
multi-level operator combination in xml query processing. a core set of efficient access methods is central to the development of any database system. in the context of an xml database, there has been considerable effort devoted to defining a good set of primitive operators and inventing efficient access methods for each individual operator. these primitive operators have been defined either at the macro-level (using a "pattern tree" to specify a selection, for example) or at the micro-level (using multiple explicit containment joins to instantiate a single xpath expression).in this paper we argue that it is valuable to consider operations at each level. we do this through a study of operator merging: the development of a new access method to implement a combination of two or more primitive operators. it is frequently the case that access methods for merged operators are superior to a pipelined execution of separate access methods for each operator. we show operator merging to be valuable at both the micro-level and the macro-level. furthermore, we show that the corresponding merged operators are hard to reason with at the other level.specifically, we consider the influence of projections and set operations on pattern-based selections and containment joins. we show, through both analysis and extensive experimentation, the benefits of considering these operations all together. even though our experimental verification is only with a native xml database, we have reason to believe that our results apply equally to rdbms-based xml query engines.
coolcat: an entropy-based algorithm for categorical clustering. in this paper we explore the connection between clustering categorical data and entropy: clusters of similar poi lower entropy than those of dissimilar ones. we use this connection to design an incremental heuristic algorithm, coolcat, which is capable of efficiently clustering large data sets of records with categorical attributes, and data streams. in contrast with other categorical clustering algorithms published in the past, coolcat's clustering results are very stable for different sample sizes and parameter settings. also, the criteria for clustering is a very intuitive one, since it is deeply rooted on the well-known notion of entropy. most importantly, coolcat is well equipped to deal with clustering of data streams(continuously arriving streams of data point) since it is an incremental algorithm capable of clustering new points without having to look at every point that has been clustered so far. we demonstrate the efficiency and scalability of coolcat by a series of experiments on real and synthetic data sets.