waashk/dblp huggingface dataset:
polyhedral transformation for indexed rank order correlation queries. rank order correlation has been used extensively when the data is non-parametric or when the relationship between two variables is nonlinear and monotonic. in such cases, linear correlation measures, such as the product-moment coefficient, are inadequate and fail to detect correlative relations. we present a polyhedral indexing technique for rank order correlation queries for time series data. we use an interesting geometry interpretation of rank order correlation which lends itself to indexing by spatial indexes such as r-trees. our experimental results indicate one to two orders of magnitudes improvement over sequential scan - the only alternative solution.
high-dimensional descriptor indexing for large multimedia databases. in this paper we address the subject of large multimedia database indexing for content-based retrieval. we introduce multicurves, a new scheme for indexing high-dimensional descriptors. this technique, based on the simultaneous use of moderate-dimensional space-filling curves, has as main advantages the ability to handle high-dimensional data (100 dimensions and over), to allow the easy maintenance of the indexes (inclusion and deletion of data), and to adapt well to secondary storage, thus providing scalability to huge databases (millions, or even thousands of millions of descriptors). we use multicurves to perform the approximate k nearest neighbors search with a very good compromise between precision and speed. the evaluation of multicurves, carried out on large databases, demonstrates that the strategy compares well to other up-to-date k nearest neighbor search strategies. we also test multicurves on the real-world application of image identification for cultural institutions. in this application, which requires the fast search of a large amount of local descriptors, multicurves allows a dramatic speed-up in comparison to the brute-force strategy of sequential search, without any noticeable precision loss.
modeling and exploiting query interactions in database systems. the typical workload in a database system consists of a mixture of multiple queries of different types, running concurrently and interacting with each other. hence, optimizing performance requires reasoning about query mixes and their interactions, rather than considering individual queries or query types. in this paper, we show the significant impact that query interactions can have on workload performance. we present a new approach based on planning experiments and statistical modeling to capture the impact of query interactions. this approach requires no prior assumptions about the internal workings of the database system or the nature or cause of query interactions, making it portable across systems. as a concrete demonstration of the potential of capturing, modeling, and exploiting query interactions, we develop a novel interaction-aware query scheduler that targets report-generation workloads in business intelligence (bi) settings. under certain assumptions, the schedule found by this scheduler is within a constant factor of optimal. an experimental evaluation with tpc-h queries on ibm db2 demonstrates that our scheduler consistently outperforms (up to 4x) conventional schedulers that do not account for query interactions.
local approximation of pagerank and reverse pagerank. we consider the problem of approximating the pagerank of a target node using only local information provided by a link server. we prove that local approximation of pagerank is feasible if and only if the graph has low in-degree and admits fast pagerank convergence. while natural graphs, such as the web graph, are abundant with high in-degree nodes, making local pagerank approximation too costly, we show that reverse natural graphs tend to have low indegree while maintaining fast pagerank convergence. it follows that calculating reverse pagerank locally is frequently more feasible than computing pagerank locally. finally, we demonstrate the usefulness of reverse pagerank in five different applications.
predicting web spam with http session information. web spam is a widely-recognized threat to the quality and security of the web. web spam pages pollute search engine indexes, burden web crawlers and web mining services, and expose users to dangerous web-borne malware. to defend against web spam, most previous research analyzes the contents of web pages and the link structure of the web graph. unfortunately, these heavyweight approaches require full downloads of both legitimate and spam pages to be effective, making real-time deployment of these techniques infeasible for web browsers, high-performance web crawlers, and real-time web applications. in this paper, we present a lightweight, predictive approach to web spam classification that relies exclusively on http session information (i.e., hosting ip addresses and http session headers). concretely, we built an http session classifier based on our predictive technique, and by incorporating this classifier into http retrieval operations, we are able to detect web spam pages before the actual content transfer. as a result, our approach protects web users from web-propagated malware, and it generates significant bandwidth and storage savings. by applying our predictive technique to a corpus of almost 350,000 web spam instances and almost 400,000 legitimate instances, we were able to successfully detect 88.2% of the web spam pages with a false positive rate of only 0.4%. these classification results are superior to previous evaluation results obtained with traditional link-based and content-based techniques. additionally, our experiments show that our approach saves an average of 15.4 kb of bandwidth and storage resources for every successfully identified web spam page, while only adding an average of 101 microseconds to each http retrieval operation. therefore, our predictive technique can be successfully deployed in applications that demand real-time spam detection.
a method to predict social annotations. this paper predicts the stabilized tag set of a resource, with feedback of a small amount of user annotations, aiming to reduce the requirement of sufficient user annotations and to resolve the cold-start problem in a social annotation system.
active relevance feedback for difficult queries. relevance feedback has been demonstrated to be an effective strategy for improving retrieval accuracy. the existing relevance feedback algorithms based on language models and vector space models are not effective in learning from negative feedback documents, which are abundant if the initial query is difficult. the probabilistic retrieval model has the advantage of being able to naturally improve the estimation of both the relevant and non-relevant models. the dirichlet compound multinomial (dcm) distribution, which relies on hierarchical bayesian modeling techniques, is a more appropriate generative model for the probabilistic retrieval model than the traditional multinomial distribution. we propose a new relevance feedback algorithm, based on a mixture model of the dcm distribution, to effectively model the overlaps between the positive and negative feedback documents. consequently, the new algorithm improves the retrieval performance substantially for difficult queries. to further reduce human relevance evaluation, we propose a new active learning algorithm in conjunction with the new relevance feedback model. the new active learning algorithm implicitly models the diversity, density and relevance of unlabeled data in a transductive experimental design framework. experimental results on several trec datasets show that both the relevance feedback and active learning algorithm significantly improve retrieval accuracy.
shopsmart: product recommendations through technical specifications and user reviews. this paper describes a new method for providing recommendations tailored to a user's preferences using text mining techniques and online technical specifications of products. we first learn a model that can predict the price of a product given automatically-determined features describing technical specifications and users' opinions. we then use this model to rank a list of products based on individual users' preferences about various features. on a data set collected from amazon reviews and online technical specifications, rankings produced by this model rank the best product for a user in the 87th percentile of products in its category, on average. our approach outperforms several comparison systems by 21 percentiles or more.
an effective algorithm for mining 3-clusters in vertically partitioned data. conventional clustering algorithms group similar data points together along one dimension of a data table. bi-clustering simultaneously clusters both dimensions of a data table. 3-clustering goes one step further and aims to concurrently cluster two data tables that share a common set of row labels, but whose column labels are distinct. such clusters reveal the underlying connections between the elements of all three sets. we present a novel algorithm that discovers 3-clusters across vertically partitioned data. our approach presents two new and important formulations: first we introduce the notion of a 3-cluster in partitioned data; and second we present a mathematical formulation that measures the quality of such clusters. our algorithm discovers high quality, arbitrarily positioned, overlapping clusters, and is efficient in time. these results are exhibited in a comprehensive study on real datasets.
joke retrieval: recognizing the same joke told differently. in a corpus of jokes, a human might judge two documents to be the "same joke" even if characters, locations, and other details are varied. a given joke could be retold with an entirely different vocabulary while still maintaining its identity. since most retrieval systems consider documents to be related only when their word content is similar, we propose joke retrieval as a domain where standard language models may fail. other meaning-centric domains include logic puzzles, proverbs and recipes; in such domains, new techniques may be required to enable us to search effectively. for jokes, a necessary component of any retrieval system will be the ability to identify the "same joke," so we examine this task in both ranking and classification settings. we exploit the structure of jokes to develop two domain-specific alternatives to the "bag of words" document model. in one, only the punch lines, or final sentences, are compared; in the second, certain categories of words (e.g., professions and countries) are tagged and treated as interchangeable. each technique works well for certain jokes. by combining the methods using machine learning, we create a hybrid that achieves higher performance than any individual approach.
exploiting pipeline interruptions for efficient memory allocation. efficiency of memory-intensive operations is a key factor in obtaining good performance during multi-join query processing. the pipelined execution of these queries forces the operations in the query plan to be processed concurrently. making a wrong decision regarding the amount of memory allocated for such operations can have a drastic impact on the response time. however, some of the execution algorithms used at run time interrupt the pipelined execution, ensuring that some operations are never executed concurrently. because of this, it is essential to explore new approaches in order to improve memory exploitation. in this paper, we address the problem of memory allocation for multiple concurrent operations in a query execution plan. first, we study the dynamic needs for memory during the execution time, and define when two operations coexist. then, we propose a post-optimization phase, which (i) identifies the operations that are concurrently executed at run time and (ii) costs different memory allocation combinations to find a near optimal solution for any type of query execution plan. we have implemented our techniques in the ibm®db2® universal database" (db2 udb) showing that they achieve significant execution time improvements compared with previous approaches, especially for multi-join queries accessing large data volumes.
an algorithm to determine peer-reviewers. the peer-review process is the most widely accepted certification mechanism for officially accepting the written results of researchers within the scientific community. an essential component of peer-review is the identification of competent referees to review a submitted manuscript. this article presents an algorithm to automatically determine the most appropriate reviewers for a manuscript by way of a co-authorship network data structure and a relative-rank particle-swarm algorithm. this approach is novel in that it is not limited to a pre-selected set of referees, is computationally efficient, requires no human-intervention, and, in some instances, can automatically identify conflict of interest situations. a useful application of this algorithm would be to open commentary peer-review systems because it provides a weighting for each referee with respects to their expertise in the domain of a manuscript. the algorithm is validated using referee bid data from the 2005 joint conference on digital libraries.
scaling up duplicate detection in graph data. duplicate detection determines different representations of real-world objects in a database. recent research has considered the use of relationships among object representations to improve duplicate detection. in the general case where relationships form a graph, research has mainly focused on duplicate detection quality/effectiveness. scalability has been neglected so far, even though it is crucial for large real-world duplicate detection tasks. we scale up duplicate detection in graph data (ddg) to large amounts of data using the support of a relational database system. we first generalize the process of ddg and then present how to scale ddg in space (amount of data processed with limited main memory) and in time. finally, we explore how complex similarity computation can be performed efficiently. experiments on data an order of magnitude larger than data considered so far in ddg clearly show that our methods scale to large amounts of data.
clustering multi-way data via adaptive subspace iteration. clustering multi-way data is a very important research topic due to the intrinsic rich structures in real-world datasets. in this paper, we propose the subspace clustering algorithm on multi-way data, called asi-t (adaptive subspace iteration on tensor). asi-t is a special version of high order svd (hosvd), and it simultaneously performs subspace identification using 2dsvd and data clustering using k-means. the experimental results on synthetic data and real-world data demonstrate the effectiveness of asi-t.
a survey of pre-retrieval query performance predictors. the focus of research on query performance prediction is to predict the effectiveness of a query given a search system and a collection of documents. if the performance of queries can be estimated in advance of, or during the retrieval stage, specific measures can be taken to improve the overall performance of the system. in particular, pre-retrieval predictors predict the query performance before the retrieval step and are thus independent of the ranked list of results; such predictors base their predictions solely on query terms, the collection statistics and possibly external sources such as wordnet. in this poster, 22 pre-retrieval predictors are categorized and assessed on three different trec test collections.
cross-document cross-lingual coreference retrieval. in this work, we address coreference retrieval, which involves identifying aliases that are distinct references to an entity. we begin with a known alias and discover unknown aliases that refer to the same entity. we use entity language models to capture the contextual language around the known alias, which aids in finding new aliases. we also show that modeling the significant dates of the known aliases improves alias discovery performance.
exploiting temporal contexts in text classification. due to the increasing amount of information being stored and accessible through the web, automatic document classification (adc) has become an important research topic. adc usually employs a supervised learning strategy, where we first build a classification model using pre-classified documents and then use it to classify unseen documents. one major challenge in building classifiers is dealing with the temporal evolution of the characteristics of the documents and the classes to which they belong. however, most of the current techniques for adc do not consider this evolution while building and using the models. previous results show that the performance of classifiers may be affected by three different temporal effects (class distribution, term distribution and class similarity). further, it is shown that using just portions of the pre-classified documents, which we call contexts, for building the classifiers, result in better performance, as a consequence of the minimization of the aforementioned effects. in this paper we define the concept of temporal contexts as being the portions of documents that minimize those effects. we then propose a general algorithm for determining such contexts, discuss its implementation-related issues, and propose a heuristic that is able to determine temporal contexts efficiently. in order to demonstrate the effectiveness of our strategy, we evaluated it using two distinct collections: acm-dl and medline. we initially evaluated the reduction in terms of both the effort to build a classifier and the entropy associated with each context. further, we evaluated whether these observed reductions translate into better classification performance by employing a very simple classifier, majority voting. the results show that we achieved precision gains of up to 30% compared to a version that is not temporally contextualized, and the same accuracy of a state-of-the-art classifier (svm), while presenting an execution time up to hundreds of times faster.
exploiting context to detect sensitive information in call center conversations. protecting sensitive information while preserving the share-ability and usability of data is becoming increasingly important. in call-centers a lot of customer related sensitive information is stored in audio recordings. in this work, we address the problem of protecting sensitive information in audio recordings and speech transcripts. we present a semi-supervised method to model sensitive information as a directed graph. effectiveness of this approach is demonstrated by applying it to the problem of detecting and locating credit card transaction in real life conversations between agents and customers in a call center.
semi-supervised ranking aggregation. ranking aggregation is important in data mining and information retrieval. in this paper, we proposed a semi-supervised ranking aggregation method, in which the order of several item pairs are labeled as side information. the core idea is to learn a ranking function based on the ordering agreement of different rankers. the ranking scores assigned by this ranking function on the labeled data are consistent with the given pairwise order constraints while the ranking scores on the unlabeled data obey the intrinsic manifold structure of the rank items. the experiment results show our method work well.
a coarse-grain grid-based subspace clustering method for online multi-dimensional data streams. this paper proposes a subspace clustering algorithm which combines grid-based clustering with frequent itemset mining. given a d-dimensional data stream, the on-going distribution statistics of its data elements in every one-dimensional data space is monitored by a list of fine-grain grid-cells called a sibling list, so that all the one-dimensional clusters are accurately identified. by tracing a set of frequently co-occurred one-dimensional clusters, it is possible to find a coarse-grain dense rectangular space in a higher dimensional subspace. an st-tree is introduced to continuously monitor dense rectangular spaces in all the subspaces of the d dimensions. among the spaces, those ones whose densities are greater than or equal to a user defined minimum support threshold smin are corresponding to final clusters.
scalable complex pattern search in sequential data. searching data streams has been traditionally very limited, either in the complexity of the search or in the size of the searched dataset. in this paper, we investigate the design and optimization of constructs that enable sql to express complex patterns. in particular we propose the rsps (recursive sequential pattern search) algorithm which exploits the inter-dependencies between the elements of a sequential pattern to minimize repeated passes over the same data. performance gains derived experimental results show impressive speedup up to 100 times.
categorizing blogger's interests based on short snippets of blog posts. blogs have become an important medium for people to express opinions and share information on the web. predicting the interests of bloggers can be beneficial for information retrieval and knowledge discovery in the blogosphere. in this paper, we propose a two-layer classification model to categorize the interests of bloggers based on a set of short snippets collected from their blog posts. experiments were conducted on a list of bloggers collected from blog directories, with their snippets collected from google blog search. the results show that the proposed method is robust to errors in the lower level and achieve satisfactory performance in categorizing blogger's interests.
a framework for estimating complex probability density structures in data streams. probability density function estimation is a fundamental component in several stream mining tasks such as outlier detection and classification. the nonparametric adaptive kernel density estimate (akde) provides a robust and asymptotically consistent estimate for an arbitrary distribution. however, its extensive computational requirements make it difficult to apply this technique to the stream environment. this paper tackles the issue of developing efficient and asymptotically consistent akde over data streams while heeding the stringent constraints imposed by the stream environment. we propose the concept of local regions to effectively synopsize local density features, design a suite of algorithms to maintain the akde under a time-based sliding window, and analyze the estimates' asymptotic consistency and computational costs. in addition, extensive experiments were conducted with real-world and synthetic data sets to demonstrate the effectiveness and efficiency of our approach.
using the current browsing context to improve search relevance. in this paper, we investigate the problem of improving the relevance of a web search engine by adapting it to the dynamic needs of the user. we examine a representative case of sudden information need change, namely the exposure of the user to news data. in our earlier work we showed that the majority of queries submitted by users after browsing documents in the news domain are related to the most recently browsed document. we explore several methods of biasing the search by performing query expansion and re-ranking of the search results of a major search engine for queries identified as good candidates for contextualization. we show that these methods highly increase the similarity between the obtained top 10 search results and the most recently browsed document.
a novel email abstraction scheme for spam detection. prior studies on collaborative spam filtering with near-duplicate similarity matching scheme mainly represent each email by a succinct abstraction derived from email content text. since these abstractions of emails cannot fully catch the evolving nature of spams, we propose in this paper a novel email abstraction scheme, which considers email layout structure to represent emails. with the proposed abstraction, we design a near-duplicate matching scheme to efficiently match each incoming email with a huge spam database.