waashk/dblp huggingface dataset:
challenging research issues in data mining, databases and information retrieval. data mining research along with related fields such as databases and information retrieval poses challenging problems, especially for doctoral students. the research spreads over a variety of topics such as text mining, semantic web, multilingual information analysis, heterogeneous data management, database learning, digital libraries and more. much of this research cuts across multiple fields and presents interesting issues for discussion at conferences with a confluence of several tracks. the acm conference on information and knowledge management provides an excellent environment for presenting such research problems spanning the three tracks of database systems, information retrieval and knowledge management. this article provides an overview of the dissertation problems presented at a ph.d. workshop in the acm conference on information and knowledge management. the goal of such workshops is to allow students to showcase their creative ideas at an early stage. this enables experts to critique their work and also gives the students an opportunity to exchange their thoughts with each other, besides providing excellent networking opportunities with industry and academia. this article provides an overview of the papers presented at the ph.d workshop. it serves as a motivation for researchers to delve deeper into the innovative dissertation problems summarized here and the related work in these areas.
adaptive learning and mining for data streams and frequent patterns. this thesis is devoted to the design of data mining algorithms for evolving data streams and for the extraction of closed frequent trees. first, we deal with each of these tasks separately, and then we deal with them together, developing classification methods for data streams containing items that are trees. in the data stream model, data arrive at high speed, and the algorithms that must process them have very strict constraints of space and time. in the first part of this thesis we propose and illustrate a framework for developing algorithms that can adaptively learn from data streams that change over time. our methods are based on using change detectors and estimator modules at the right places. we propose an adaptive sliding window algorithm adwin for detecting change and keeping updated statistics from a data stream, and use it as a black-box in place or counters or accumulators in algorithms initially not designed for drifting data. since adwin has rigorous performance guarantees, this opens the possibility of extending such guarantees to learning and mining algorithms. we test our methodology with several learning methods as naíve bayes, clustering, decision trees and ensemble methods. we build an experimental framework for data stream mining with concept drift, based on the moa framework, similar to weka, so that it will be easy for researchers to run experimental data stream benchmarks. trees are connected acyclic graphs and they are studied as link-based structures in many cases. in the second part of this thesis, we describe a rather formal study of trees from the point of view of closure-based mining. moreover, we present efficient algorithms for subtree testing and for mining ordered and unordered frequent closed trees. we include an analysis of the extraction of association rules of full condence out of the closed sets of trees, and we have found there an interesting phenomenon: rules whose propositional counterpart is nontrivial are, however, always implicitly true in trees due to the peculiar combinatorics of the structures. and finally, using these results on evolving data streams mining and closed frequent tree mining, we present high performance algorithms for mining closed unlabeled rooted trees adaptively from data streams that change over time. we introduce a general methodology to identify closed patterns in a data stream, using galois lattice theory. using this methodology, we then develop an incremental one, a sliding-window based one, and finally one that mines closed trees adaptively from data streams. we use these methods to develop classification methods for tree data streams.
the weka data mining software: an update. more than twelve years have elapsed since the first public release of weka. in that time, the software has been rewritten entirely from scratch, evolved substantially and now accompanies a text on data mining [35]. these days, weka enjoys widespread acceptance in both academia and business, has an active community, and has been downloaded more than 1.4 million times since being placed on source-forge in april 2000. this paper provides an introduction to the weka workbench, reviews the history of the project, and, in light of the recent 3.6 stable release, briefly discusses what has been added since the last stable version (weka 3.4) released in 2003.
what's pmml and what's new in pmml 4.0? the predictive model markup language (pmml) data mining standard has arguably become one of the most widely adopted data mining standards in use today. two years in the making, the latest release of pmml contains several new features and many enhancements to existing ones. this paper provides a primer on the pmml standard and its applications along with a description of the new features in pmml 4.0 which was released in may 2009.
development and user experiences of an open source data cleaning, deduplication and record linkage system. record linkage, also known as database matching or entity resolution, is now recognised as a core step in the kdd process. data mining projects increasingly require that information from several sources is combined before the actual mining can be conducted. also of increasing interest is the deduplication of a single database. the objectives of record linkage and deduplication are to identify, match and merge all records that relate to the same real-world entities. because real-world data is commonly 'dirty', data cleaning is an important first step in many deduplication, record linkage, and data mining project. in this paper, an overview of the febrl (freely extensible biomedical record linkage) system is provided, and the results of a recent survey of febrl users is discussed. febrl includes a variety of functionalities required for data cleaning, deduplication and record linkage, and it provides a graphical user interface that facilitates its application for users who do not have programming experience.
open source analytics: an introduction to the special issue. this special issue contains six articles on open source analytics. it includes an article describing the weka data mining system, two articles on infrastructure to support analytics, an article on the pmml standard for statistical and data mining models, an article on how clouds are being used in analytics, and an article about an open source tool for cleaning data.
knime - the konstanz information miner: version 2.0 and beyond. the konstanz information miner is a modular environment, which enables easy visual assembly and interactive execution of a data pipeline. it is designed as a teaching, research and collaboration platform, which enables simple integration of new algorithms and tools as well as data manipulation or visualization methods in the form of new modules or nodes. in this paper we describe some of the design aspects of the underlying architecture, briey sketch how new nodes can be incorporated, and highlight some of the new features of version 2.0.
correlation clustering. this is a short summary of the author's thesis on "correlation clustering" (ludwig-maximilians-universität münchen, germany, 2008). the complete thesis is available at http://edoc.ub.uni-muenchen.de/8736/.
a linear algorithm for computing convex hulls for random lines. finding the convex hull of n points in the plane requires o(n log n) time in general. in devroye and toussaint [1993] and golin et al. [2002] the problem of computing the convex hull of the intersection points of n lines was considered, where the lines are chosen randomly according to two various models. in both models, linear-time algorithms were developed. here we improve the results of devroye and toussaint [1993] by giving a universal algorithm for a wider range of distributions.
polynomial constraint satisfaction problems, graph bisection, and the ising partition function. we introduce a problem class we call polynomial constraint satisfaction problems, or pcsp. where the usual csps from computer science and optimization have real-valued score functions, and partition functions from physics have monomials, pcsp has scores that are arbitrary multivariate formal polynomials, or indeed take values in an arbitrary ring. although pcsp is much more general than csp, remarkably, all (exact, exponential-time) algorithms we know of for 2-csp (where each score depends on at most 2 variables) extend to 2-pcsp, at the expense of just a polynomial factor in running time. specifically, we extend the reduction-based algorithm of scott and sorkin [2007]; the specialization of that approach to sparse random instances, where the algorithm runs in polynomial expected time; dynamic-programming algorithms based on tree decompositions; and the split-and-list matrix-multiplication algorithm of williams [2004]. this gives the first polynomial-space exact algorithm more efficient than exhaustive enumeration for the well-studied problems of finding a maximum bisection of a graph, and calculating the partition function of an ising model. it also yields the most efficient algorithm known for certain instances of counting and/or weighted maximum independent set. furthermore, pcsp solves both optimization and counting versions of a wide range of problems, including all csps, and thus enables samplers including uniform sampling of optimal solutions and gibbs sampling of all solutions.
enumeration of isolated cliques and pseudo-cliques. in this article, we consider isolated cliques and isolated dense subgraphs. for a given graph g, a vertex subset s of size k (and also its induced subgraph g(s)) is said to be c-isolated if g(s) is connected to its outside via less than ck edges. the number c is sometimes called the isolation factor. the subgraph appears more isolated if the isolation factor is smaller. the main result in this work shows that for a fixed constant c, we can enumerate all c-isolated maximal cliques (including a maximum one, if any) in linear time. in more detail, we show that, for a given graph g of n vertices and m edges, and a positive real number c, all c-isolated maximal cliques can be enumerated in time o( c4 22cm). from this, we can see that: (1) if c is a constant, all c-isolated maximal cliques can be enumerated in linear time, and (2) if c &equlas; o(log n), all c-isolated maximal cliques can be enumerated in polynomial time. moreover, we show that these bounds are tight. that is, if f(n) is an increasing function not bounded by any constant, then there is a graph of n vertices and m edges for which the number of f(n)-isolated maximal cliques is superlinear in n + m. furthermore, if f(n) &equals; &omega;(log n), there is a graph of n vertices and m edges for which the number of f(n)-isolated maximal cliques is superpolynomial in n + m. we next introduce the idea of pseudo-cliques. a pseudo-clique having an average degree &alpha; and a minimum degree &beta;, denoted by pc(&alpha;,&beta;), is a set v&prime; &sube; v such that the subgraph induced by v&prime; has an average degree of at least &alpha; and a minimum degree of at least &beta;. this article investigates these, and obtains some cases that can be solved in polynomial time and some other cases that have a superpolynomial number of solutions. especially, we show the following results, where k is the number of vertices of the isolated pseudo-cliques: (1) for any &epsiv; > 0 there is a graph of n vertices for which the number of 1-isolated pc(k &minus; (log k)1 + &epsiv;, k/(log k)1 + &epsiv;) is superpolynomial, and (2) there is a polynomial-time algorithm which enumerates all c-isolated pc(k &minus; log k, k/log k), for any constant c.
sublinear estimation of entropy and information distances. in many data mining and machine learning problems, the data items that need to be clustered or classified are not arbitrary points in a high-dimensional space, but are distributions, that is, points on a high-dimensional simplex. for distributions, natural measures are not &ell;p distances, but information-theoretic measures such as the kullback-leibler and hellinger divergences. similarly, quantities such as the entropy of a distribution are more natural than frequency moments. efficient estimation of these quantities is a key component in algorithms for manipulating distributions. since the datasets involved are typically massive, these algorithms need to have only sublinear complexity in order to be feasible in practice. we present a range of sublinear-time algorithms in various oracle models in which the algorithm accesses the data via an oracle that supports various queries. in particular, we answer a question posed by batu et al. on testing whether two distributions are close in an information-theoretic sense given independent samples. we then present optimal algorithms for estimating various information-divergences and entropy with a more powerful oracle called the combined oracle that was also considered by batu et al. finally, we consider sublinear-space algorithms for these quantities in the data-stream model. in the course of doing so, we explore the relationship between the aforementioned oracle models and the data-stream model. this continues work initiated by feigenbaum et al. an important additional component to the study is considering data streams that are ordered randomly rather than just those which are ordered adversarially.
improved online algorithms for the sorting buffer problem on line metrics. an instance of the sorting buffer problem consists of a metric space and a server, equipped with a finite-capacity buffer capable of holding a limited number of requests. an additional ingredient of the input is an online sequence of requests, each of which is characterized by a destination in the given metric space; whenever a request arrives, it must be stored in the sorting buffer. at any point in time, a currently pending request can be served by drawing it out of the buffer and moving the server to its corresponding destination. the objective is to serve all input requests in a way that minimizes the total distance traveled by the server. in this article, we focus our attention on instances of the problem in which the underlying metric is either an evenly-spaced line metric or a continuous line metric. our main findings can be briefly summarized as follows. (1) we present a deterministic o(log n)-competitive algorithm for n-point evenly-spaced line metrics. this result improves on a randomized o(log2 n)-competitive algorithm due to khandekar and pandit [2006b]. it also refutes their conjecture, stating that a deterministic strategy is unlikely to obtain a nontrivial competitive ratio. (2) we devise a deterministic o(log n log log n)-competitive algorithm for continuous line metrics, where n denotes the length of the input sequence. in this context, we introduce a novel discretization technique of independent interest. (3) we establish the first nontrivial lower bound for the evenly-spaced case, by proving that the competitive ratio of any deterministic algorithm is at least 2 + &sqrt;3/&sqrt;3 &ap; 2.154. this result settles, to some extent, an open question due to khandekar and pandit [2006b], who posed the task of attaining lower bounds on the achievable competitive ratio as a foundational objective for future research.
computing rank-convolutions with a mask. rank-convolutions have important applications in a variety of areas such as signal processing and computer vision. we define a mask as a function taking only values zero and infinity. rank-convolutions with masks are of special interest to image processing. we show how to compute the rank-k convolution of a function over an interval of length n with an arbitrary mask of length m in o(n&sqrt;m log m) time. the result generalizes to the d-dimensional case. previously no algorithm performing significantly better than the brute-force o(nm) bound was known. our algorithm seems to perform well in practice. we describe an implementation, illustrating its application to a problem in image processing. already on relatively small images, our experiments show a signficant speedup compared to brute force.
latency-constrained aggregation in sensor networks. a sensor network consists of sensing devices which may exchange data through wireless communication; sensor networks are highly energy constrained since they are usually battery operated. data aggregation is a possible way to save energy consumption: nodes may delay data in order to aggregate them into a single packet before forwarding them towards some central node (sink). however, many applications impose constraints on the maximum delay of data; this translates into latency constraints for data arriving at the sink. we study the problem of data aggregation to minimize maximum energy consumption under latency constraints on sensed data delivery, and we assume unique communication paths that form an intree rooted at the sink. we prove that the offline problem is strongly np-hard and we design a 2-approximation algorithm. the latter uses a novel rounding technique. almost all real-life sensor networks are managed online by simple distributed algorithms in the nodes. in this context we consider both the case in which sensor nodes are synchronized or not. we assess the performance of the algorithm by competitive analysis. we also provide lower bounds for the models we consider, in some cases showing optimality of the algorithms we propose. most of our results also hold when minimizing the total energy consumption of all nodes.
exponential time algorithms for the minimum dominating set problem on some graph classes. the minimum dominating set problem remains np-hard when restricted to any of the following graph classes: c-dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, and circle graphs. developing and using a general approach, for each of these graph classes we present an exponential time algorithm solving the minimum dominating set problem faster than the best known algorithm for general graphs. our algorithms have the following running time: o(1.4124n) for chordal graphs, o(1.4776n) for weakly chordal graphs, o(1.4845n) for 4-chordal graphs, o(1.4887n) for circle graphs, and o(1.2273(1+&sqrt;1&minus;2c)n) for c-dense graphs.
quantum algorithms for simon's problem over nonabelian groups. daniel simon's 1994 discovery of an efficient quantum algorithm for finding &ldquo;hidden shifts&rdquo; of z2n provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. in this article, we study the generalization of simon's problem to arbitrary groups. fixing a finite group g, this is the problem of recovering an involution m &equals; (m1,&hellip;,mn) &isin; gn from an oracle f with the property that f(x &sdot; y) &equals; f(x) &harr; y &isin; {1, m}. in the current parlance, this is the hidden subgroup problem (hsp) over groups of the form gn, where g is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. although groups of the form gn have a simple product structure, they share important representation--theoretic properties with the symmetric groups sn, where a solution to the hsp would yield a quantum algorithm for graph isomorphism. in particular, solving their hsp with the so-called &ldquo;standard method&rdquo; requires highly entangled measurements on the tensor product of many coset states. in this article, we provide quantum algorithms with time complexity 2o(&sqrt;n) that recover hidden involutions m &equals; (m1,&hellip;mn) &isin; gn where, as in simon's problem, each mi is either the identity or the conjugate of a known element m which satisfies &kappa;(m) &equals; &minus;&kappa;(1) for some &kappa; &isin; &gcirc;. our approach combines the general idea behind kuperberg's sieve for dihedral groups with the &ldquo;missing harmonic&rdquo; approach of moore and russell. these are the first nontrivial hsp algorithms for group families that require highly entangled multiregister fourier sampling.
approximating the minimum quadratic assignment problems. we consider the well-known minimum quadratic assignment problem. in this problem we are given two n &times; n nonnegative symmetric matrices a &equals; (aij) and b &equals; (bij). the objective is to compute a permutation &pi; of v &equals; {1,&hellip;,n} so that &sum; i,j&isin;vi&ne;j a&pi;(i),&pi;(j)bi,j is minimized. we assume that a is a 0/1 incidence matrix of a graph, and that b satisfies the triangle inequality. we analyze the approximability of this class of problems by providing polynomial bounded approximations for some special cases, and inapproximability results for other cases.
minimum cycle bases: faster and simpler. we consider the problem of computing exact or approximate minimum cycle bases of an undirected (or directed) graph g with m edges, n vertices and nonnegative edge weights. in this problem, a {0, 1} (&minus;1,0,1}) incidence vector is associated with each cycle and the vector space over f2 (q) generated by these vectors is the cycle space of g. a set of cycles is called a cycle basis of g if it forms a basis for its cycle space. a cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of g. cycle bases of low weight are useful in a number of contexts, for example, the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. there exists a set of &theta;(mn) cycles which is guaranteed to contain a minimum cycle basis. a minimum basis can be extracted by gaussian elimination. the resulting algorithm [horton 1987] was the first polynomial-time algorithm. faster and more complicated algorithms have been found since then. we present a very simple method for extracting a minimum cycle basis from the candidate set with running time o(m2 n), which improves the running time for sparse graphs. furthermore, in the undirected case by using bit-packing we improve the running time also in the case of dense graphs. for undirected graphs we derive an o(m2 n/log n + n2 m) algorithm. for directed graphs we get an o(m3 n) deterministic and an o(m2 n) randomized algorithm. our results improve the running times of both exact and approximate algorithms. finally, we derive a smaller candidate set with size in &omega;(m) &cap; o(mn).
simultaneous source location. we consider the problem of simultaneous source location: selecting locations for sources in a capacitated graph such that a given set of demands can be satisfied simultaneously, with the goal of minimizing the number of locations chosen. for general directed and undirected graphs we give an o(log d)-approximation algorithm, where d is the sum of demands, and prove matching &omega;(log d) hardness results assuming p &ne; np. for undirected trees, we give an exact algorithm and show how this can be combined with a result of r&auml;cke to give a solution that exceeds edge capacities by at most o(log2 n log log n), where n is the number of nodes. for undirected graphs of bounded treewidth we show that the problem is still np-hard, but we are able to give a ptas with at most (1 + &epsis;) violation of the capacities for arbitrarily small &epsis;, or a (k+1) approximation with exact capacities, where k is the treewidth.