OpenRaiser/Intern-Atlas huggingface dataset:
A system for detecting xml similarity in content and structure using relational database
Authors: Waraporn Viyanon, Sanjay Kumar Madria
Venue: CIKM
Year: 2009

In this paper, we describe a system incorporating an improved technique that detects the similarity of two XML documents based on content and structure similarity using keys. The technique consists of three major components: a subtree generator and validator, a key generator, and similarity components that compare content and structure of the XML documents. First, an XML document is stored in a relational database and extracted into small subtrees using leaf-node parents. The leaf-node parents are considered as a root of a subtree which is then recursively traversed bottom-up for matching. Second, a possible key(s) is identified in order to match XML subtrees from two documents efficiently. Key matchings help in reducing the number of comparisons dramatically. In addition, the number of subtrees to be processed is reduced in the subtree validation phase using instance statistics and taxonomic analyzer. The subtrees are matched by the key(s) first and the remaining subtrees are matched by finding degrees of similarity in content and structure. To obtain improved similarity comparison results, XML element names are transformed according to their semantic similarity. The results show that the clustering points are selected appropriately and the overall execution time is reduced dramatically.
Robust record linkage blocking using suffix arrays
Authors: Timothy de Vries, Hui Ke, Sanjay Chawla, Peter Christen
Venue: CIKM
Year: 2009

Record linkage is an important data integration task that has many practical uses for matching, merging and duplicate removal in large and diverse databases. However, a quadratic scalability for the brute force approach necessitates the design of appropriate indexing or blocking techniques. We design and evaluate an efficient and highly scalable blocking approach based on suffix arrays. Our suffix grouping technique exploits the ordering used by the index to merge similar blocks at marginal extra cost, resulting in a much higher accuracy while retaining the high scalability of the base suffix array method. Efficiently grouping similar suffixes is carried out with the use of a sliding window technique. We carry out an in-depth analysis of our method and show results from experiments using real and synthetic data, which highlights the importance of using efficient indexing and blocking in real world applications where data sets contain millions of records.
Topic analysis for topic-focused multi-document summarization
Authors: Xiaojun Wan
Venue: CIKM
Year: 2009

Topic-focused multi-document summarization has been a challenging task because the created summary is required to be biased to the given topic or query. Existing methods consider the given topic as a single coarse unit and then directly incorporate the relevance between each sentence and the single topic into the sentence evaluation process. However, the given topic is usually not well-defined and it consists of a few explicit or implicit subtopics. In this study, the related subtopics are discovered from the topic's narrative text or document set through topic analysis techniques. Then, the sentence relationships against each subtopic are considered as an individual modality and the multi-modality manifold-ranking method is proposed to evaluate and rank sentences by fusing the multiple modalities. Experimental results on the DUC benchmark datasets show the promising results of our proposed methods.
An efficient clustering algorithm for large-scale topical web pages
Authors: Lei Wang, Peng Chen, Lian&apos, en Huang
Venue: CIKM
Year: 2009

The clustering of topic-related web pages has been recognized as a foundational work in exploiting large sets of web pages such as the cases in search engines and web archive systems, which collect and preserve billions of web pages. However, this task faces great challenges both in efficiency and accuracy. In this paper we present a novel clustering algorithm for large scale topical web pages which achieves high efficiency together with considerately high accuracy. In our algorithm, a two-phase divide and conquer framework is developed to solve the efficiency problem, in which both link analysis and content analysis are utilized in mining the topical similarity between pages to achieve a high accuracy. A comprehensive experiment was conducted to evaluate our method in terms of its effectiveness, efficiency, and quality of result.
Learning to rank using evolutionary computation: immune programming or genetic programming?
Authors: Shuaiqiang Wang, Jun Ma, Jiming Liu
Venue: CIKM
Year: 2009

Nowadays ranking function discovery approaches using Evolutionary Computation (EC), especially Genetic Programming (GP), have become an important branch in the Learning to Rank for Information Retrieval (LR4IR) field. Inspired by the GP based learning to rank approaches, we provide a series of generalized definitions and a common framework for the application of EC in learning to rank research. Besides, according to the introduced framework, we propose RankIP, a ranking function discovery approach using Immune Programming (IP). Experimental results demonstrate that RankIP evidently outperforms the baselines.
Demonstration of an RFID middleware: LIT ALE manager
Authors: Qiang Wang, Wooseok Ryu, Soohan Kim, Bonghee Hong
Venue: CIKM
Year: 2009

The sharp increase of RFID tags and readers require dedicated middleware solutions that manage readers and process event data. In this paper, we demonstrate a RFID middleware called LIT ALE Manager system with key features and also illustrate overall functional components of the middleware system with implementation techniques.
Heterogeneous cross domain ranking in latent space
Authors: Bo Wang, Jie Tang, Wei Fan, Songcan Chen, Zi Yang, Yanzhu Liu
Venue: CIKM
Year: 2009

Traditional ranking mainly focuses on one type of data source, and effective modeling still relies on a sufficiently large number of labeled or supervised examples. However, in many real-world applications, in particular with the rapid growth of the Web 2.0, ranking over multiple interrelated (heterogeneous) domains becomes a common situation, where in some domains we may have a large amount of training data while in some other domains we can only collect very little. One important question is: "if there is not sufficient supervision in the domain of interest, how could one borrow labeled information from a related but heterogenous domain to build an accurate model?". This paper explores such an approach by bridging two heterogeneous domains via the latent space. We propose a regularized framework to simultaneously minimize two loss functions corresponding to two related but different information sources, by mapping each domain onto a "shared latent space", capturing similar and transferable oncepts. We solve this problem by optimizing the convex upper bound of the non-continuous loss function and derive its generalization bound. Experimental results on three different genres of data sets demonstrate the effectiveness of the proposed approach.
Beyond hyperlinks: organizing information footprints in search logs to support effective browsing
Authors: Xuanhui Wang, Bin Tan, Azadeh Shakery, ChengXiang Zhai
Venue: CIKM
Year: 2009

While current search engines serve known-item search such as homepage finding very well, they generally cannot support exploratory search effectively. In exploratory search, users do not know their information needs precisely and also often lack the needed knowledge to formulate effective queries, thus querying alone, as supported by the current search engines, is insufficient, and browsing into related information would be very useful. Currently, browsing is mostly done by following hyperlinks embedded on Web pages. In this paper, we propose to leverage search logs to allow a user to browse beyond hyperlinks with a multi-resolution topic map constructed based on search logs. Specifically, we treat search logs as "footprints" left by previous users in the information space and build a multi-resolution topic map to semantically capture and organize them in multiple granularities. Such a topic map can support a user to zoom in, zoom out, and navigate horizontally over the information space, and thus provide flexible and effective browsing capabilities for end users. To test the effectiveness of the proposed methods of supporting browsing, we rely on real search logs and a commercial search engine to implement our proposed methods. Our experimental results show that the proposed topic map is effective to support browsing beyond hyperlinks.
HyperSum: hypergraph based semi-supervised sentence ranking for query-oriented summarization
Authors: Wei Wang, Furu Wei, Wenjie Li, Sujian Li
Venue: CIKM
Year: 2009

Graph based sentence ranking algorithms such as PageRank and HITS have been successfully used in query-oriented summarization. With these algorithms, the documents to be summarized are often modeled as a text graph where nodes represent sentences and edges represent pairwise similarity relationships between two sentences. A deficiency of conventional graph modeling is its incapability of naturally and effectively representing complex group relationships shared among multiple objects. Simply squeezing complex relationships into pairwise ones will inevitably lead to loss of information which can be useful for ranking and learning. In this paper, we propose to take advantage of hypergraph, i.e. a generalization of graph, to remedy this defect. In a text hypergraph, nodes still represent sentences, yet hyperedges are allowed to connect more than two sentences. With a text hypergraph, we are thus able to integrate both group relationships formulated among multiple sentences and pairwise relationships formulated between two sentences in a unified framework. As essential work, it is first addressed in the paper that how a text hypergraph can be built for summarization by applying clustering techniques. Then, a hypergraph based semi-supervised sentence ranking algorithm is developed for query-oriented extractive summarization, where the influence of query is propagated to sentences through the structure of the constructed text hypergraph. When evaluated on DUC data sets, performance of the proposed approach is remarkable.
Minimal common container of tree patterns
Authors: Junhu Wang, Jeffrey Xu Yu, Chaoyi Pang, Chengfei Liu
Venue: CIKM
Year: 2009

Tree patterns represent important fragments of XPath. In this paper, we show that some classes of tree patterns exhibit such a property that, given a finite number of tree patterns P1, ..., Pn, there exists another pattern P (tree pattern or DAG-pattern) such that P1, ..., Pn, are all contained in P, and for any tree pattern Q belonging to a given class C, P1, ..., Pn, are contained in Q implies P is contained in Q.
Comparative document summarization via discriminative sentence selection
Authors: Dingding Wang, Shenghuo Zhu, Tao Li, Yihong Gong
Venue: CIKM
Year: 2009

Given a collection of document groups, a quick question is what are the differences in these groups. In this paper, we study a novel problem of summarizing the differences between document groups. A discriminative sentence selection method is proposed to extract the most discriminative sentences which represent the specific characteristics of each document group. Experiments on real world data sets demonstrate the effectiveness of our proposed method.
MagicCube: choosing the best snippet for each aspect of an entity
Authors: Yexin Wang, Li Zhao, Yan Zhang
Venue: CIKM
Year: 2009

Wikis are currently used in business to provide knowledge management systems, especially for individual organizations. However, building wikis manually is a laborious and time-consuming work. To assist founding wikis, we propose a methodology in this paper to automatically select the best snippets for entities as their initial explanations. Our method consists of two steps. First, we focus on extracting snippets from a given set of web pages for each entity. Starting from a seed sentence, a snippet grows up by adding the most relevant neighboring sentences into itself. The sentences are chosen by the Snippet Growth Model, which employs a distance function and an influence function to make decisions. Secondly, we pick out the best snippet for each aspect of an entity. The combination of all the selected snippets serves as the primary description of the entity. We present three ever-increasing methods to handle selection process. Experimental results based on a real data set show that our proposed method works effectively in producing primary descriptions for entities such as employee names.
Bridging the gap: complex networks meet information and knowledge management
Authors: Jun Wang, Shi Zhou, Dell Zhang
Venue: CIKM
Year: 2009

In this article, we briefly summarize the motivation, content and structure of the CNIKM'09 workshop.
iRANK: an interactive ranking framework and its application in query-focused summarization
Authors: Furu Wei, Wenjie Li, Wei Wang, Yanxiang He
Venue: CIKM
Year: 2009

We address the problem of unsupervised ensemble ranking in this paper. Traditional approaches either combine multiple ranking criteria into a unified representation to obtain an overall ranking score or to utilize certain rank fusion or aggregation techniques to combine the ranking results. Beyond the aforementioned combine-then-rank and rank-then-combine approaches, we propose a novel rank-learn-combine ranking framework, called Interactive Ranking (iRANK), which allows two base rankers to "teach" each other before combination during the ranking process by providing their own ranking results as feedback to the others so as to boost the ranking performance. This mutual ranking refinement process continues until the two base rankers cannot learn from each other any more. The overall performance is improved by the enhancement of the base rankers through the mutual learning mechanism. We apply this framework to the sentence ranking problem in query-focused summarization and evaluate its effectiveness on the DUC 2005 data set. The results are encouraging with consistent and promising improvements.
DB-IR integration and its application to a massively-parallel search engine
Authors: Kyu-Young Whang
Venue: CIKM
Year: 2009

Nowadays, as there is an increasing need to integrate the DBMS (for structured data) with Information Retrieval (IR) features (for unstructured data), DB-IR integration is becoming one of major challenges in the database area[1,2]. Extensible architectures provided by commercial object-relational DBMS(ORDBMS) vendors can be used for DB-IR integration. Here, extensions are implemented using a high-level (typically, SQL-level) interface. We call this architecture loose-coupling. The advantage of loose-coupling is ease of implementation. But, loose-coupling is not preferable for implementing new data types and operations in large databases when high performance is required. In this talk, we present a new DBMS architecture applicable to DB-IR integration, which we call tight-coupling. In tight-coupling, new data types and operations are integrated into the core of the DBMS engine in the extensible type layer. Thus, they are incorporated as the "first-class citizens"[1] within the DBMS architecture and are supported in a consistent manner with high performance. This tight-coupling architecture is being used to incorporate IR features and spatial database features into the Odysseus ORDBMS that has been under development at KAIST/AITrc for over 19 years. In this talk, we introduce Odysseus and explain its tightly-coupled IR features (U.S. patented in 2002[2]). Then, we demonstrate excellence in performance of tight-coupling by showing benchmark results. We have built a web search engine that is capable of managing 100 million web pages per node in a non-parallel configuration using Odysseus. This engine has been successfully tested in many commercial environments. This work won the Best Demonstration Award from the IEEE ICDE conference held in Tokyo, Japan, in April 2005[3]. Last, we present a design of a massively-parallel search engine using Odysseus. Recently, parallel search engines have been implemented based on scalable distributed file systems (e.g., GFS). Nevertheless, building a massively-parallel search engine using a DBMS can be an attractive alternative since it supports a higher-level (i.e., SQL-level) interface than that of a distributed file system while providing scalability. The parallel search engine designed is capable of indexing 30 billion web pages with a performance comparable to or better than those of state-of-the-art search engines.
Clustering web queries
Authors: John S. Whissell, Charles L. A. Clarke, Azin Ashkan
Venue: CIKM
Year: 2009

Despite the wide applicability of clustering methods, their evaluation remains a problem. In this paper, we present a metric for the evaluation of clustering methods. The data set to be clustered is viewed as a sample from a larger population, with clustering quality measured in terms of our predicted ability to discriminate between members of this population. We measure this property by training a classifier to recognize each cluster and measuring the accuracy of this classifier, normalized by a notion of expected accuracy. To demonstrate the applicability of this metric we apply it to Web queries. We investigated a commercially oriented data set of 1700 queries and a general data set of 4000 queries. Both sets are taken from the logs of a commercial Web search engine. Clustering is based on the contents of search engine result pages generated by executing the queries on the search engine from which they were taken. Multiple clustering algorithms are crossed with various weighting schemes to produce multiple clusterings of each query set. Our metric is used evaluate these clusterings. The results on the commercially oriented data set are compared to two pre-existing manual labelings, and are also used in an ad clickthrough experiment.
Exploring multimedia databases via optimization-based relevance feedback and the earth mover's distance
Authors: Marc Wichterich, Christian Beecks, Martin Sundermeyer, Thomas Seidl
Venue: CIKM
Year: 2009

Determining similar objects is a fundamental operation both in data mining tasks such as clustering and in query-driven object retrieval. By definition of similarity search, query objects can only be imprecise descriptions of what users are looking for in a database, and even high-quality similarity measures can only be approximations of the users' notion of similarity. To overcome these shortcomings, iterative query refinement systems have been proposed. They utilize user feedback regarding the relevance of intermediate results to adapt the query object and/or the similarity measure.
DS-Cuber: an integrated OLAP environment for data streams
Authors: Ho Jin Woo, Se Jung Shin, Woo Sock Yang, Won Suk Lee
Venue: CIKM
Year: 2009

Most of emerging applications deal with an infinite data stream in an incessant, immense and volatile manner. Consequently, it is very important to analyze not only the varying characteristics of a source data stream in a short-term period but also those in a long-term period. For this purpose, this paper demonstrates an OLAP system, DS-Cuber (Data Stream Cuber) for the analysis of data streams. The proposed system consists of two analytic components: short-term and long-term, so that it can provide an integrated analysis environment for infinite data streams. Furthermore, each of these two components supports diversified exception detection methods which can be used for the automatic identification of abnormality in the data elements of a data stream in order to guide the data cube navigation of a user effectively. Network traffic flow streams are used to demonstrate the features of the DS-Cube system.
ASIC: algebra-based structural index comparison
Authors: Yuqing Wu, Sofia Brenes, Tejas Totade, Shijin Joshua, Dhaval Damani, Michel Salim
Venue: CIKM
Year: 2009

Structural indices play a significant role in improving the efficiency of XML query evaluation. Being able to compare various structural indexing techniques is critical for a DBMS to select which indices to support, for the query optimizer to choose an index to use in query evaluation, and for DBAs to configure a database application. We present ASIC, an Algebra-based Structural Index Comparison framework that aids users in understanding the ability of different types of structural indices in answering XPath queries which have been characterized using the XPath algebra. ASIC allows users to select, configure and construct structural indices for comparison, guides users to compare the selected indices by evaluating queries of a particular XPath sub-algebra, and visually displays the index structures, query evaluation plans, and performance results for analysis and comparison.
Workload-aware trie indices for XML
Authors: Yuqing Wu, Sofia Brenes, Hyungdae Yi
Venue: CIKM
Year: 2009

Well-designed indices can dramatically improve query performance. Including query workload information can produce indices that yield better overall throughput while balancing the space and performance trade-off at the core of index design. In the context of XML, structural indices have proven to be particularly effective in supporting XPath queries by capturing the structural correlation between data components in an XML document. In this paper, we propose a family of novel workload-aware indices by taking advantage of the disk-based Ρ[k]-Trie index framework, which indexes node pairs of an XML document to facilitate index-only evaluation plans. Our indices are designed to be optimal for answering frequent path queries in one index lookup and efficient for answering non-frequent path queries using an index-only plan. Experimental results prove that our indices outperform the APEX index in overall throughput and excel in answering non-frequent queries, queries with predicates, and queries that yield empty results.
Smoothing DCG for learning to rank: a novel approach using smoothed hinge functions
Authors: Mingrui Wu, Yi Chang, Zhaohui Zheng, Hongyuan Zha
Venue: CIKM
Year: 2009

Discounted cumulative gain (DCG) is widely used for evaluating ranking functions. It is therefore natural to learn a ranking function that directly optimizes DCG. However, DCG is non-smooth, rendering gradient-based optimization algorithms inapplicable. To remedy this, smoothed versions of DCG have been proposed but with only partial success. In this paper, we first present analysis that shows it is ineffective using the gradient of the smoothed DCG to drive the optimization algorithm. We then propose a novel approach, SHF-SDCG, for smoothing DCG by using smoothed hinge functions (SHF). It has the advantage of seamlessly transition from driving the optimization mimicking pairwise learning when the ranking function does not fit the data well, to driving the optimization using DCG when the ranking function becomes more accurate. SHF-SDCG is then extended to REG-SHF-SDCG, an algorithm which gradually transits from pointwise and pairwise to listwise learning. Finally experimental results are provided to validate the effectiveness of SHF-SDCG and REG-SHF-SDCG.
XQGen: an algebra-based XPath query generator for micro-benchmarking
Authors: Yuqing Wu, Namrata Lele, Rashmi Aroskar, Sharanya Chinnusamy, Sofia Brenes
Venue: CIKM
Year: 2009

We propose XQGen, a stand-alone, algebra-based XPath generator to aid engineers in testing and improving the design of XML query engines. XQGen takes an XML schema sketch and user configurations, such as number of queries, query types, duplication factors, and branching factors as input, and generates a set of queries that comform to the schema and configurations. In addition, given a set of label-paths as workload input, XQGen is capable of generating query sets that honor the workload.