OpenRaiser/Intern-Atlas huggingface dataset:
Bitmap indexes for relational XML twig query processing
Authors: Kyong-Ha Lee, Bongki Moon
Venue: CIKM
Year: 2009

Due to an increasing volume of XML data, it is considered prudent to store XML data on an industry-strength database system instead of relying on a domain specific application or a file system. For shredded XML data stored in the relational tables, however, it may not be straightforward to apply existing algorithms for twig query processing, because most of the algorithms require XML data to be accessed in a form of streams of elements grouped by their tags and sorted in a particular order. In order to support XML query processing within the common framework of relational database systems, we first propose several bitmap indexes for supporting holistic twig joins on XML data stored in the relational tables. Since bitmap indexes are well supported in most of the commercial and open-source database systems, the proposed bitmap indexes and twig query processing algorithms can be incorporated into the relational query processing framework with more ease. The proposed query processing algorithms are efficient in terms of both time and space, since the compressed bitmap indexes stay compressed during query processing. In addition, we propose a hybrid index which computes twig query solutions with only bit-vectors, without accessing labeled XML elements stored in the relational tables.
An improved feedback approach using relevant local posts for blog feed retrieval
Authors: Yeha Lee, Seung-Hoon Na, Jong-Hyeok Lee
Venue: CIKM
Year: 2009

Blog feed search aims to identify a blog feed with a recurring interest in a given topic. In this paper, we investigate the "pseudo-relevance feedback" for blog feed search task, where its unit of relevance judgment is not based on a blog post but a blog feed (the collection of all its constituent posts). This paper focuses on two characteristics of feed search task, blog feed's topical diversity and multifaceted property of query. We propose a novel feed-level selection of local posts which uses only highly relevant local posts in each top-ranked feed, in order to capture the correct and diverse relevant information to a given topic. Experimental results show that the proposed approach outperforms traditional feedback approaches. Especially, the proposed approach gives 2% further increase of nDCG over the best performing result of TREC '08 Blog Distillation Task.
Measuring system performance and topic discernment using generalized adaptive-weight mean
Authors: Chung Tong Lee, Vishwa Vinay, Eduarda Mendes Rodrigues, Gabriella Kazai, Natasa Milic-Frayling, Aleksandar Ignjatovic
Venue: CIKM
Year: 2009

Standard approaches to evaluating and comparing information retrieval systems compute simple averages of performance statistics across individual topics to measure the overall system performance. However, topics vary in their ability to differentiate among systems based on their retrieval performance. At the same time, systems that perform well on discriminative queries demonstrate notable qualities that should be reflected in the systems' evaluation and ranking. This motivated research on alternative performance measures that are sensitive to the discriminative value of topics and the performance consistency of systems. In this paper we provide a mathematical formulation of a performance measure that postulates the dependence between the system and topic characteristics. We propose the Generalized Adaptive-Weight Mean (GAWM) measure and show how it can be computed as a fixed point of a function for which the Brouwer Fixed Point Theorem applies. This guarantees the existence of a scoring scheme that satisfies the starting axioms and can be used for ranking of both systems and topics. We apply our method to TREC experiments and compare the GAWM with the standard averages used in TREC.
Compressing tags to find interesting media groups
Authors: Matthijs van Leeuwen, Francesco Bonchi, Börkur Sigurbjörnsson, Arno Siebes
Venue: CIKM
Year: 2009

On photo sharing websites like Flickr and Zooomr, users are offered the possibility to assign tags to their uploaded pictures. Using these tags to find interesting groups of semantically related pictures in the result set of a given query is a problem with obvious applications. We analyse this problem from a Minimum Description Length (MDL) perspective and develop an algorithm that finds the most interesting groups. The method is based on Krimp, which finds small sets of patterns that characterise the data using compression. These patterns are sets of tags, often assigned together to photos. The better a database compresses, the more structure it contains and thus the more homogeneous it is. Following this observation we devise a compression-based measure. Our experiments on Flickr data show that the most interesting and homogeneous groups are found. We show extensive examples and compare to clusterings on the Flickr website.
Networks, communities and kronecker products
Authors: Jure Leskovec
Venue: CIKM
Year: 2009

Emergence of the web and online computing applications gave rise to rich large scale social activity data. One of the principal challenges then is to build models and understanding of the structure of such large social and information networks. Here I present our work on clustering and community structure in large networks, where clusters are thought of as sets of nodes that are better connected internally than to the rest of the network. We find that large networks have very different clustering structure from well studied small social networks and graphs that are well-embeddable in a low-dimensional structure. In networks of millions of nodes tight clusters exist at only very small size scales up to around 100 nodes, while at large size scales networks becomes expander like. A network model based on Kronecker products efficiently models such core-periphery network structures. The results suggest broader implications for data analysis and machine learning in sparse and noisy high-dimensional social and information networks, where intuitive notions about cluster quality fail.
Blog cascade affinity: analysis and prediction
Authors: Hui Li, Sourav S. Bhowmick, Aixin Sun
Venue: CIKM
Year: 2009

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.
Structure-aware indexing for keyword search in databases
Authors: Guoliang Li, Jianhua Feng, Jianyong Wang
Venue: CIKM
Year: 2009

Most of existing methods of keyword search over relational databases find the Steiner trees composed of relevant tuples as the answers. They identify the Steiner trees by discovering the rich structural relationships between tuples, and neglect the fact that such structural relationships can be pre-computed and indexed. Tuple units that are composed of most relevant tuples are proposed to address this problem. Tuple units can be precomputed and indexed. Existing methods identify a single tuple unit to answer keyword queries. They, however, may involve false negatives as in many cases a single tuple unit cannot answer a keyword query. Instead, multiple tuple units should be integrated to answer keyword queries. To address this problem, in this paper, we study how to integrate multiple related tuple units to effectively answer keyword queries. We devise novel indices and incorporate the structural relationships between different tuple units into the indices. We use the indices to efficiently and progressively identify the top-k relevant answers. We have implemented our method in real database systems, and the experimental results show that our approach achieves high search efficiency and accuracy, and outperforms state-of-the-art methods significantly.
Incorporating robustness into web ranking evaluation
Authors: Xin Li, Fan Li, Shihao Ji, Zhaohui Zheng, Yi Chang, Anlei Dong
Venue: CIKM
Year: 2009

In many Web search engines, a ranking function is selected for deployment mainly by comparing the relevance measurements over candidates. Due to the dynamical nature of the Web, the ranking features and the query and URL distribution on which the ranking functions are built, may change dramatically over time. The actual relevance of the function may degrade, and thus the previous function selection conclusions become invalid. In this work we suggest to select Web ranking functions according to both their relevance and robustness to the changes that may lead to relevance degradation over time. We argue that the ranking robustness can be effectively measured by taking into account the ranking score distribution across search results. We then propose two alternatives to the NDCG metric that both incorporate ranking robustness into ranking function evaluation and selection. A machine learning approach is developed to learn the parameters that control the metric sensitivity to score turbulence, from human-judged preference data.
Supporting context-based query in personal DataSpace
Authors: Yukun Li, Xiaofeng Meng
Venue: CIKM
Year: 2009

Many users need to refer to content in existing files (pictures, tables, emails, web pages and etc.) when they write doc-uments(programs, presentations, proposals and etc.), and often need to revisit these referenced files for review, re-vision or reconfirmation. Therefore it is meaningful to dis-cover an approach to help users revisit these references effec-tively. Traditional approaches(file explorer, desktop search, and etc.) fail to work in this case. In this paper, we propose an efficient solution for this problem. We firstly define a new personal data relationship: Context-based Reference(CR), which is generated by user behaviors. We also propose ef-ficient methods to identify CR relationship and present a new type of query based on it: Context-based Query(C-Query), which helps users efficiently revisit personal docu-ments based on CR relationship. Our experiments validate the effectiveness and efficiency of our methods.
Efficient join processing on uncertain data streams
Authors: Xiang Lian, Lei Chen
Venue: CIKM
Year: 2009

Join processing in the streaming environment has many practical applications such as data cleaning and outlier detection. Due to the inherent uncertainty in the real-world data, it has become an increasingly important problem to consider the join processing on uncertain data streams, where the incoming data at each timestamp are uncertain and imprecise. Different from the static databases, processing uncertain data streams has its own requirements such as the limited memory, small response time, and so on. To tackle the challenges with respect to efficiency and effectiveness, in this paper, we formalize the problem of join on uncertain data streams (USJ), which can guarantee the accuracy of USJ answers over uncertain data, and propose effective pruning methods to filter out false alarms. We integrate the pruning methods into an efficient query procedure for incrementally maintaining USJ answers. Extensive experiments have been conducted to demonstrate the efficiency and effectiveness of our approaches.
Feature engineering on event-centric surrogate documents to improve search results
Authors: Wenhui Liao, Isabelle Moulinier
Venue: CIKM
Year: 2009

We investigate the task of re-ranking search results based on query log information. Prior work has considered this problem as either the task of learning document rankings of using features based on user behavior, or as the task of enhancing documents and queries using log data. Our contribution combines both. We distill log information into event-centric surrogate documents (ESDs), and extract features from these ESDs to be used in a learned ranking function. Our experiments on a legal corpus demonstrate that features engineered on surrogate documents lead to improved rankings, in particular when the original ranking is of poor quality.
A targeted web crawling for building malicious javascript collection
Authors: Peter Likarish, Eunjin Jung
Venue: CIKM
Year: 2009

Malicious javascript frequently serves as a starting point of web-based attacks, in particular cross-site scripting. Thus detecting malicious javascript before execution can protect users from attacks such as malware infection, drive-by downloads, and even from participating in denial-of-service attacks as part of botnet sometimes. A large collection of malicious javascript would help with detector development, but by the time crawler arrives at blacklisted domains attackers and malicious scripts are often long gone. We have used classifiers to direct a web crawler better towards more likely locations of malicious scripts, and show how this targeted web crawler performs compared to crawler seed with blacklisted-domains.
Semantic queries in databases: problems and challenges
Authors: Lipyeow Lim, Haixun Wang, Min Wang
Venue: CIKM
Year: 2009

Supporting semantic queries in relational databases is essential to many advanced applications. Recently, with the increasing use of ontology in various applications, the need for querying relational data together with its related ontology has become more urgent. In this paper, we identify and discuss the problem of querying relational data with its ontologies. Two fundamental challenges make the problem interesting. First, it is extremely difficult to express queries against graph structured ontology in the relational query language SQL, and second, in many cases where data and its related ontology are complicated, queries are usually not precise, that is, users often have only a vague notion, rather than a clear understanding and definition, of what they query for. We outline a query-by-example approach that enables us to support semantic queries in relational databases with ease. Instead of endeavoring to incorporate ontology into relational form and create new language constructs to express such queries, we ask the user to provide a small number of examples that satisfy the query she has in mind. Using these examples as seeds, the system infers the exact query automatically, and the user is therefore shielded from the complexity of interfacing with the ontology.
Joint sentiment/topic model for sentiment analysis
Authors: Chenghua Lin, Yulan He
Venue: CIKM
Year: 2009

Sentiment analysis or opinion mining aims to use automated tools to detect subjective information such as opinions, attitudes, and feelings expressed in text. This paper proposes a novel probabilistic modeling framework based on Latent Dirichlet Allocation (LDA), called joint sentiment/topic model (JST), which detects sentiment and topic simultaneously from text. Unlike other machine learning approaches to sentiment classification which often require labeled corpora for classifier training, the proposed JST model is fully unsupervised. The model has been evaluated on the movie review dataset to classify the review sentiment polarity and minimum prior information have also been explored to further improve the sentiment classification accuracy. Preliminary experiments have shown promising results achieved by JST.
MatchSim: a novel neighbor-based similarity measure with maximum neighborhood matching
Authors: Zhenjiang Lin, Michael R. Lyu, Irwin King
Venue: CIKM
Year: 2009

The problem of measuring similarity between web pages arises in many important Web applications, such as search engines and Web directories. In this paper, we propose a novel neighbor-based similarity measure called MatchSim, which uses only the neighborhood structure of web pages. Technically, MatchSim recursively defines similarity between web pages by the average similarity of the maximum matching between their neighbors. Our method extends the traditional methods which simply count the numbers of common and/or different neighbors. It also successfully overcomes a severe counterintuitive loophole in SimRank, due to its strict consistency with the intuitions of similarity. We give the computational complexity of MatchSim iteration. The accuracy of MatchSim is compared against others on two real datasets. The results show that our method performs best in most cases.
Computational community interest for ranking
Authors: Xiaozhong Liu, Vadim von Brzeski
Venue: CIKM
Year: 2009

Ranking documents with respect to users' information needs is a challenging task, due, in part, to the dynamic nature of users' interest with respect to a query, which can change over time. In this paper, we propose an innovative method for characterizing the interests of a community of users at a specific point in time and for using this characterization to alter the ranking of documents retrieved for a query. By generating a community interest vector (CIV) for a given query, we measure the community interest by computing a score in a specific document or web page retrieved by the query. This score is based on a continuously updated set of recent (daily or past few hours) user-oriented text data. When applying our method in ranking Yahoo! Buzz results, the CIV score improves relevant results by 16% as determined by real-world user evaluation.
Incremental query evaluation for support vector machines
Authors: Danzhou Liu, Kien A. Hua
Venue: CIKM
Year: 2009

Support vector machines (SVMs) have been widely used in multimedia retrieval to learn a concept in order to find the best matches. In such a SVM active learning environment, the system first processes k sampling queries and top-k uncertain queries to select the candidate data items for training. The user's top-k relevant queries are then evaluated to compute the answer. This approach has shown to be effective. However, it suffers from the scalability problem associated with larger database sizes. To address this limitation, we propose an incremental query evaluation technique for these three types of queries. Based on the observation that most queries are not revised dramatically during the iterative evaluation, the proposed technique reuses the results of previous queries to reduce the computation cost. Furthermore, this technique takes advantage of a tuned index structure to efficiently prune irrelevant data. As a result, only a small portion of the data set needs to be accessed for query processing. This index structure also provides an inexpensive means to process the set of candidates to evaluate the final query result. This technique can work with different kernel functions and kernel parameters. Our experimental results indicate that the proposed technique significantly reduces the overall computation cost, and offers a promising solution to the scalability issue.
Post-rank reordering: resolving preference misalignments between search engines and end users
Authors: Chao Liu, Mei Li, Yi-Min Wang
Venue: CIKM
Year: 2009

No search engine is perfect. A typical type of imperfection is the preference misalignment between search engines and end users, e.g., from time to time, web users skip higher-ranked documents and click on lower-ranked ones. Although search engines have been aggressively incorporating clickthrough data in their ranking, it is hard to eliminate such misalignments across millions of queries. Therefore, we, in this paper, propose to accompany a search engine with an "always-on" component that reorders documents on a per-query basis, based on user click patterns. Because of positional bias and dependencies between clicks, we show that a simple sort based on click counts (and its variants), albeit intuitive and useful, is not precise enough.
Efficient processing of twig pattern matching in fuzzy XML
Authors: Jian Liu, Zong Min Ma, Li Yan
Venue: CIKM
Year: 2009

In order to find all occurrences of a twig pattern in XML documents, a considerable amount of twig pattern matching algorithms have been proposed. At the same time, previous work mainly focuses on twig pattern query under the complete semantics. However, there is often a need to produce partial answers because XML data may have missing sub-elements. Furthermore, the existed works fall short in their ability to support twig pattern query under different semantics in fuzzy XML. In this paper, we study the problem of twig matches in fuzzy XML. We begin by introducing the extended region scheme to accurately and effectively represent nodes information in fuzzy XML. We then discuss the fuzzy query semantics and compute the membership information by using Einstein operator instead of Zadeh's min-max technique. On the basis, we propose two efficient algorithms for querying twig under complete and incomplete semantics in fuzzy XML. The experimental results show that our proposed algorithms can perform on the fuzzy twig pattern matching efficiently.
Effective XML content and structure retrieval with relevance ranking
Authors: Xiping Liu, Changxuan Wan, Lei Chen
Venue: CIKM
Year: 2009

XML documents can be retrieved by means of not only content-only (CO) queries, but also content-and-structure (CAS) queries. Though promising better retrieval precision, CAS queries introduce several new challenges. To address these challenges, we propose a novel approach for XML CAS retrieval. The distinctive feature of the approach is that it adopts a content-oriented point of view. Specifically, the approach first decomposes a CAS query into several fragments, then retrieves results for each query fragment in a content-centric way, and finally scores each answer node. The approach is adaptive to versatile homogeneous and heterogeneous data environments. To assess the relevance of retrieval results to a query fragment, we present a scoring strategy that measures relevance from both content and structure perspectives. In addition, an effective approach is proposed to infer answer nodes based on the CAS query and document structure. An efficient algorithm is also presented for CAS retrieval. Finally, we demonstrate the effectiveness of the proposed methods through comprehensive experimental studies.
Cross-domain sentiment classification using a two-stage method
Authors: Kang Liu, Jun Zhao
Venue: CIKM
Year: 2009

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.