waashk/dblp huggingface dataset:
on lossy time decompositions of time stamped documents. constructing time decompositions of time stamped documents is an important first step in extracting temporal information from a document set. efficient algorithms are described for computing optimal lossy decompositions for a given document set, where the loss of information is constrained to be within a specified bound. a novel and efficient algorithm is proposed for computing information loss values required to construct optimal lossy decompositions. experimental results are reported comparing optimal lossy decompositions and equal length decompositions in terms of a number of parameters such as information loss. in particular, our results show that optimal lossy decompositions outperform equal length decompositions by preserving more of the information content of the underlying document set. the results also demonstrate that permitting even small amounts of variability in the length of the subintervals of a decomposition results in capturing more of the temporal information content of a document set when compared to equal length decompositions. this paper builds upon our earlier work on time decompositions where the problem of computing optimal lossy decomposition of the time period associated with a document set was first formulated.
determining the semantic orientation of terms through gloss classification. sentiment classification is a recent subdiscipline of text classification which is concerned not with the topic a document is about, but with the opinion it expresses. it has a rich set of applications, ranging from tracking users' opinions about products or about political candidates as expressed in online forums, to customer relationship management. functional to the extraction of opinions from text is the determination of the orientation of ``subjective'' terms contained in text, i.e. the determination of whether a term that carries opinionated content has a positive or a negative connotation. in this paper we present a new method for determining the orientation of subjective terms. the method is based on the quantitative analysis of the glosses of such terms, i.e. the definitions that these terms are given in on-line dictionaries, and on the use of the resulting term representations for semi-supervised term classification. the method we present outperforms all known methods when tested on the recognized standard benchmarks for this task.
topic-oriented collaborative crawling. a major concern in the implementation of a distributed web crawler is the choice of a strategy for partitioning the web among the nodes in the system. our goal in selecting this strategy is to minimize the overlap between the activities of individual nodes. we propose a topic-oriented approach, in which the web is partitioned into general subject areas with a crawler assigned to each. we examine design alternatives for a topic-oriented distributed crawler, including the creation of a web page classifier for use in this context. the approach is compared experimentally with a hash-based partitioning, in which crawler assignments are determined by hash functions computed over urls and page contents. the experimental evaluation demonstrates the feasibility of the approach, addressing issues of communication overhead, duplicate content detection, and page quality assessment.
future directions in data mining: streams, networks, self-similarity and power laws. how to spot abnormalities in a stream of temperature data from a sensor? or from a network of sensors? how does the internet look like? are there 'abnormal' sub-graphs in a given social network, possibly indicating, e.g., money-laundering rings?we present some recent work and list many remaining challenges for these two fascinating issues in data mining, namely, streams and networks. streams appear in numerous settings, in the form of, e.g., temperature readings, road traffic data, series of video frames for surveillance, patient physiological data. in all these settings, we want to equip the sensors with nimble, but powerful enough algorithms to look for patterns and abnormalities,<ol>(a) on a semi-infinite stream,(b) using finite memory, and (c) without human intervention.</ol.for networks, the applications are also numerous: social networks recording who knows/calls/emails whom; the internet itself, as well as the web, with routers and links, or pages and hyper-links; the genes and how they are related; customers and products they buy. in fact, any "many-to-many" database relationship eventually leads to a graph/network. in all these settings we want to find patterns and 'abnormalities'; the most central/important nodes; we also want to predict how the network will evolve; and we want to tackle huge graphs, with millions or billions of nodes and edges.as a promising direction towards these problems, we present some surprising tools from the theory of fractals, self-similarity and power laws. we show how the 'intrinsic' or 'fractal' dimension can help us find patterns, when traditional tools and assumptions fail. we show that self-similarity and power laws models work well in an impressive variety of settings, including real, bursty disk and web traffic; skewed distributions of click-streams; and multiple, real internet graphs.
mining gene expression datasets using density-based clustering. given the recent advancement of microarray technologies, we present a density-based clustering approach for the purpose of co-expressed gene cluster identification. the underlying hypothesis is that a set of co-expressed gene clusters can be used to reveal a common biological function. by addressing the strengths and limitations of previous density-based clustering approaches, we present a novel clustering algorithm that utilizes a neighborhood defined by <i>k</i>-nearest neighbors. experimental results indicate that the proposed method identifies biologically meaningful and co-expressed gene clusters.
composable xml integration grammars. the proliferation of xml as a standard for data representation and exchange in diverse, next-generation web applications has created an emphatic need for effective xml data-integration tools. for several real-life scenarios, such xml data integration needs to be <i>dtd-directed</i> -- in other words, the target, integrated xml database must conform to a prespecified, user- or application-defined dtd. in this paper, we propose a novel formalism, <i>xml integration grammars (xigs)</i>, for specifying dtd-directed integration of xml data. abstractly, an xig maps data from multiple xml sources to a target xml document that conforms to a predefined dtd. an xig extracts source xml data via queries expressed in a fragment of xquery, and controls target document generation with tree-valued attributes and the target dtd. the novelty of xigs consists in not only their automatic support for dtd-conformance but also in their: an xig may embed local and remote xigs in its definition, and invoke these xigs during its evaluation. this yields an important modularity property for our xigs that allows one to divide a complex integration task into manageable sub-tasks and conquer each of them separately. to efficiently evaluate xigs we provide algorithms for merging xml queries in an xig and for scheduling queries and embedded xigs. these lead to an effective framework, as well as a design tool for xquery, for effectively specifying and computing complex, dtd-directed xml integration.
a novel approach for privacy-preserving video sharing. to support privacy-preserving video sharing, we have proposed a novel framework that is able to protect the video content privacy at the individual video clip level and prevent statistical inferences from video collections. to protect the video content privacy at the individual video clip level, we have developed an effective algorithm to automatically detect privacy-sensitive video objects and video events. to prevent the statistical inferences from video collections, we have developed a distributed framework for privacy-preserving classifier training, which is able to significantly reduce the costs of data transmission and reliably limit the privacy breaches by determining the optimal size of blurred test samples for classifier validation. our experiments on a specific domain of patient training and counseling videos show convincing results.
thematic mapping - from unstructured documents to taxonomies. verity inc. has developed a comprehensive suite of tools for accurately and efficiently organizing enterprise content which involves four basic steps: (i) creating taxonomies, (ii) building classification models, (iii) populating taxonomies with documents, and (iv) deploying populated taxonomies in enterprise portals. a taxonomy is a hierarchical representation of categories. a taxonomy provides a navigation structure for exploring and understanding the underlying corpus without sifting through a huge volume of documents. thematic mapping automatically discovers a concept tree from a corpus of unstructured documents and assigns meaningful labels to concepts based on a semantic network. integrating with verity intelligent classifier's user-friendly gui, a user can drill down a concept tree for navigation, perform a conceptual search to retrieve documents pertaining to a concept, build a taxonomy from the concept tree, as well as edit a taxonomy to tailor it into various views (customized taxonomies) of the same corpus. classification rules can be generated automatically from concepts. these classification rules can be used for populating documents into the taxonomy.
augeas: authoritativeness grading, estimation, and sorting. when searching for content in in a large heterogeneous document collections like the world wide web it is not easy to know which documents provide reliable authoritative information about a subject. the problem is particularly pointed as it concerns content search for "high-value" informational needs such as retrieving medical information, where the cost of error may be high. in this paper, a method is described for estimating the authoritativeness of a document based on textual, non-topical cues. this method is complementary to estimates of authoritativeness based on link structure, such as the pagerank and hits algorithms. this method is particularly suited to "high-value" content search where the user is interested in searching for information about a specific topic. a method for combining textual estimates of authoritativeness with link analysis is also presented. the types of textual cues to authoritativeness that are easily computed and utilized by our method are described, as well as the method used to select a subset of cues to increase the computation speed. methods for applying authoritativeness estimates to re-ranking documents returned from search engines, combining textual authoritativeness with social authority, and use in query expansion are also presented. by combining textual authority with link analysis, a more complete and robust estimate can be made of a document's authoritativeness.
summarization of discussion groups. in this paper, we describe an algorithm to generate textual summaries of discussion groups. our system combines sentences extracted from individual postings into variable-length summaries by utilizing the hierarchical discourse context provided by discussion threads. we have incorporated this algorithm into a web-based application called ids (interactive discussion summarizer).
approximating the top-m passages in a parallel question answering system. we examine the problem of retrieving the top-<i>m</i> ranked items from a large collection, randomly distributed across an <i>n</i>-node system. in order to retrieve the top <i>m</i> overall, we must retrieve the top <i>m</i> from the subcollection stored on each node and merge the results. however, if we are willing to accept a small probability that one or more of the top-<i>m</i> items may be missed, it is possible to reduce computation time by retrieving only the top <i>k < m</i> from each node. in this paper, we demonstrate that this simple observation can be exploited in a realistic application to produce a substantial efficiency improvement without compromising the quality of the retrieved results. to support our claim, we present a statistical model that predicts the impact of the optimization. the paper is structured around a specific application~---~passage retrieval for question answering~---~but the primary results are more broadly applicable.
a reliable storage management layer for distributed information retrieval systems. we present a storage management layer that facilitates the implementation of parallel information retrieval systems, and related applications, on networks of workstations. the storage management layer automates the process of adding and removing nodes, and implements a dispersed mirroring strategy to improve reliability. when nodes are added and removed, the document collection managed by the system is redistributed for load balancing purposes. the use of dispersed mirroring minimizes the impact of node failures and system modifications on query performance.
query processing of streamed xml data. we are addressing the efficient processing of continuous xml streams, in which the server broadcasts xml data to multiple clients concurrently through a multicast data stream, while each client is fully responsible for processing the stream. in our framework, a server may disseminate xml fragments from multiple documents in the same stream, can repeat or replace fragments, and can introduce new fragments or delete invalid ones. a client uses a light-weight database based on our proposed xml algebra to cache stream data and to evaluate xml queries against these data. the synchronization between clients and servers is achieved through annotations and punctuations transmitted along with the data streams. we are presenting a framework for processing xml queries in xquery form over continuous xml streams. our framework is based on a novel xml algebra and a new algebraic optimization framework based on query decorrelation, which is essential for non-blocking stream processing.
a domain independent environment for creating information extraction modules. text-mining is a growing area of interest within the field of data mining and knowledge discovery. given a collection of text documents, most approaches to text mining perform knowledge-discovery operations either on external tags associated with each document, or on the set of all words within each document. both approaches suffer from limitations. this paper focuses on an intermediate approach, one that we call text mining via information extraction, in which knowledge discovery takes place on focused, relevant terms, phrases and facts, as extracted from the documents.
interconnection semantics for keyword search in xml. a framework for describing semantic relationships among nodes in xml documents is presented. in contrast to earlier work, the xml documents may have id references (i.e., they correspond to graphs and not just trees). a specific interconnection semantics in this framework can be defined explicitly or derived automatically. the main advantage of interconnection semantics is the ability to pose queries on xml data in the style of keyword search. several methods for automatically deriving interconnection semantics are presented. the complexity of the evaluation and the satisfiability problems under the derived semantics is analyzed. for many important cases, the complexity is tractable and hence, the proposed interconnection semantics can be efficiently applied to real-world xml documents.
automatic construction of multifaceted browsing interfaces. databases of text and text-annotated data constitute a significant fraction of the information available in electronic form. searching and browsing are the typical ways that users locate items of interest in such databases. interfaces that use multifaceted hierarchies represent a new powerful browsing paradigm which has been proven to be a successful complement to keyword searching. thus far, multifaceted hierarchies have been created manually or semi-automatically, making it difficult to deploy multifaceted interfaces over a large number of databases. we present automatic and scalable methods for creation of multifaceted interfaces. our methods are integrated with traditional relational databases and can scale well for large databases. furthermore, we present methods for selecting the best portions of the generated hierarchies when the screen space is not sufficient for displaying all the hierarchy at once. we apply our technique to a range of large data sets, including annotated images, television programming schedules, and web pages. the results are promising and suggest directions for future research.
query expansion using random walk models. it has long been recognized that capturing term relationships is an important aspect of information retrieval. even with large amounts of data, we usually only have significant evidence for a fraction of all potential term pairs. it is therefore important to consider whether multiple sources of evidence may be combined to predict term relations more accurately. this is particularly important when trying to predict the probability of relevance of a set of terms given a query, which may involve both lexical and semantic relations between the terms.we describe a markov chain framework that combines multiple sources of knowledge on term associations. the stationary distribution of the model is used to obtain probability estimates that a potential expansion term reflects aspects of the original query. we use this model for query expansion and evaluate the effectiveness of the model by examining the accuracy and robustness of the expansion methods, and investigate the relative effectiveness of various sources of term evidence. statistically significant differences in accuracy were observed depending on the weighting of evidence in the random walk. for example, using co-occurrence data later in the walk was generally better than using it early, suggesting further improvements in effectiveness may be possible by learning walk behaviors.
improved string matching under noisy channel conditions. many document-based applications, including popular web browsers, email viewers, and word processors, have a 'find on this page' feature that allows a user to find every occurrence of a given string in the document. if the document text being searched is derived from a noisy process such as optical character recognition (ocr), the effectiveness of typical string matching can be greatly reduced. this paper describes an enhanced string-matching algorithm for degraded text that improves recall, while keeping precision at acceptable levels. the algorithm is more general than most approximate matching algorithms and allows string-to-string edits with arbitrary costs. we develop a method for evaluating our technique and use it to examine the relative effectiveness of each sub-component of the algorithm. of the components we varied, we find that using confidence information from the recognition process lead to the largest improvements in matching accuracy.
scalable ranking for preference queries. top-k preference queries with multiple attributes are critical for decision-making applications. previous research has concentrated on improving the computational efficiency mainly by using novel index structures and search strategies. since current applications need to scale to terabytes of data and thousands of users, performance of such systems is strongly impacted by the amount of available memory. this paper proposes a scalable approach for memory-bounded top-k query processing.
exploiting redundancy in sensor networks for energy efficient processing of spatiotemporal region queries. sensor networks are made of autonomous devices that are able to collect, store, process and share data with other devices. spatiotemporal region queries can be used for retrieving information of interest from such networks. such queries require the answers only from the subset of the network nodes that fall into the query region. if the network is redundant in the sense that the measurements of some nodes can be substituted by those of other nodes with a certain degree of confidence, then a much smaller subset of nodes may be sufficient to answer the query at a lower energy cost. we investigate how to take advantage of such data redundancy and propose two techniques to process spatiotemporal region queries under these conditions. our techniques reduce up to twenty times the energy cost of query processing compared to the typical network flooding, thus prolonging the lifetime of the sensor network.
mining inter-transaction associations with templates. multi-dimensional, inter-transaction association rules extend the traditional association rules to describe more general associations among items with multiple properties cross transactions. &ldquo;after mcdonald and burger king open branches, kfc will open a branch two months later and one mile away&rdquo; is an example of such rules. since the number of potential inter-transaction association rules tends to be extremely large, mining inter-transaction associations poses more challenges on efficient processing than mining intra-transaction associations. in order to make such association mining truly practical and computationally tractable, in this study, we present a template model to help users declare the interesting inter-transaction associations to be mined. with the guidance of templates, several optimization techniques are devised to speed up the discovery of inter-transaction association rules. we show, through a series of experiments, that these optimization techniques can yield significant performance benefits.
automatic recognition of distinguishing negative indirect history language in judicial opinions. we describe a model-based filtering application that generates candidate case-to-case distinguishing citations. we developed the system to aid editors in identifying indirect relationships among judicial opinions in a database of over 5 million documents. using a training collection of approximately 30,000 previously edited cases, the filter application provides ranked sets of textual evidence for current case law documents in the editorial process. these sets contain judicial language with a strong probability of containing distinguishing relationships. integrating this application into the editorial review environment has greatly improved the coverage and efficiency of the work flow to identify and generate new distinguishing relationship entries.
efficient processing of conical queries. conical queries are a novel type of query with an increasing number of applications. traditional index structures and retrieval mechanisms, in general, have been optimized for rectangular and circular queries, rather than conical queries. in this paper, we focus on conical queries which can be defined as a multi-dimensional cone in a multi-dimensional data space. we develop a model for expressing such queries and suggest efficient techniques for evaluating them. in particular, we explore the retrieval problem in the context of conical query processing and develop multi-disk allocation methods specifically for processing conical queries.