waashk/dblp huggingface dataset:
margin-based local regression for adaptive filtering. adaptive information filtering is an open challenge in information retrieval. one of the tough issues is the optimization of decision thresholds over time, based on partial relevance feedback on the system-retrieved documents in chronological order. we developed a new approach, namely margin-based local regression, that automatically adjusts the thresholds based on a sliding window over the truly positive examples for which the system predicted "yes" with respect to a particular class, and a second sliding window over the other documents being processed by the system. using the means of the scores of the documents in the two windows, we monitor the temporal drifting of the margin that is a function of both the current classification model and the threshold calibration strategy, and that suggests the bounds for the optimal threshold at a given time. examining this approach together with a rocchio-style classifier on the trec 2001 and trec 2002 benchmark data sets in adaptive filtering, we obtained significant improvements in performance (measured using fβ=0.5) over the baseline system that did not adapt the threshold over time, and the best result ever reported on the trec 2002 benchmark corpus for adaptive filtering evaluations. these empirical results suggest that it is important to use both system-accepted and system-rejected documents to optimize thresholds instead of just using system-accepted documents alone, as well as to make the thresholding function temporally sensitive to the shifting centroids of on-topic and off-topic documents.
finding highly correlated pairs efficiently with powerful pruning. we consider the problem of finding highly correlated pairs in a large data set. that is, given a threshold not too small, we wish to report all the pairs of items (or binary attributes) whose (pearson) correlation coefficients are greater than the threshold. correlation analysis is an important step in many statistical and knowledge-discovery tasks. normally, the number of highly correlated pairs is quite small compared to the total number of pairs. identifying highly correlated pairs in a naive way by computing the correlation coefficients for all the pairs is wasteful. with massive data sets, where the total number of pairs may exceed the main-memory capacity, the computational cost of the naive method is prohibitive. in their kdd'04 paper [15], hui xiong et al. address this problem by proposing the taper algorithm. the algorithm goes through the data set in two passes. it uses the first pass to generate a set of candidate pairs whose correlation coefficients are then computed directly in the second pass. the efficiency of the algorithm depends greatly on the selectivity (pruning power) of its candidate-generating stage.in this work, we adopt the general framework of the taper algorithm but propose a different candidate-generation method. for a pair of items, taper's candidate-generation method considers only the frequencies (supports) of individual items. our method also considers the frequency (support) of the pair but does not explicitly count this frequency (support). we give a simple randomized algorithm whose false-negative probability is negligible. the space and time complexities of generating the candidate set in our algorithm are asymptotically the same as taper's. we conduct experiments on synthesized and real data. the results show that our algorithm produces a greatly reduced candidate set - one that can be several orders of magnitude smaller than that generated by taper. because of this, our algorithm uses much less memory and can be faster. the former is critical for dealing with massive data.
information retrieval from relational databases using semantic queries. relational databases are widely used today as a mechanism for providing access to structured data. they, however, are not suitable for typical information finding tasks of end users. there is often a semantic gap between the queries users want to express and the queries that can be answered by the database. in this paper, we propose a system that bridges this semantic gap using domain knowledge contained in ontologies. our system extends relational databases with the ability to answer semantic queries that are represented in sparql, an emerging semantic web query language. users express their queries in sparql, based on a semantic model of the data, and they get back semantically relevant results. we define different categories of results that are semantically relevant to the users' query and show how our system retrieves these results. we evaluate the performance of our system on sample relational databases, using a combination of standard and custom ontologies.
on the complexity of schema inference from web pages in the presence of nullable data attributes. an increasingly large number of web pages are machine-generated by filling in templates with data stored in backend databases. these templates can be viewed as the implicit schemas of those web pages. the ability to infer the implicit schema from a collection of web pages is important for scalable data extraction, since the inferred schema can be used to automatically identify schema attributes that are "encoded" in web pages.however, the task of inferring a "good" schema is complicated due to the existence of nullable (missing) data attributes. usually if an attribute contains a null value, then it will be omitted in the generated web page, giving rise to different variations and permutations of layout structures in web pages that are generated from the same template.in this paper we investigate the complexity of schema inference from web pages in the presence of nullable data attributes. we introduce the notion of unambiguity as a quality measure for inferred schemas and prove that the problem of inferring "good" (unambiguous) schemas is np-complete. our complexity results imply that ambiguity resolution is one of the root causes of the computational difficulty underlying schema inference from web pages.
salsa: computing the skyline without scanning the whole sky. skyline queries compute the set of pareto-optimal tuples in a relation, ie those tuples that are not dominated by any other tuple in the same relation. although several algorithms have been proposed for efficiently evaluating skyline queries, they either require to extend the relational server with specialized access methods (which is not always feasible) or have to perform the dominance tests on all the tuples in order to determine the result. in this paper we introduce salsa (sort and limit skyline algorithm), which exploits the sorting machinery of a relational engine to order tuples so that only a subset of them needs to be examined for computing the skyline result. this makes salsa particularly attractive when skyline queries are executed on top of systems that do not understand skyline semantics or when the skyline logic runs on clients with limited power and/or bandwidth.
in search of meaning for time series subsequence clustering: matching algorithms based on a new distance measure. recent papers have claimed that the result of k-means clustering for time series subsequences (sts clustering) is independent of the time series that created it. our paper revisits this claim. in particular, we consider the following question: given several time series sequences and a set of sts cluster centroids from one of them (generated by the k-means algorithm), is it possible to reliably determine which of the sequences produced these cluster centroids? while recent results suggest that the answer should be no, we answer this question in the affirmative.we present cluster shape distance, an alternate distance measure for time series subsequence clusters, based on cluster shapes. given a set of clusters, its shape is the sorted list of the pairwise euclidean distances between their centroids. we then present two algorithms based on this distance measure, which match a set of sts cluster centroids with the time series that produced it. while the first algorithm creates dqg reuse this term more smaller "fingerprints" for the sequences, the second is more accurate. in our experiments with a dataset of 10 sequences, it produced a correct match 100% of the time.furthermore, we offer an analysis that explains why our cluster shape distance provides a reliable way to match sts clusters to the original sequences, whereas cluster set distance fails to do so. our work establishes for the first time a strong relation between the result of k-means sts clustering and the time series sequence that created it, despite earlier predictions that this is not possible.
efficient data access to multi-channel broadcast programs. this paper studies fast access to data that are broadcast on multiple channels. broadcast is a useful data dissemination technique because of its scalability, but is lacking when it comes to response time. increasing the number of available broadcast channels is a logical way of increasing throughput. little work, however, has considered the access structures necessary for making effective use of the additional channels. we propose various indexing schemes for a multi-channel broadcast program. we demonstrate the effectiveness of our techniques in decreasing response time and tuning time via extensive experiments over a wide range of parameters.
mining compressed commodity workflows from massive rfid data sets. radio frequency identification (rfid) technology is fast becoming a prevalent tool in tracking commodities in supply chain management applications. the movement of commodities through the supply chain forms a gigantic workflow that can be mined for the discovery of trends, flow correlations and outlier paths, that in turn can be valuable in understanding and optimizing business processes.in this paper, we propose a method to construct compressed probabilistic workflows that capture the movement trends and significant exceptions of the overall data sets, but with a size that is substantially smaller than that of the complete rfid workflow. compression is achieved based on the following observations: (1) only a relatively small minority of items deviate from the general trend, (2)only truly non-redundant deviations, ie, those that substantially deviate from the previously recorded ones, are interesting, and (3) although rfid data is registered at the primitive level, data analysis usually takes place at a higher abstraction level. techniques for workflow compression based on non-redundant transition and emission probabilities are derived; and an algorithm for computing approximate path probabilities is developed. our experiments demonstrate the utility and feasibility of our design, data structure, and algorithms.
an rsa-based time-bound hierarchical key assignment scheme for electronic article subscription. the time-bound hierarchical key assignment problem is to assign time sensitive keys to security classes in a partially ordered hierarchy so that legal data accesses among classes can be enforced. two time-bound hierarchical key assignment schemes have been proposed in the literature, but both of them were proved insecure against collusive attacks. in this paper, we will propose an rsa-based time-bound hierarchical key assignment scheme and describe its possible application. the security analysis shows that the new scheme is safe against the collusive attacks.
multi-task text segmentation and alignment based on weighted mutual information. text segmentation is important for text analysis, while text alignment is to determine shared sub-topics among similar documents. multi-task text segmentation and alignment is the extension of single-task segmentation to utilize information of multi-source documents. in this paper we introduce a novel domain-independent unsupervised method for multi-task segmentation and alignment based on the idea that the optimal segmentation and alignment maximizes weighted mutual information, mutual information with term weights. the experiment results show that our approach works well.
using domain knowledge in knowledge discovery. with the explosive growth of the size of databases, many knowledge discovery applications deal with large quantities of data. there is an urgent need to develop methodologies which will allow the applications to focus search to a potentially interesting and relevant portion of the data, which can reduce the computational complexity of the knowledge discovery process and improve the interestingness of discovered knowledge. previous work on semantic query optimization, which is an approach to take advantage of domain knowledge for query optimization, has demonstrated that significant cost reduction can be achieved by reformulating a query into a less expensive yet equivalent query which produces the same answer as the original one. in this paper, we introduce a method to utilize three types of domain knowledge in reducing the cost of finding a potentially interesting and relevant portion of the data while improving the quality of discovered knowledge. in addition, we propose a method to select relevant domain knowledge without an exhaustive search of all domain knowledge. the contribution of this paper is that we lay out a general framework for using domain knowledge in the knowledge discovery process effectively by providing guidelines.
intelligent query answering in deductive and object-oriented databases. in the near future, we believe that we will need much more sophisticated answer-finding schemes in an object-oriented database in order to satisfy the needs of truly intelligent information system. in this paper, we introduce a method to apply the intensional query processing techniques of deductive databases to object-oriented databases. so, we can generate intensional answers to represent answer-set abstractly for a given query in object-oriented databases.our approach consists of four steps: rule generation, pre-resolution, resolution, and post-resolution. in rule generation, we generate a set of deductive rules based on an object-oriented database schema. in pre-resolution, rule transformation is done to get unique intensional literals and extended term-restricted rules. in resolution, we identify rules that are potentially relevant to a query. in post-resolution, we find relevant resolvents as candidates for intensional answers among potentially relevant resolvents. we also use the notion of potentially relevant resolvents and relevant resolvents to avoid generating certain meaningless intensional answers.
query result ranking over e-commerce web databases. to deal with the problem of too many results returned from an e-commerce web database in response to a user query, this paper proposes a novel approach to rank the query results. based on the user query, we speculate how much the user cares about each attribute and assign a corresponding weight to it. then, for each tuple in the query result, each attribute value is assigned a score according to its "desirableness" to the user. these attribute value scores are combined according to the attribute weights to get a final ranking score for each tuple. tuples with the top ranking scores are presented to the user first. our ranking method is domain independent and requires no user feedback. experimental results demonstrate that this ranking method can effectively capture a user's preferences.
an approximate multi-word matching algorithm for robust document retrieval. document generation from low level data and its utilization is one of the most challenging tasks in document engineering. word occurrence detection is a fundamental problem in the recognized document utilization obtained by a recognizer, such as ocr and speech recognition. given a set of words, such as a dictionary, this paper proposes an efficient dynamic programming (dp) algorithm to find the occurrences of each word in a text. in this paper, the string similarity is measured by a statistical similarity model that enables a definition of the similarities in the character level as well as edit operation level. the proposed algorithm uses tree structures to measure similarities in order to avoid measuring similarities of the same substrings appearing in different parts of the text and words. the time complexity of the proposed algorithm is o(|w|⋅|s|⋅|q|), where |w| (resp. |s|) denote the number of nodes in the trees representing the word set (resp. the text), and |q| donotes the number of the states of the model used for string similarity. this paper shows the proposed algorithm is experimentally about six times faster than a naive dp algorithm.
out-of-context noun phrase semantic interpretation with cross-linguistic evidence. the acquisition of semantic knowledge is paramount for any application that requires a deep understanding of natural language text. motivated by the problem of building a noun phrase-level semantic parser and adapting it to various applications, such as machine translation and multilingual question answering, in this paper we present a domain-independent model for noun phrase semantic interpretation. we investigate the problem based on cross-linguistic evidence from a set of four romance languages: spanish, italian, french, and romanian. the focus on romance languages is well motivated. it is generally the case that english noun phrases translate into constructions of the form "n p n" in romance languages where, as we will show, the p (preposition) varies in ways that correlate with the semantics. thus, based on a set of 22 semantic interpretation categories (such as part-whole, agent, possession) we present empirical observations regarding the distribution of these semantic categories in a cross-lingual corpus and their mapping to various syntactic constructions in english and romance. furthermore, given a training set of english noun phrases along with their translations in the four romance languages, our algorithm automatically learns classification rules and applies them to unseen noun phrase instances for semantic interpretation. experimental results are compared against a state-of-the-art model reported in the literature.
translation enhancement: a new relevance feedback method for cross-language information retrieval. as an effective technique for improving retrieval effectiveness, relevance feedback (rf) has been widely studied in both monolingual and cross-language information retrieval (clir) settings. the studies of rf in clir have been focused on query expansion (qe), in which queries are reformulated before and/or after they are translated. however, rf in clir actually not only can help select better query terms, but also can enhance query translation by adjusting translation probabilities and even resolve some out-of-vocabulary terms. in this paper, we propose a novel rf method called translation enhancement (te), which uses the extracted translation relationships from relevant documents to revise the translation probabilities of query terms and to identify extra translation alternatives if available so that the translated queries are more tuned to the current search. we studied te using pseudo relevance feedback (prf) and interactive relevance feedback (irf). our results show that te can significantly improve clir with both types of rf methods, and that the improvement is comparable to that of qe. more importantly, the effects of te and qe are complementary. their integration can produce further improvement, and makes clir more robust for a variety of queries.
utility scoring of product reviews. we identify a new task in the ongoing research in text sentiment analysis: predicting utility of product reviews, which is orthogonal to polarity classification and opinion extraction. we build regression models by incorporating a diverse set of features, and achieve highly competitive performance for utility scoring on three real-world data sets.
a dual-view approach to interactive network visualization. visualizing network data, from tree structures to arbitrarily connected graphs, is a difficult problem in information visualization. a large part of the problem is that in network data, users not only have to visualize the attributes specific to each data item, but also the links specifying how those items are connected to each other. past approaches to resolving these difficulties focus on zooming, clustering, filtering and applying various methods of laying out nodes and edges. such approaches, however, focus only on optimizing a network visualization in a single view, limiting the amount of information that can be shown and explored in parallel. moreover, past approaches do not allow users to cross reference different subsets or aspects of large, complex networks. in this paper, we propose an approach to these limitations using multiple coordinated views of a given network. to illustrate our approach, we implement a tool called dualnet and evaluate the tool with a case study using an email communication network. we show how using multiple coordinated views improves navigation and provides insight into large networks with multiple node and link properties and types.
semi-automatic annotation and mpeg-7 authoring of dance videos. this paper presents a system (danvideo) that is implemented using j2se and jmf to annotate manually the macro and micro features of the dance videos by the dance experts. as mpeg-7 has reached a matured state for the description of the multimedia structure and semantics through the descriptors and description schemes, danvideo generates a mpeg-7 instance that conforms to the mpeg-7 schema, semi-automatically and effortlessly from the dance annotations.
towards efficient search on unstructured data: an intelligent-storage approach. applications that create and consume unstructured data have grown both in scale of storage requirements and complexity of search primitives. we consider two such applications: exhaustive search and integration of structured and unstructured data. current block-based storage systems are either incapable or inefficient to address the challenges bought forth by the above applications. we propose a storage framework to efficiently store and search unstructured and structured data while controlling storage management costs. experimental results based on our prototype show that the proposed system can provide impressive performance and feature benefits.
representing documents with named entities for story link detection (sld). several information organization, access, and filtering systems can benefit from different kind of document representations than those used in traditional information retrieval (ir). topic detection and tracking (tdt) is an example of such an application. in this paper we demonstrate that named entities serve as better choices of units for document representation over all words. in order to test this hypothesis we study the effect of words-based and entity-based representations on story link detection (sld) - a core task in tdt research. the experiments on tdt corpora show that entity-based representations give significant improvements for sld. we also propose a mechanism to expand the set of named entities used for document representation, which enhances the performance in some cases. we then take a step further and analyze the limitations of using only named entities for the document representation. our studies and experiments indicate that adding additional topical terms can help in addressing such limitations.
language models, probability of relevance and relevance likelihood. this paper proposes a measure of relevance likelihood derived specifically for language models. such a measure may be used to guide a user on how far to browse through the list of retrieved items or for pseudo-relevance feedback. to derive this measure, it is necessary to make the assumption that a user is seeking an ideal (usually non-existent) document and the actual relevant documents in the collection will contain fragments of this ideal document. thus, in deriving this measure we propose a novel way of capturing relevance in language modelling.