waashk/dblp huggingface dataset:
on parameterized exponential time complexity. in this paper we study the notion of parameterized exponential time complexity. we show that a parameterized problem can be solved in parameterized 2^o^(^f^(^k^)^)p(n) time if and only if it is solvable in time o(2^@d^f^(^k^)q(n)) for any constant @d>0, where p and q are polynomials. we then illustrate how this equivalence can be used to show that special instances of parameterized np-hard problems are as difficult as the general instances. for example, we show that the planar dominating set problem on degree-3 graphs can be solved in 2^o^(^k^)p(n) parameterized time if and only if the general planar dominating set problem can. apart from their complexity theoretic implications, our results have some interesting algorithmic implications as well.
on the intersection of regex languages with regular languages. in this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [a.v. aho, algorithms for finding patterns in strings, in: jan van leeuwen (ed.), handbook of theoretical computer science, in: algorithms and complexity, vol. a, elsevier and mit press, 1990, pp. 255-300] and rigorously in 2003 by campeanu, salomaa and yu [c. campeanu, k. salomaa, s. yu, a formal study of practical regular expressions, ijfcs 14 (6) (2003) 1007-1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. we give a positive answer; and for doing so, we propose a new class of machines - regex automata systems (ras) - which are equivalent to regex. among others, these machines provide a consistent and convenient method of implementing regex in practice. we also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages.
conjugacy of finite biprefix codes. two languages x and y are called conjugates, if they satisfy the conjugacy equation xz=zy for some non-empty language z. we will compare solutions of this equation with those of the corresponding equation of words and study the case of finite biprefix codes x and y. we show that the maximal z in this case is rational. we will also characterize x and y in the case where they are both finite biprefix codes. this yields the decidability of the conjugacy of two finite biprefix codes.
a cache-friendly truncated fft. we describe a cache-friendly version of van der hoeven's truncated fft and inverse truncated fft, focusing on the case of 'large' coefficients, such as those arising in the schonhage-strassen algorithm for multiplication in z[x]. we describe two implementations and examine their performance.
identifying comparable entities on the web. web search engines are often presented with user queries that involve comparisons of real-world entities. thus far, this interaction has typically been captured by users submitting appropriately designed keyword queries for which they are presented a list of relevant documents. richer interactions that explicitly allow for a comparative analysis of entities represent a new potential direction to improve the search experience. with this in mind, we present an initial step of mining comparable entities from sources of information available to a large-scale web search engine, namely, search query logs and documents from a web crawl. our mining methods generate a diverse set of comparables consisting of entities from a broad class of categories, such as medicines, appliances, electronics, and vacation destinations.
mining tourist information from user-supplied collections. tourist photographs constitute a large part of the images uploaded to photo sharing platforms. but filtering methods are needed before one can extract useful knowledge from noisy user-supplied metadata. here we show how to extract clean trip related information (what people visit, for how long, panoramic spots) from flickr metadata. we illustrate our technique on a sample of metadata and images covering 183 cities of different size and from different parts of the world.
fast and effective histogram construction. histogram construction or sequence segmentation is a basic task with applications in database systems, information retrieval, and knowledge management. its aim is to approximate a sequence by line segments. unfortunately, the quadratic algorithm that derives an optimal histogram for euclidean error lacks the desired scalability. therefore, sophisticated approximation algorithms have been recently proposed, while several simple heuristics are used in practice. still, these solutions fail to resolve the efficiency-quality tradeoff in a satisfactory manner. in this paper we take a fresh view on the problem. we propose conceptually clear and scalable algorithms that efficiently derive high-quality histograms. we experimentally demonstrate that existing approximation schemes fail to deliver the desired efficiency and conventional heuristics do not fare well on the side of quality. on the other hand, our schemes match or exceed the quality of the former and the efficiency of the latter.
pseudo relevance feedback using semantic clustering in relevance language model. pseudo relevance feedback has demonstrated to be in general an effective technique for improving retrieval effectiveness, but the noise in the top retrieved documents still can cause topic drift problem that affects the performance of certain topics. by viewing a document as an interaction of a set of independent hidden topics, we propose a novel semantic clustering technique using independent component analysis. then within the language modeling framework, we apply the obtained semantic topic clusters into the query sampling process so that the sampling depends on the activated topics rather than on the individual document language model. therefore, we obtain a semantic cluster based relevance language model, which uses pseudo relevance feedback technique without requiring any relevance training information. we applied the model on five trec data sets. the experiments show that our model can significantly improve retrieval performance over traditional language models including relevance-based and clustering-based retrieval language models. the main contribution of the improvements comes from the estimation of the relevance model on the semantic clusters that are closely related to the query.
automatic link detection: a sequence labeling approach. the popularity of wikipedia and other online knowledge bases has recently produced an interest in the machine learning community for the problem of automatic linking. automatic hyperlinking can be viewed as two sub problems - link detection which determines the source of a link, and link disambiguation which determines the destination of a link. wikipedia is a rich corpus with hyperlink data provided by authors. it is possible to use this data to train classifiers to be able to mimic the authors in some capacity. in this paper, we introduce automatic link detection as a sequence labeling problem. conditional random fields (crfs) are a probabilistic framework for labeling sequential data. we show that training a crf with different types of features from the wikipedia dataset can be used to automatically detect links with almost perfect precision and high recall.
what's behind topic formation and development: a perspective of community core groups. over the past several years, there has been a great interest in topic detection and tracking (tdt). recently, analyzing general research trend from the huge amount of history documents also arouses considerable attention. however, existing work on tdt mainly focuses on overall trend analysis, and is unable to address questions such as "what determines the evolution of a topic?" and "when and how does a new topic get formed?". in this paper, we propose a core group model to explain the dynamics and further segment topic development. according to the division phase and interphase in the life cycle of a core group, a topic is separated into four states, i.e. birth state, extending state, saturation state and shrinkage state. experimental results on a real dataset show that the division of a core group brings on the generation of a new topic, and the progress of an entire topic is closely correlated to the growth of a core group during its interphase.
bridging the gap: complex networks meet information and knowledge management. in this article, we briefly summarize the motivation, content and structure of the cnikm'09 workshop.
exsearch: a novel vertical search engine for online barter business. e-commerce has shown its exponentially-growing business value in the past decade. however, in contrast to the successful examples in online sales, such as amazon1 and ebay2, the online barter business is still underexplored due to the lack of corresponding information aggregation service. in this paper, we design and implement a novel vertical search engine, called exsearch, to aggregate online barter information for developing the barter market. different from classical general purpose web search engines, exsearch adopts a focused crawler to gather related information from various websites. we propose to automatically extract the barter information from free-text web pages such that the unstructured information is represented in structured databases. in addition, we utilize the data mining techniques such as regression to fulfill the missing information, which cannot be extracted from the web pages. finally, we validate and rank the search results according to user queries. experimental results show that each component module in our proposed exsearch system is efficient and effective. the volunteer users are satisfied by and interested in this novel vertical search engine.
blog cascade affinity: analysis and prediction. information propagation within the blogosphere is of much importance in implementing policies, marketing research, launching new products, and other applications. in this paper, we take a microscopic view of the information propagation pattern in blogosphere by investigating blog cascade affinity. a blog cascade is a group of posts linked together discussing about the same topic, and cascade affnity refers to the phenomenon of a blog's inclination to join a specific cascade. we identify and analyze an array of features that may affect a blogger's cascade joining behavior and utilize these features to predict cascade affinity of blogs. evaluated on a real dataset consisting of 873,496 posts, our svm-based prediction achieved accuracy of 0.723 measured by f1. our experiments also showed that among all features identified, the number of friends was the most important factor affecting bloggers' inclination to join cascades.
a query model based on normalized log-likelihood. leveraging information from relevance assessments has been proposed as an effective means for improving retrieval. we introduce a novel language modeling method which uses information from each assessed document and their aggregate. while most previous approaches focus either on features of the entire set or on features of the individual relevant documents, our model exploits features of both the documents and the set as a whole. when evaluated, we show that our model is able to significantly improve over state-of-art feedback methods.
loop: local outlier probabilities. many outlier detection methods do not merely provide the decision for a single data object being or not being an outlier but give also an outlier score or "outlier factor" signaling "how much" the respective data object is an outlier. a major problem for any user not very acquainted with the outlier detection method in question is how to interpret this "factor" in order to decide for the numeric score again whether or not the data object indeed is an outlier. here, we formulate a local density based outlier detection method providing an outlier "score" in the range of [0, 1] that is directly interpretable as a probability of a data object for being an outlier.
predicting the conversion probability for items on c2c ecommerce sites. online ecommerce has been booming for a decade. for instance, as the largest online c2c marketplace (ebay), millions of new items are listed daily. due to the overwhelming number of items, the process of finding the right items to buy is sometimes daunting. in order to address this problem, this paper describes the idea of predicting the probability that a newly listed item will be sold successfully. and adjust the item exposure chances proportional according to their conversion possibility. hence, by ranking higher items that users are likely to buy, the chance that users make the purchases could be increased as well as their user satisfaction. for catalog products that have been listed repeatedly, this probability can be measured empirically. however, on c2c sites like ebay, lots of items are not product-based. they are unique, and from different sellers. therefore, in order to predict whether a new listing will be sold, we collect a large scale item set as the training data, and a set of features were used to model the average buyer shopping decision on c2c sites. experimental results verified our system's feasibility and effectiveness.
poka: identifying pareto-optimal k-anonymous nodes in a domain hierarchy lattice. data generalization is widely used to protect identities and prevent inference of sensitive information during the public release of microdata. the k-anonymity model has been extensively applied in this context. the model seeks a generalization scheme such that every individual becomes indistinguishable from at least k-1 other individuals and the loss in information while doing so is kept at a minimum. the search is performed on a domain hierarchy lattice where every node is a vector signifying the level of generalization for each attribute. an effort to understand privacy and data utility trade-offs will require knowing the minimum possible information losses of every possible value of k. however, this can easily lead to an exhaustive evaluation of all nodes in the hierarchy lattice. in this paper, we propose using the concept of pareto-optimality to obtain the desired trade-off information. a pareto-optimal generalization is one in which no other generalization can provide a higher value of k without increasing the information loss. we introduce the pareto-optimal k-anonymization (poka) algorithm to traverse the hierarchy lattice and show that the number of node evaluations required to find the pareto-optimal generalizations can be significantly reduced. results on a benchmark data set show that the algorithm is capable of identifying all pareto-optimal nodes by evaluating only 20% of nodes in the lattice.
opinion classification with tree kernel svm using linguistic modality analysis. we propose a method for classifying opinions which captures the role of linguistic modalities in the sentence. we use features than simple bag-of-words or opinion-holding predicates. the method is based on a machine learning and utilizes opinion-holding predicates and linguistic modalities as features. two different detectors help to classify the opinions: the opinion-holding predicate detector and the modality detector. an opinion in the target is first parsed into a dependency structure, and then the opinion-holding predicates and modalities stick onto the leaf nodes of the dependency tree. the whole tree is regarded as input features of the opinion, and it becomes the input of tree kernel support vector machines. we have applied method to opinions in japanese about television programs, and have confirmed the effectiveness of the method against conventional bag-of-words features, or against simple opinion-holding predicates features
inverted indexes vs. bitmap indexes in decision support systems. bitmap indexes are widely used in decision support systems (dsss) to improve query performance. in this paper, we evaluate the use of compressed inverted indexes with adapted query processing strategies from information retrieval as an alternative. in a thorough experimental evaluation on both synthetic data and data from the star schema benchmark, we show that inverted indexes are more compact than bitmap indexes in almost all cases. this compactness combined with efficient query processing strategies results in inverted indexes outperforming bitmap indexes for most queries, often significantly.
fragment-based clustering ensembles. clustering ensembles combine different clustering solutions into a single robust and stable one. most of existing methods become highly time-consuming when the data size turns to large. in this paper, we study the properties of the defined 'clustering fragment' and put forward a useful proposition. solid proofs are presented with two widely used goodness measures for clustering ensembles. finally, a new ensemble framework termed as fragment-based clustering ensembles is proposed. theoretically, most of existing methods can be improved by adopting this framework. to evaluate the proposed framework, three new methods are introduced by bring three popular clustering ensemble methods into our framework. the experimental results on several public data sets show that the three introduced methods are greatly improved in computational complexity and also achieved better or similar accurate results than the original methods.
characteristics of document similarity measures for compliance analysis. due to increased competition in the it services business, improving quality, reducing costs and shortening schedules has become extremely important. a key strategy being adopted for achieving these goals is the use of an asset-based approach to service delivery, where standard reusable components developed by domain experts are minimally modified for each customer instead of creating custom solutions. one example of this approach is the use of contract templates, one for each type of service offered. a compliance checking system that measures how well actual contracts adhere to standard templates is critical for ensuring the success of such an approach. this paper describes the use of document similarity measures - cosine similarity and latent semantic indexing - to identify the top candidate templates on which a more detailed (and expensive) compliance analysis can be performed. comparison of results of using the different methods are presented.
a co-classification framework for detecting web spam and spammers in social media web sites. social media are becoming increasingly popular and have attracted considerable attention from spammers. using a sample of more than ninety thousand known spam web sites, we found between 7% to 18% of their urls are posted on two popular social media web sites, digg.com and delicious.com. in this paper, we present a co-classification framework to detect web spam and the spammers who are responsible for posting them on the social media web sites. the rationale for our approach is that since both detection tasks are related, it would be advantageous to train them simultaneously to make use of the labeled examples in the web spam and spammer training data. we have evaluated the effectiveness of our algorithm on the delicious.com data set. our experimental results showed that the proposed co-classification algorithm significantly outperforms classifiers that learn each detection task independently.
retrieval constraints and word frequency distributions: a log-logistic model for ir. we first present in this paper an analytical view of heuristic retrieval constraints which yields simple tests to determine whether a retrieval function satisfies the constraints or not. we then review empirical findings on word frequency distributions and the central role played by burstiness in this context. this leads us to propose a formal definition of burstiness which can be used to characterize probability distributions wrt this phenomenon. we then introduce the family of information-based ir models which naturally captures heuristic retrieval constraints when the underlying probability distribution is bursty and propose a new ir model within this family, based on the log-logistic distribution. the experiments we conduct on three different collections illustrate the good behavior of the log-logistic ir model: it significantly outperforms the jelinek-mercer and dirichlet prior language models on all three collections, with both short and long queries and for both the map and the precision at 10 documents. it also outperforms the inl2 dfr model for the map, and yields results on a par with it for the precision at 10.
enhancing expertise retrieval using community-aware strategies. expertise retrieval has received increased interests in recent years, whose task is to suggest people with relevant expertise. motivated by the observation that communities could provide valuable insight and distinctive information, we investigate two community-aware strategies to enhance expertise retrieval. we first propose a new smoothing method using the community context instead of the whole collection for statistical language model in the document-based model. furthermore, a query-sensitive authorrank is proposed to model the authors' authorities according to the community co-authorship networks, and then an adaptive ranking refinement method is developed to further enhance expertise retrieval. experimental results demonstrate the effectiveness and robustness of both community-aware strategies.
exploiting bidirectional links: making spamming detection easier. previous anti-spamming algorithms based on link structure suffer from either the weakness of the page value metric or the vagueness of the seed selection. in this paper, we propose two page value metrics, avrank and hvrank. these two "values" of all the web pages can be well assessed by using the bidirectional links' information. moreover, with the help of bidirectional links, it becomes easier to enlarge the propagation coverage of seed sets. we further discuss the effectiveness of the combination of these two metrics, such as the quadratic mean of them. our experimental results show that with such two metrics, our method can filter out spam sites and identify reputable ones more effectively than previous algorithms such as trustrank.
cross-domain sentiment classification using a two-stage method. in this paper, we give out a two-stage approach for domain adaptation problem in sentiment classification. in the first stage, based on our observation that customers often use different words to comment on the similar topics in the different domains, we regard these common topics as the bridge to link the different domain-specific features. we propose a novel topic model named transfer-plsa to extract the topic knowledge between different domains. through these common topics, the features in the source domain are corresponded to the target features, so that those domain-specific knowledge can be transferred across different domains. in the second step, we use the classifier trained on the labeled examples in the source domain to pick up some informative examples in the target domain. then we retrain the classifier on these selected examples, so that the classifier is adapted for the target domain. experimental results on sentiment classification in four different domains indicate that our method outperforms other traditional methods.
predicting the volume of comments on online news stories. on-line news agents provide commenting facilities for readers to express their views with regard to news stories. the number of user supplied comments on a news article may be indicative of its importance or impact. we report on exploratory work that predicts the comment volume of news articles prior to publication using five feature sets. we address the prediction task as a two stage classification task: a binary classification identifies articles with the potential to receive comments, and a second binary classification receives the output from the first step to label articles "low" or "high" comment volume. the results show solid performance for the former task, while performance degrades for the latter.