waashk/dblp huggingface dataset:
k nearest neighbor classification across multiple private databases. distributed privacy preserving data mining tools are critical for mining multiple databases with a minimum information disclosure. we present a framework including a general model as well as multi-round algorithms for mining horizontally partitioned databases using a privacy preserving k nearest neighbor (knn) classifier.
distributed spatio-temporal similarity search. in this paper we introduce the distributed spatio-temporal similarity search problem: given a query trajectory q, we want to find the trajectories that follow a motion similar to q, when each of the target trajectories is segmented across a number of distributed nodes. we propose two novel algorithms, ub-k and ublb-k, which combine local computations of lower and upper bounds on the matching between the distributed subsequences and q. such an operation generates the desired result without pulling together all the distributed subsequences over the fundamentally expensive communication medium. our solutions find applications in a wide array of domains, such as cellular networks, wild life monitoring and video surveillance. our experimental evaluation using realistic data demonstrates that our framework is both efficient and robust to a variety of conditions.
cto: concept tree based semantic overlay for pure peer-to-peer information retrieval. inspired by how search behavior works in human society, we propose cto, a self-organized semantic overlay based on concept tree for p2p ir infrastructure, which is efficient for full text search in pure p2p environment without any central control or powerful peer as hub node. especially, cto performs very well on searching the unpopular resources shared by a few peers. in our experiment, while searching for the scarce documents shared by the peers, cto achieves about 80% recall rate when the search covers less than 5% peers in the overlay. the search latency of cto is also very low, which is controlled in the range about 5~12 hops.
query-specific clustering of search results based on document-context similarity scores. this paper presents a pilot study of query-specific clustering that uses our novel document-context based similarity scores as compared with document similarity scores. clustering is applied to the top 1000 retrieved documents for a given query. clustering effectiveness is evaluated based on the mk1 score for trec-2, trec-6 and trec-7 test collections. encouraging results were obtained whereby document-context clustering produces better mk1 scores than document clustering with a 95% confidence level if precision and recall are equally important.
movie review mining and summarization. with the flourish of the web, online review is becoming a more and more useful and important information resource for people. as a result, automatic review mining and summarization has become a hot research topic recently. different from traditional text summarization, review mining and summarization aims at extracting the features on which the reviewers express their opinions and determining whether the opinions are positive or negative. in this paper, we focus on a specific domain - movie review. a multi-knowledge based approach is proposed, which integrates wordnet, statistical analysis and movie knowledge. the experimental results show the effectiveness of the proposed approach in movie review mining and summarization.
towards interactive indexing for large chinese calligraphic character databases. in this paper, based on a novel shape-similarity-based retrieval method, we propose an interactive partial-distance-map (pdm)- based high-dimensional indexing scheme to speed up the retrieval performance of the large chinese calligraphic character databases. specifically, we use the approximate minimal bounding hyper- sphere of query character to search the pdm and utilize the users' relevance feedback to refine the search process. we conduct comprehensive experiments to testify the efficiency and effectiveness of the proposed method.
a comparison of statistical significance tests for information retrieval evaluation. information retrieval (ir) researchers commonly use three tests of statistical significance: the student's paired t-test, the wilcoxon signed rank test, and the sign test. other researchers have previously proposed using both the bootstrap and fisher's randomization (permutation) test as non-parametric significance tests for ir but these tests have seen little use. for each of these five tests, we took the ad-hoc retrieval runs submitted to trecs 3 and 5-8, and for each pair of runs, we measured the statistical significance of the difference in their mean average precision. we discovered that there is little practical difference between the randomization, bootstrap, and t tests. both the wilcoxon and sign test have a poor ability to detect significance and have the potential to lead to false detections of significance. the wilcoxon and sign tests are simplified variants of the randomization test and their use should be discontinued for measuring the significance of a difference between means.
coupling feature selection and machine learning methods for navigational query identification. it is important yet hard to identify navigational queries in web search due to a lack of sufficient information in web queries, which are typically very short. in this paper we study several machine learning methods, including naive bayes model, maximum entropy model, support vector machine (svm), and stochastic gradient boosting tree (sgbt), for navigational query identification in web search. to boost the performance of these machine techniques, we exploit several feature selection methods and propose coupling feature selection with classification approaches to achieve the best performance. different from most prior work that uses a small number of features, in this paper, we study the problem of identifying navigational queries with thousands of available features, extracted from major commercial search engine results, web search user click data, query log, and the whole web's relational content. a multi-level feature extraction system is constructed.our results on real search data show that 1) among all the features we tested, user click distribution features are the most important set of features for identifying navigational queries. 2) in order to achieve good performance, machine learning approaches have to be coupled with good feature selection methods. we find that gradient boosting tree, coupled with linear svm feature selection is most effective. 3) with carefully coupled feature selection and classification approaches, navigational queries can be accurately identified with 88.1% f1 score, which is 33% error rate reduction compared to the best uncoupled system, and 40% error rate reduction compared to a well tuned system without feature selection.
automatic computation of semantic proximity using taxonomic knowledge. taxonomic measures of semantic proximity allow us to compute the relatedness of two concepts. these metrics are versatile instruments required for diverse applications, e.g., the semantic web, linguistics, and also text mining. however, most approaches are only geared towards hand-crafted taxonomic dictionaries such as wordnet, which only feature a limited fraction of real-world concepts. more specific concepts, and particularly instances of concepts, i.e., names of artists, locations, brand names, etc., are not covered.the contributions of this paper are two fold. first, we introduce a framework based on google and the open directory project (odp), enabling us to derive the semantic proximity between arbitrary concepts and instances. second, we introduce a new taxonomy-driven proximity metric tailored for our framework. studies with human subjects corroborate our hypothesis that our new metric outperforms benchmark semantic proximity metrics and comes close to human judgement.
index compression is good, especially for random access. index compression techniques are known to substantially decrease the storage requirements of a text retrieval system. as a side-effect, they may increase its retrieval performance by reducing disk i/o overhead. despite this advantage, developers sometimes choose to store index data in uncompressed form, in order to not obstruct random access into each index term's postings list. in this paper, we show that index compression does not harm random access performance. in fact, we demonstrate that, in some cases, random access into a term's postings list may be realized more efficiently if the list is stored in compressed form instead of uncompressed. this is regardless of whether the index is stored on disk or in main memory, since both types of storage - hard drives and ram - do not support efficient random access in the first place.
on the structural properties of massive telecom call graphs: findings and implications. with ever growing competition in telecommunications markets, operators have to increasingly rely on business intelligence to offer the right incentives to their customers. toward this end, existing approaches have almost solely focussed on the individual behaviour of customers. call graphs, that is, graphs induced by people calling each other, can allow telecom operators to better understand the interaction behaviour of their customers, and potentially provide major insights for designing effective incentives.in this paper, we use the call detail records of a mobile operator from four geographically disparate regions to construct call graphs, and analyse their structural properties. our findings provide business insights and help devise strategies for mobile telecom operators. another goal of this paper is to identify the shape of such graphs. in order to do so, we extend the well-known reachability analysis approach with some of our own techniques to reveal the shape of such massive graphs. based on our analysis, we introduce the treasure-hunt model to describe the shape of mobile call graphs. the proposed techniques are general enough for analysing any large graph. finally, how well the proposed model captures the shape of other mobile call graphs needs to be the subject of future studies.
trips and tides: new algorithms for tree mining. recent research in data mining has progressed from mining frequent itemsets to more general and structured patterns like trees and graphs. in this paper, we address the problem of frequent subtree mining that has proven to be viable in a wide range of applications such as bioinformatics, xml processing, computational linguistics, and web usage mining. we propose novel algorithms to mine frequent subtrees from a database of rooted trees. we evaluate the use of two popular sequential encodings of trees to systematically generate and evaluate the candidate patterns. the proposed approach is very generic and can be used to mine embedded or induced subtrees that can be labeled, unlabeled, ordered, unordered, or edge-labeled. our algorithms are highly cache-conscious in nature because of the compact and simple array-based data structures we use. typically, l1 and l2 hit rates above 99% are observed. experimental evaluation showed that our algorithms can achieve up to several orders of magnitude speedup on real datasets when compared to state-of-the-art tree mining algorithms.
optimisation methods for ranking functions with multiple parameters. optimising the parameters of ranking functions with respect to standard ir rank-dependent cost functions has eluded satisfactory analytical treatment. we build on recent advances in alternative differentiable pairwise cost functions, and show that these techniques can be successfully applied to tuning the parameters of an existing family of ir scoring functions (bm25), in the sense that we cannot do better using sensible search heuristics that directly optimize the rank-based cost function ndcg. we also demonstrate how the size of training set affects the number of parameters we can hope to tune this way.
efficient search ranking in social networks. in social networks such as orkut, www.orkut.com, a large portion of the user queries refer to names of other people. indeed, more than 50% of the queries in orkut are about names of other users, with an average of 1.8 terms per query. further, the users usually search for people with whom they maintain relationships in the network. these relationships can be modelled as edges in a friendship graph, a graph in which the nodes represent the users. in this context, search ranking can be modelled as a function that depends on the distances among users in the graph, more specifically, of shortest paths in the friendship graph. however, application of this idea to ranking is not straightforward because the large size of modern social networks (dozens of millions of users) prevents efficient computation of shortest paths at query time. we overcome this by designing a ranking formula that strikes a balance between producing good results and reducing query processing time. using data from the orkut social network, which includes over 40 million users, we show that our ranking, augmented by this new signal, produces high quality results, while maintaining query processing time small.
a structure-oriented relevance feedback method for xml retrieval. relevance feedback (rf) is a technique allowing to enrich an initial query according to the user feedback. the goal is to express more precisily the user's needs. some open issues appear when considering semi-structured documents like xml documents. most of the rf approaches proposed in xml retrieval are simple adaptations of traditional rf to the new granularity of information. they enrich queries by adding terms extracted from relevant elements instead of terms extracted from whole documents. in this paper we show how structural constraints can also be used in rf. we propose a new approach that is able to extend the initial query by adding one or more generative structures. this approach is applied to unstructured queries. experiments are carried out on inex collection and results show the interest of our method.
probabilistic document-context based relevance feedback with limited relevance judgments. this paper presents our novel relevance feedback (rf) algorithm that uses the probabilistic document-context based retrieval model with limited relevance judgments for document re-ranking. probabilities of the document-context based retrieval model are estimated from the top n (=20) documents in the initial retrieval. we use document-context based cosine similarity measure to find similar data for better probability estimation in order to reduce the data scarcity problem and the negative weighting problem. our rf algorithm is promising because its mean average precision is statistically significantly better than the baseline using trec-6 and trec-7 data collections.
a novel scheme for domain-transfer problem in the context of sentiment analysis. in this work, we attempt to tackle domain-transfer problem by combining old-domain labeled examples with new-domain unlabeled ones. the basic idea is to use old-domain-trained classifier to label some informative unlabeled examples in new domain, and retrain the base classifier over these selected examples. the experimental results demonstrate that proposed scheme can significantly boost the accuracy of the base sentiment classifier on new domain.
term context models for information retrieval. at their heart, most if not all information retrieval models utilize some form of term frequency.the notion is that the more often a query term occurs in a document, the more likely it is that document meets an information need. we examine an alternative. we propose a model which assesses the presence of a term in a document not by looking at the actual occurrence of that term, but by a set of non-independent supporting terms, i.e. context. this yields a weighting for terms in documents which is different from and complementary to tf-based methods, and is beneficial for retrieval.
a combination of trie-trees and inverted files for the indexing of set-valued attributes. set-valued attributes frequently occur in contexts like market-basked analysis and stock market trends. late research literature has mainly focused on set containment joins and data mining without considering simple queries on set valued attributes. in this paper we address superset, subset and equality queries and we propose a novel indexing scheme for answering them on set-valued attributes. the proposed index superimposes a trie-tree on top of an inverted file that indexes a relation with set-valued data. we show that we can efficiently answer the aforementioned queries by indexing only a subset of the most frequent of the items that occur in the indexed relation. finally, we show through extensive experiments that our approach outperforms the state of the art mechanisms and scales gracefully as database size grows.
evaluation by comparing result sets in context. familiar evaluation methodologies for information retrieval (ir) are not well suited to the task of comparing systems in many real settings. these systems and evaluation methods must support contextual, interactive retrieval over changing, heterogeneous data collections, including private and confidential information.we have implemented a comparison tool which can be inserted into the natural ir process. it provides a familiar search interface, presents a small number of result sets in side-by-side panels, elicits searcher judgments, and logs interaction events. the tool permits study of real information needs as they occur, uses the documents actually available at the time of the search, and records judgments taking into account the instantaneous needs of the searcher.we have validated our proposed evaluation approach and explored potential biases by comparing different whole-of-web search facilities using a web-based version of the tool. in four experiments, one with supplied queries in the laboratory and three with real queries in the workplace, subjects showed no discernable left-right bias and were able to reliably distinguish between high- and low-quality result sets. we found that judgments were strongly predicted by simple implicit measures.following validation we undertook a case study comparing two leading whole-of-web search engines. the approach is now being used in several ongoing investigations.
practical private data matching deterrent to spoofing attacks. private data matching between the data sets of two potentially distrusted parties has a wide range of applications. however, existing solutions have substantial weaknesses and do not meet the needs of many practical application scenarios. in particular, practical private data matching applications often require discouraging the matching parties from spoofing their private inputs. in this paper, we address this challenge by forcing the matching parties to "escrow" the data they use for matching to an auditorial agent, and in the "after-the-fact" period, they undertake the liability to attest the genuineness of the escrowed data.
high-performance distributed inverted files. we present a general method of parallel query processing that allows scalable performance on distributed inverted files. the method allows the realization of a hybrid that combines the advantages of the document and term partitioned inverted files.
adapting association patterns for text categorization: weaknesses and enhancements. the use of association patterns for text categorization has attracted great interest and a variety of useful methods have been developed. however, the key characteristics of pattern-based text categorization remain unclear. indeed, there are still no concrete answers for the following two questions: first, what kind of association patterns are the best candidate for pattern-based text categorization? second, what is the most desirable way to use patterns for text categorization? in this paper, we focus on answering the above two questions. specifically, we show that hyperclique patterns are more desirable than frequent patterns for text categorization. along this line, we develop an algorithm for text categorization using hyperclique patterns. the experimental results show that our method provides better performance than state-of-the-art methods in terms of both computational performance and classification accuracy.
classification spanning correlated data streams. in many applications, classifiers need to be built based on multiple related data streams. for example, stock streams and news streams are related, where the classification patterns may involve features from both streams. thus instead of mining on a single isolated stream, we need to examine multiple related data streams in order to find such patterns and build an accurate classifier. other examples of related streams include traffic reports and car accidents, sensor readings of different types or at different locations, etc. in this paper, we consider the classification problem defined over sliding-window join of several input data streams. as the data streams arrive in fast pace and the many-to-many join relationship blows up the data arrival rate even more, it is impractical to compute the join and then build the classifier each time the window slides forward. we present an efficient algorithm to build a naïve bayesian classifier in such context. our method does not need to perform the join operations but is still able to build exactly the same classifier as if built on the joined result. it only examines each input tuple twice, independent of the number of tuples it joins in other streams, therefore, is able to keep pace with the fast arriving data streams in the presence of many-to-many join relationships. the experiments confirmed that our classification algorithm is more efficient than conventional methods while maintaining good classification accuracy.
ranking robustness: a novel framework to predict query performance. in this paper, we introduce the notion of ranking robustness, which refers to a property of a ranked list of documents that indicates how stable the ranking is in the presence of uncertainty in the ranked documents. we propose a statistical measure called the robustness score to quantify this notion. we demonstrate that the robustness score significantly and consistently correlates with query performance in a variety of trec test collections including the gov2 collection. we compare the robustness score with the clarity score method which is the state-of-the-art technique for query performance prediction. our experimental results show that the robustness score performs better than or at least as good as the clarity score. we find that the clarity score is barely correlated with query performance on the gov2 collection while the correlation between the robustness score and query performance remains significant. we also notice that a combination of the two usually results in more prediction power.
an on-line interactive method for finding association rules data streams. in order to trace the changes of association rules over an online data stream efficiently, this paper proposes two different methods of generating all association rules directly over the changing set of currently frequent itemsets. while all of the currently frequent itemsets are monitored by the estdec method, all the association rules of every frequent itemset in the prefix tree of the estdec method are generated. for this purpose, a traversal stack is introduced to efficiently enumerate all association rules. these online methods can avoid the drawbacks of the conventional two-step approach. in an on-line environment, a user may be interested in finding those association rules whose antecedents or consequents are fixed to be a specific itemset. since generating all the association rules may take too long to produce them timely, two additional methods, namely assoc-x and assoc-y, are introduced. finally, the proposed methods are compared by a series of experiments to identify their various characteristics.