waashk/dblp huggingface dataset:
very efficient mining of distance-based outliers. in this work a novel algorithm, named dolphin, for detecting distance-based outliers is presented. the proposed algorithm performs only two sequential scans of the dataset. it needs to store into main memory a portion of the dataset, to efficiently search for neighbors and early prune inliers. the strategy pursued by the algorithm allows to keep this portion very small. both theoretical justification and empirical evidence that the size of the stored data amounts only to a few percent of the dataset are provided. another important feature of dolphin is that the memory-resident data are indexed by using a suitable proximity search approach. this allows to search for nearest neighbors looking only at a small subset of the main memory stored data. temporal and spatial cost analysis show that the novel algorithm achieves both near linear cpu and i/o cost. dolphin has been compared with state of the art methods, showing that it outperforms existing ones.
efficient mining of max frequent patterns in a generalized environment. this poster paper summarizes our solution for mining max frequent generalized itemsets (g-itemsets), a compact representation for frequent patterns in the generalized environment.
search result summarization and disambiguation via contextual dimensions. topic hierarchies are a popular method of summarizing the results obtained in response to a query in various search applications. however, topic hierarchies are rigid when they are pre-defined and somewhat unintuitive when they are dynamically generated by statistical techniques. in this paper, we propose an alternative approach to query disambiguation and result summarization by placing the results in set of contextual dimensions which can be viewed as facets. for the generic search scenario, we illustrate our approach by using three types of contextual dimensions, namely, concepts, features, and specializations. we use nlp techniques and a data mining algorithm to select distinct contexts.
efficient lca based keyword search in xml data. keyword search in xml documents based on the notion of lowest common ancestors (lcas) and modifications of it has recently gained research interest [2, 3, 4]. in this paper we propose an efficient algorithm called indexed stack to find answers to keyword queries based on xrank's semantics to lca [2]. the complexity of the indexed stack algorithm is o(kd|s1|\log|s|) where k is the number of keywords in the query, d is the depth of the tree and |s1 | (|s|) is the occurrence of the least (most) frequent keyword in the query. in comparison, the best worst case complexity of the core algorithms in [2] is o(kd|s|). we analytically and experimentally evaluate the indexed stack algorithm and the two core algorithms in [2]. the results show that the indexed stack algorithm outperforms in terms of both cpu and i/o costs other algorithms by orders of magnitude when the query contains at least one low frequency keyword along with high frequency keywords.
efficient processing of complex similarity queries in rdbms through query rewriting. multimedia and complex data are usually queried by similarity predicates. whereas there are many works dealing with algorithms to answer basic similarity predicates, there are not generic algorithms able to efficiently handle similarity complex queries combining several basic similarity predicates. in this work we propose a simple and effective set of algorithms that can be combined to answer complex similarity queries, and a set of algebraic rules useful to rewrite similarity query expressions into an adequate format for those algorithms. those rules and algorithms allow relational database management systems to turn complex queries into efficient query execution plans. we present experiments that highlight interesting scenarios. they show that the proposed algorithms are orders of magnitude faster than the traditional similarity algorithms. moreover, they are linearly scalable considering the database size.
designing clustering-based web crawling policies for search engine crawlers. the world wide web is growing and changing at an astonishing rate. web information systems such as search engines have to keep up with the growth and change of the web. due to resource constraints, search engines usually have difficulties keeping the local database completely synchronized with the web. in this paper, we study how tomake good use of the limited system resource and detect as many changes as possible. towards this goal, a crawler for the web search engine should be able to predict the change behavior of the webpages. we propose applying clustering-based sampling approach. specifically, we first group all the local webpages into different clusters such that each cluster contains webpages with similar change pattern. we then sample webpages from each cluster to estimate the change frequency of all the webpages in that cluster. finally, we let the crawler re-visit the cluster containing webpages with higher change frequency with a higher probability. to evaluate the performance of an incremental crawler for a web search engine, we measure both the freshness and the quality of the query results provided by the search engine. we run extensive experiments on a real web data set of about 300,000 distinct urls distributed among 210 websites. the results demonstrate that our clustering algorithm effectively clusters the pages with similar change patterns, and our solution significantly outperforms the existing methods in that it can detect more changed webpages and improve the quality of the user experience for those who query the search engine.
investigating the exhaustivity dimension in content-oriented xml element retrieval evaluation. inex, the evaluation initiative for content-oriented xml retrieval, has since its establishment defined the relevance of an element according to two graded dimensions, exhaustivity and specificity. the former measures how exhaustively an xml element discusses the topic of request, whereas specificity measures how focused the element is on the topic of request. the reason for having two dimensions was to provide a more stable measure of relevance than if assessors were asked to rate the relevance of an element on a single scale. however, obtaining relevance assessments is a costly task. as each document must be assessed for relevance by a human assessor. in xml retrieval this problem is exacerbated as the elements of the document must also be assessed with respect to the exhaustivity and specificity dimensions. a continuous discussion in inex has been whether such a sophisticated definition of relevance, and in particular the exhaustivity dimension, was needed. this paper attempts to answer this question through extensive statistical tests to compare the conclusions about system performance that could be made under different assessment scenarios.
vector and matrix operations programmed with udfs in a relational dbms. in general, a relational dbms provides limited capabilities to perform multidimensional statistical analysis, which requires manipulating vectors and matrices. in this work, we study how to extend a dbms with basic vector and matrix operators by programming user-defined functions (udfs). we carefully analyze udf features and limitations to implement vector and matrix operations commonly used in statistics, machine learning and data mining, paying attention to dbms, operating system and computer architecture constraints. udfs represent a c programming interface that allows the definition of scalar and aggregate functions that can be used in sql. udfs have several advantages and limitations. a udf allows fast evaluation of arithmetic expressions, memory manipulation, using multidimensional arrays and exploiting all c language control statements. nevertheless, a udf cannot perform disk i/o, the amount of heap and stack memory that can be allocated is small and the udf code must consider specific architecture characteristics of the dbms. we experimentally compare udfs and sql with respect to performance, ease of use, flexibility and scalability. we profile udfs based on call overhead, memory management and interleaved disk access. we show udfs are faster than standard sql aggregations and as fast as sql arithmetic expressions.
robust periodicity detection algorithms. periodicity detection is an important pre-processing step for many time series algorithms. it provides important information about the structural properties of a time series. feature vectors based on periodicity can be used for clustering, classification, abnormality detection, and human motion understanding. the periodicity detection task is not difficult in case of simple and uncontaminated signal. unfortunately, most of the real datasets exhibit one or more of the following properties: i) non-stationarity, ii) interlaced cyclic patterns and iii) data contamination, which makes the period detection extremely challenging. a seemingly straightforward solution is to develop individual specialized algorithms for handling each case separately. however, determining if a time series is non-stationary or is contaminated in itself is an extremely difficult task. in this article, we propose generic algorithms which can detect periods in complex, noisy and incomplete datasets. the algorithm leverages the frequency characterization and autocorrelation structure inherent in a time series to estimate its periodicity. we extend the methods to handle non-stationary time series by tracking the candidate periods using a kalman filter. we also address the interesting problem of finding multiple interlaced periodicities.
polestar: collaborative knowledge management and sensemaking tools for intelligence analysts. in this paper, we describe polestar (policy explanation using stories and arguments), an integrated suite of knowledge management and collaboration tools for intelligence analysts.polestar provides built-in support for analyst workflow, including collection of textual facts from source documents, structured argumentation, and automatic citation in analytic product documents. underlying polestar is a scalable dependency repository, which provides traceability from product documents to source snippets. the repository's notification engine allows polestar to alert analysts when dependent sources are discredited and aid them in repairing affected arguments. the paper then discusses recent extensions to polestar to support collaborative analysis through community-of-interest finding, portfolio sharing, and peer review of arguments. we conclude with a preview of future research and summary of polestar's primary benefits from the point of view of its deployed users.
mining blog stories using community-based and temporal clustering. in recent years, weblogs, or blogs for short, have become an important form of online content. the personal nature of blogs, online interactions between bloggers, and the temporal nature of blog entries, differentiate blogs from other kinds of web content. bloggers interact with each other by linking to each other's posts, thus forming online communities. within these communities, bloggers engage in discussions of certain issues, through entries in their blogs. since these discussions are often initiated in response to online or offline events, a discussion typically lasts for a limited time duration. we wish to extract such temporal discussions, or stories, occurring within blogger communities, based on some query keywords. we propose a content-community-time model that can leverage the content of entries, their timestamps, and the community structure of the blogs, to automatically discover stories. doing so also allows us to discover hot stories. we demonstrate the effectiveness of our model through several case studies using real-world data collected from the blogosphere.
diva: a variance-based clustering approach for multi-type relational data. clustering is a common technique used to extract knowledge from a dataset in unsupervised learning. in contrast to classical propositional approaches that only focus on simple and flat datasets, relational clustering can handle multi-type interrelated data objects directly and adopt semantic information hidden in the linkage structure to improve the clustering result. however, exploring linkage information will greatly reduce the scalability of relational clustering. moreover, some characteristics of vector data space utilized to accelerate the propositional clustering procedure are no longer valid in relational data space. these two disadvantages restrain the relational clustering techniques from being applied to very large datasets or in time-critical tasks, such as online recommender systems. in this paper we propose a new variance-based clustering algorithm to address the above difficulties. our algorithm combines the advantages of divisive and agglomerative clustering paradigms to improve the quality of cluster results. by adopting the idea of representative object, it can be executed with linear time complexity. experimental results show our algorithm achieves high accuracy, efficiency and robustness in comparison with some well-known relational clustering approaches.
constrained subspace skyline computation. in this paper we introduce the problem of constrained subspace skyline queries. this class of queries can be thought of as a generalization of subspace skyline queries using range constraints. although both constrained skyline queries and subspace skyline queries have been addressed previously, the implications of constrained subspace skyline queries has not been examined so far. constrained skyline queries are usually more expensive than regular skylines. in case of constrained subspace skyline queries additional performance degradation is caused through the projection. in order to support constrained skylines for arbitrary subspaces, we present approaches exploiting multiple low-dimensional indexes instead of relying on a single high-dimensional index. effective pruning strategies are applied to discard points from dominated regions. an important ingredient of our approach is the workload-adaptive strategy for determining the number of indexes and the assignment of dimensions to the indexes. extensive performance evaluation shows the superiority of our proposed technique compared to its most related competitors.
multi-evidence, multi-criteria, lazy associative document classification. we present a novel approach for classifying documents that combines different pieces of evidence (e.g., textual features of documents, links, and citations) transparently, through a data mining technique which generates rules associating these pieces of evidence to predefined classes. these rules can contain any number and mixture of the available evidence and are associated with several quality criteria which can be used in conjunction to choose the "best" rule to be applied at classification time. our method is able to perform evidence enhancement by link forwarding/backwarding (i.e., navigating among documents related through citation), so that new pieces of link-based evidence are derived when necessary. furthermore, instead of inducing a single model (or rule set) that is good on average for all predictions, the proposed approach employs a lazy method which delays the inductive process until a document is given for classification, therefore taking advantage of better qualitative evidence coming from the document. we conducted a systematic evaluation of the proposed approach using documents from the acm digital library and from a brazilian web directory. our approach was able to outperform in both collections all classifiers based on the best available evidence in isolation as well as state-of-the-art multi-evidence classifiers. we also evaluated our approach using the standard webkb collection, where our approach showed gains of 1% in accuracy, being 25 times faster. further, our approach is extremely efficient in terms of computational performance, showing gains of more than one order of magnitude when compared against other multi-evidence classifiers.
a fast and robust method for web page template detection and removal. the widespread use of templates on the web is considered harmful for two main reasons. not only do they compromise the relevance judgment of many web ir and web mining methods such as clustering and classification, but they also negatively impact the performance and resource usage of tools that process web pages. in this paper we present a new method that efficiently and accurately removes templates found in collections of web pages. our method works in two steps. first, the costly process of template detection is performed over a small set of sample pages. then, the derived template is removed from the remaining pages in the collection. this leads to substantial performance gains when compared to previous approaches that combine template detection and removal. we show, through an experimental evaluation, that our approach is effective for identifying terms occurring in templates - obtaining f-measure values around 0.9, and that it also boosts the accuracy of web page clustering and classification methods.
a study on the effects of personalization and task information on implicit feedback performance. while implicit relevance feedback (irf) algorithms exploit users' interactions with information to customize support offered to users of search systems, it is unclear how individual and task differences impact the effectiveness of such algorithms. in this paper we describe a study on the effect on retrieval performance of using additional information about the user and their search tasks when developing irf algorithms. we tested four algorithms that use document display time to estimate relevance, and tailored the threshold times (i.e., the time distinguishing relevance from non-relevance) to the task, the user, a combination of both, or neither. interaction logs gathered during a longitudinal naturalistic study of online information-seeking behavior are used as stimuli for the algorithms. the findings show that tailoring display time thresholds based on task information improves irf algorithm performance, but doing so based on user information worsens performance. this has implications for the development of effective irf algorithms.
a comparative study on classifying the functions of web page blocks. in this paper, we study the problem of learning block classification models to estimate block functions. we distinguish general models, which are learned across multiple sites, and site-specific models, which are learned within individual sites. we further consider several factors that affect the learning process and model effectiveness. these factors include the layout features, the content features, the classifiers, and the term selection methods. we have empirically evaluated the performance of the models when the factors are varied. our main results are that layout features do better than content features for learning both general and site-specific models.
clustering for unsupervised relation identification. unsupervised relation identification is the task of automatically discovering interesting relations between entities in a large text corpora. relations are identified by clustering the frequently co-occurring pairs of entities in such a way that pairs occurring in similar contexts end up belonging to the same clusters. in this paper we compare several clustering setups, some of them novel and others already tried. the setups include feature extraction and selection methods and clustering algorithms. in order to do the comparison, we develop a clustering evaluation metric, specifically adapted for the relation identification task. our experiments demonstrate significant superiority of the single-linkage hierarchical clustering with the novel threshold selection technique over the other tested clustering algorithms. also, the experiments indicate that for successful relation identification it is important to use rich complex features of two kinds: features that test both relation slots together ("relation features"), and features that test only one slot each ("entity features"). we have found that using both kinds of features with the best of the algorithms produces very high-precision results, significantly improving over the previous work.
matching and evaluation of disjunctive predicates for data stream sharing. new optimization techniques, e.g., in data stream management systems (dsmss), make the treatment of disjunctive predicates a necessity. in this paper, we introduce and compare methods for matching and evaluating disjunctive predicates.
semiautomatic evaluation of retrieval systems using document similarities. semiautomatic evaluation of retrieval systems using document similarities.
approximate reverse k-nearest neighbor queries in general metric spaces. in this paper, we propose an approach for efficient approximative rknn search in arbitrary metric spaces where the value of k is specified at query time. our method uses an approximation of the nearest-neighbor-distances in order to prune the search space. in several experiments, our solution scales significantly better than existing non-approximative approaches while producing an approximation of the true query result with a high recall.
an integer programming approach for frequent itemset hiding. the rapid growth of transactional data brought, soon enough, into attention the need of its further exploitation. in this paper, we investigate the problem of securing sensitive knowledge from being exposed in patterns extracted during association rule mining. instead of hiding the produced rules directly, we decide to hide the sensitive frequent itemsets that may lead to the production of these rules. as a first step, we introduce the notion of distance between two databases and a measure for quantifying it. by trying to minimize the distance between the original database and its sanitized version (that can safely be released), we propose a novel, exact algorithm for association rule hiding and evaluate it on real world datasets demonstrating its effectiveness towards solving the problem.
a dictionary for approximate string search and longest prefix search. in this paper we propose a dictionary data structure for string search with errors where the query string may didiffer from the expected matching string by a few edits. this data structure can also be used to find the database string with the longest common prefix with few errors. specifically, with a database of n random strings, each of length of o(m), we show how to perform string search on a query string that differs from its closest match by k edits using a data structure of linear size and query time equal to õ(log n 2 log n klog a 2m over 2m). this means that if k < m over log a 2m log n, then the query time is õ(1). this is of significant in practice as there are several applications where k is small relative to m. our approach converts strings into bit vectors so that similar strings can map to similar bit vectors with small hamming distance. a simple reduction can be used to obtain similar results for approximate longest prefix search.