waashk/dblp huggingface dataset:
visual analytics tools for analysis of movement data. with widespread availability of low cost gps devices, it is becoming possible to record data about the movement of people and objects at a large scale. while these data hide important knowledge for the optimization of location and mobility oriented infrastructures and services, by themselves they lack the necessary semantic embedding which would make fully automatic algorithmic analysis possible. at the same time, making the semantic link is easy for humans who however cannot deal well with massive amounts of data. in this paper, we argue that by using the right visual analytics tools for the analysis of massive collections of movement data, it is possible to effectively support human analysts in understanding movement behaviors and mobility patterns. we suggest a framework for analysis combining interactive visual displays, which are essential for supporting human perception, cognition, and reasoning, with database operations and computational methods, which are necessary for handling large amounts of data. we demonstrate the synergistic use of these techniques in case studies of two real datasets.
a classical predictive modeling approach for task "who rated what?" of the kdd cup 2007. this paper describes one possible way to solve task "who rated what?" of the kdd cup 2007. the proposed solution is a history-based model that predicts whether a user will vote a given movie. key points to our approach are (1) the estimation of the model baseline, (2) the definition of the explanatory variables and (3) the mathematical model form. given the binary outcome of the problem, the estimation of the true baseline (ratio of 1's in the test data) is critical in order to correctly make predictions. in parallel, to improve the model predictive power, we have developed a careful construction of the input variables. these explanatory variables can be grouped as: user voting behaviour variables, the movie characteristics and user-movie interactions. finally, the mathematical model form (linear logistic regression) has been chosen among various model form competitors.
8 french-speaking conference on knowledge discovery and management (egc2008): conference report. in this paper, we provide a report about the 8th french-speaking conference on knowledge discovery and management (egc'2008) [1] held in sophia antipolis, france, from january 29th to february 1st, 2008. since 2001, this annual conference has been supported by the french-speaking association (egc association) which aims at promoting data mining and knowledge management for both research issues and applications in companies. egc2008 may be summarized in some key figures: 130 submitted papers, 40 accepted long papers (33% selection ratio) published in a special issue of a review and completed with 30 short papers, 15 posters, and 8 software demonstrations; 9 joined workshops and 2 tutorials; 4 keynote talks; a best paper contest rewarded by 2 prizes of 1500 euros each; and 250 participants from 14 countries. the 9th egc conference will be held in strasbourg, france, in january 27-30, 2009 [2].
higher order mining. the value of knowledge obtainable by analysing large quantities of data is widely acknowledged. however, so-called primary or raw data may not always be available for knowledge discovery for several reasons. first, cooperating institutions that are interested in sharing knowledge may not be willing (or allowed) to disclose their primary data. second, data in the form of streams are only temporarily available for processing. if stored at all, stream data are maintained in the form of synopses or derived, abstract representations of the original data. finally, even for non-stream data, there are limits on the computation speed to be achieved -- such limits are set by hardware and firmware technologies. this problem can only be partially solved through parallelization and increased processing power. ultimately, in many cases data must be summarized to be processed efficiently. in the light of these observations, we anticipate the need for defining and practising data mining without the luxury of primary data. to that end, we formally introduce the paradigm of higher order mining as a form of data mining that is applied over non-primary, derived data or patterns. although higher order mining is a new paradigm, there are already research advances on knowledge discovery methods from patterns rather than data. we discuss them and organize them under the light of the new paradigm. we show that the hom paradigm reveals further potential for knowledge discovery, including the delivery of rules and patterns with semantics that are closer to human intuition and are thus more appropriate for human inspection.
blogosphere: research issues, tools, and applications. weblogs, or blogs, have facilitated people to express their thoughts, voice their opinions, and share their experiences and ideas. individuals experience a sense of community, a feeling of belonging, a bonding that members matter to one another and their niche needs will be met through online interactions. its open standards and low barrier to publication have transformed information consumers to producers. this has created a plethora of open-source intelligence, or "collective wisdom" that acts as the storehouse of over-whelming amounts of knowledge about the members, their environment and the symbiosis between them. nonetheless, vast amounts of this knowledge still remain to be discovered and exploited in its suitable way. in this paper, we introduce various state-of-the-art research issues, review some key elements of research such as tools and methodologies in blogosphere, and present a case study of identifying the influential bloggers in a community to exemplify the integration of some major aspects discussed in this paper. towards the end, we also compare and contrast the blogosphere and social networks and the research therein.
a privacy-aware trajectory tracking query engine. advances in telecommunications and gps sensors technology have made possible the collection of data like time series of locations, related to the movement of individuals. the analysis of this, so-called trajectory data, is beneficial both for the individuals (e.g., through location-based services) and for the community as a whole (e.g., decision support for urban planning or traffic control). however, because of the very nature of this data, strict safeguards must be enforced to ensure the privacy of the individuals, whose movement is recorded. in this paper, we present a privacy-aware trajectory tracking query engine that offers strict guarantees about what can be observed by untrusted third parties. through the query engine, subscribed users can gain restricted access to an in-house trajectory data warehouse, to perform certain analysis tasks. in addition to regular queries involving non-spatial non-temporal attributes, the engine supports a variety of spatiotemporal queries, including range queries, nearest neighbor queries and queries for aggregate statistics. the query results are augmented with fake trajectory data (dummies) to fulfil the requirements of k-anonymity. through qualitative analysis, we prove the effectiveness of our approach towards blocking certain types of attacks, while minimally distorting the dataset.
data mining with cellular automata. a cellular automaton is a discrete, dynamical system composed of very simple, uniformly interconnected cells. cellular automata may be seen as an extreme form of simple, localized, distributed machines. many researchers are familiar with cellular automata through conway's game of life. researchers have long been interested in the theoretical aspects of cellular automata. this article explores the use of cellular automata for data mining, specifically for classification tasks. we demonstrate that reasonable generalization behavior can be achieved as an emergent property of these simple automata.
approximating rank-width and clique-width quickly. rank-width was defined by oum and seymour [2006] to investigate clique-width. they constructed an algorithm that either outputs a rank-decomposition of width at most f(k) for some function f or confirms that rank-width is larger than k in time o(&verbar;v&verbar;9log &verbar;v&verbar;) for an input graph g &equals; (v,e) and a fixed k. we develop three separate algorithms of this kind with faster running time. we construct an o(&verbar;v&verbar;4)-time algorithm with f(k) &equals; 3k + 1 by constructing a subroutine for the previous algorithm; we avoid generic algorithms minimizing submodular functions used by oum and seymour. another one is an o(&verbar;v&verbar;3)-time algorithm with f(k) &equals; 24k, achieved by giving a reduction from graphs to binary matroids; then we use an approximation algorithm for matroid branch-width by hlin&ecaron;n&yacute; [2005]. finally we construct an o(&verbar;v&verbar;3)-time algorithm with f(k) &equals; 3k &minus; 1 by combining the ideas of the two previously cited papers.
pricing multicasting in more flexible network models. the problem of designing efficient algorithms for sharing the cost of multicasting has recently received considerable attention. in this article, we examine the effect on the complexity of pricing when two flexibility-enhancing mechanisms are incorporated into the network model. in particular, we study a model where the session is offered at a number of different rates of transmission, and where there is a cost for enabling multicasting at each node of the network. we consider two techniques that have been used in practice to provide multiple rates: using a layered transmission scheme (called the layered paradigm) and using different multicast groups for each possible rate (called the split session paradigm). we demonstrate that the difference between these two paradigms has a significant impact on the complexity of pricing multicasting.for the layered paradigm, we provide a distributed algorithm for computing pricing efficiently in terms of local computation and message complexity. for the split session paradigm, on the other hand, we demonstrate that this problem can be solved in polynomial time if the number of possible rates is fixed, but if the number of rates is part of the input, then the problem becomes np-hard even to approximate. we also examine the effect of delivering the transmissions for the various rates from different locations within the network. we show that, in this case, the pricing problem becomes np-hard for the split session paradigm even for a fixed constant number of possible rates but if layering is used, then it can be solved in polynomial time by formulating the problem as a totally unimodular integer program.
oblivious routing on node-capacitated and directed graphs. oblivious routing algorithms for general undirected networks were introduced by r&auml;cke [2002], and this work has led to many subsequent improvements and applications. comparatively little is known about oblivious routing in general directed networks, or even in undirected networks with node capacities. we present the first nontrivial upper bounds for both these cases, providing algorithms for k-commodity oblivious routing problems with competitive ratio o(&sqrt;k log(n)) for undirected node-capacitated graphs and o(&sqrt;k n1/4 log(n)) for directed graphs. in the special case that all commodities have a common source or sink, our upper bound becomes o(&sqrt;n log(n)) in both cases, matching the lower bound up to a factor of log(n). the lower bound (which first appeared in azar et al. [2003]) is obtained on a graph with very high degree. we show that, in fact, the degree of a graph is a crucial parameter for node-capacitated oblivious routing in undirected graphs, by providing an o(&delta; polylog(n))-competitive oblivious routing scheme for graphs of degree &delta;. for the directed case, however, we show that the lower bound of &omega;(&sqrt;n) still holds in low-degree graphs. finally, we settle an open question about routing problems in which all commodities share a common source or sink. we show that even in this simplified scenario there are networks in which no oblivious routing algorithm can achieve a competitive ratio better than &omega;(log n).
black box for constant-time insertion in priority queues (note). we present a simple black box that takes a priority queue q which supports find-min, insert, and delete in x-time at most t. here x-time may be worst-case, expected, or amortized. the black-box transforms q into a priority queue q* that supports find-min in constant time, insert in constant x-time, and delete in x-time o(t). moreover, if q supports dec-key in constant time, then so does q*.
compact name-independent routing with minimum stretch. given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a&otilde;(&sqrt;n,) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the minimum cost paths. this is optimal in a very strong sense. it is known that no compact routing using o(n) space per node can route with stretch below 3. also, it is known that any stretch below 5 requires &omega;(&sqrt;n,)space per node.
an () algorithm for ear decompositions of matching-covered graphs. our main result is an o(nm)-time (deterministic) algorithm for constructing an ear decomposition of a matching-covered graph, where n and m denote the number of nodes and edges. the improvement in the running time comes from new structural results that give a sharpened version of lov&aacute;sz and plummer's two-ear theorem. our algorithm is based on o(nm)-time algorithms for two other fundamental problems in matching theory, namely, finding all the allowed edges of a graph, and finding the canonical partition of an elementary graph. to the best of our knowledge, no faster deterministic algorithms are known for these two fundamental problems.
clustering, community partition and disjoint spanning trees. clustering method is one of the most important tools in statistics. in a graph theory model, clustering is the process of finding all dense subgraphs. a mathematically well-defined measure for graph density is introduced in this article as follows. let g &equals; (v, e) be a graph (or multi-graph) and h be a subgraph of g. the dynamic density of h is the greatest integer k such that min&forall;p {&verbar;e(h/p)&verbar;/&verbar;v(h/p)&verbar; &minus; 1} > k where the minimum is taken over all possible partitions p of the vertex set of h, and h/p is the graph obtained from h by contracting each part of p into a single vertex. a subgraph h of g is a level-k community if h is a maximal subgraph of g with dynamic density at least k. an algorithm is designed in this paper to detect all level-h communities of an input multi-graph g. the worst-case complexity of this algorithm is upper bounded by o(&verbar;v(g)&verbar;2h2). this new method is one of few available clustering methods that are mathematically well-defined, supported by rigorous mathematical proof and able to achieve the optimization goal with polynomial complexity. as a byproduct, this algorithm also can be applied for finding edge-disjoint spanning trees of a multi-graph. the worst-case complexity is lower than all known algorithms for multi-graphs.
on a generalization of the stable roommates problem. we consider two generalizations of the stable roommates problem: a) we allow parallel edges in the underlying graph, and b) we study a problem with multiple partners. we reduce both problems to the classical stable roommates problem and describe an extension of irving's algorithm that solves the generalized problem efficiently. we give a direct proof of a recent result on the structure of stable many-to-many matchings (so called stable b-matchings) as a by-product of the justification of the algorithm.
optimal branch-decomposition of planar graphs in () time. we give an o(n3) time algorithm for constructing a minimum-width branch-decomposition of a given planar graph with n vertices. this is achieved through a refinement to the previously best known algorithm of seymour and thomas, which runs in o(n4) time.
the greedy algorithm for the minimum common string partition problem. in the minimum common string partition problem (mcsp), we are given two strings on input, and we wish to partition them into the same collection of substrings, minimizing the number of the substrings in the partition. this problem is np-hard, even for a special case, denoted 2-mcsp, where each letter occurs at most twice in each input string. we study a greedy algorithm for mcsp that at each step extracts a longest common substring from the given strings. we show that the approximation ratio of this algorithm is between &omega;(n0.43) and o(n0.69). in the case of 2-mcsp, we show that the approximation ratio is equal to 3. for 4-mcsp, we give a lower bound of &omega;(log n).
average-case lower bounds for the plurality problem. given a set of n elements, each of which is colored one of c &ge; 2 colors, we have to determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. we derive lower bounds for the expected number of color comparisons when the cn colorings are equally probable. we prove a general lower bound of c/3n &minus; o(&sqrt;n) for c &ge; 2; we prove the stronger particular bounds of 7/6 n &minus; o(&sqrt;n) for c &equals; 3, 54/35n &minus; o(&sqrt;n) for c &equals; 4, 607/315n &minus; o(&sqrt;n) for c &equals; 5, 1592/693n &minus; o(&sqrt;n) for c &equals; 6, 7985/3003n &minus; o(&sqrt;n) for c &equals; 7, and 19402/6435n &minus; o(&sqrt;n) for c &equals; 8.
fixed-parameter algorithms for (, )-center in planar graphs and map graphs. the (k, r)-center problem asks whether an input graph g has &le;k vertices (called centers) such that every vertex of g is within distance &le;r from some center. in this article, we prove that the (k, r)-center problem, parameterized by k and r, is fixed-parameter tractable (fpt) on planar graphs, i.e., it admits an algorithm of complexity f(k, r)no(1) where the function f is independent of n. in particular, we show that f(k,r) = 2o(r log r) &ksqrt;, where the exponent of the exponential term grows sublinearly in the number of centers. moreover, we prove that the same type of fpt algorithms can be designed for the more general class of map graphs introduced by chen, grigni, and papadimitriou. our results combine dynamic-programming algorithms for graphs of small branchwidth and a graph-theoretic result bounding this parameter in terms of k and r. finally, a byproduct of our algorithm is the existence of a ptas for the r-domination problem in both planar graphs and map graphs.our approach builds on the seminal results of robertson and seymour on graph minors, and as a result is much more powerful than the previous machinery of alber et al. for exponential speedup on planar graphs. to demonstrate the versatility of our results, we show how our algorithms can be extended to general parameters that are &ldquo;large&rdquo; on grids. in addition, our use of branchwidth instead of the usual treewidth allows us to obtain much faster algorithms, and requires more complicated dynamic programming than the standard leaf/introduce/forget/join structure of nice tree decompositions. our results are also unique in that they apply to classes of graphs that are not minor-closed, namely, constant powers of planar graphs and map graphs.
testing euclidean minimum spanning trees in the plane. given a euclidean graph g over a set p of n points in the plane, we are interested in verifying whether g is a euclidean minimum spanning tree (emst) of p or g differs from it in more than &epsi; n edges. we assume that g is given in adjacency list representation and the point/vertex set p is given in an array. we present a property testing algorithm that accepts graph g if it is an emst of p and that rejects with probability at least 2/3 if g differs from every emst of p in more than &epsi;, n edges. our algorithm runs in o(&sqrt;n/&epsi; &sdot; log2 (n/&epsi;)) time and has a query complexity of o(&sqrt;n/&epsi; &sdot; log (n/&epsi;)).
a maiden analysis of longest wait first. we consider server scheduling strategies to minimize average flow time in a multicast pull system where data items have uniform size. the algorithm longest wait first (lwf) always services the page where the aggregate waiting times of the outstanding requests for that page is maximized. we provide the first non-trivial analysis of the worst case performance of lwf. on the negative side, we show that lwf is not s-speed o(1)-competitive for s < 1+&sqrt;5/2. on the positive side, we show that lwf is 6-speed o(1)-competitive.
determining plurality. given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. we prove that (c &minus; 1)(n &minus; c)/2 color comparisons are necessary in the worst case to determine the plurality color and give an algorithm requiring (0.775c + 5.9)n + o(c2) color comparisons for c &ge; 9.
computing almost shortest paths. we study the <i>s-sources almost shortest paths</i> (abbreviated <i>s-asp</i>) problem. given an unweighted graph <i>g</i> equals; (<i>v,e</i>), and a subset <i>s</i> sube; <i>v</i> of <i>s</i> nodes, the goal is to compute almost shortest paths between all the pairs of nodes <i>s</i> times; <i>v</i>. we devise an algorithm with running time <i>o</i>( mid;<i>e</i> mid;<i>n</i><sup> rho;</sup> plus; <i>s</i> middot; <i>n</i><sup>1 plus; zeta;)</sup> for this problem that computes the paths <i>p</i><sub><i>u,w</i></sub> for all pairs (<i>u,w</i>) isin; <i>s</i> times; <i>v</i> such that the length of <i>p</i><sub><i>u,w</i></sub> is at most (1 plus; epsi;) <i>d</i><sub><i>g</i></sub>(<i>u,w</i>) plus; beta;( zeta;, rho;, epsi;), and beta;( zeta;, rho;, epsi;) is constant when zeta;, rho;, and epsi; are arbitrarily small constants. we also devise a distributed protocol for the <i>s</i>-asp problem that computes the paths <i>p</i><inf><i>u,w</i></inf> as above, and has time and communication complexities of <i>o</i>(<i>s</i> middot; <i>diam(g)</i> plus; <i>n</i><sup>1 plus; zeta;/2</sup>) (respectively, <i>o</i>(<i>s</i> middot; <i>diam(g)</i> log<sup>3</sup> <i>n</i> plus; <i>n</i><sup>1 plus; zeta;/2</sup> log <i>n</i>)) and <i>o</i>( mid;<i>e</i> mid; <i>n</i><sup> rho;</sup> plus; <i>s</i> middot; <i>n</i><sup>1 plus; zeta;)</sup> (respectively, <i>o</i>( mid;<i>e</i> mid; <i>n</i><sup> rho;</sup> plus; <i>s</i> middot; <i>n</i><sup>1 plus; zeta;</sup> plus; <i>n</i><sup>1 plus; rho; plus; zeta;( rho; minus; zeta;/2)/2)) in the synchronous (respectively asynchronous) setting. our sequential algorithm, as well as the distributed protocol, is based on a novel algorithm for constructing (1 plus; epsi;, beta;( zeta;, rho;, epsi;))-spanners of size <i>o</i>(<i>n</i><sup>1 plus; zeta;</sup>), developed in this article. this algorithm has running time of <i>o</i>( mid;<i>e</i> mid; <i>n</i><sup> rho;</sup>), which is significantly faster than the previously known algorithm given in elkin and peleg [2001], whose running time is <i> otilde;</i>(<i>n</i><sup>2 plus; rho;</sup>). we also develop the first distributed protocol for constructing (1 plus; epsi;, beta;)-spanners. the communication complexity of this protocol is near optimal.