OpenRaiser/Intern-Atlas huggingface dataset:
A flexible simulation environment for flash-aware algorithms
Authors: Peiquan Jin, Xuan Su, Zhi Li, Lihua Yue
Venue: CIKM
Year: 2009

In this paper, we present a flexible simulation environment for the performance evaluation of flash-aware algorithms, which is called Flash-DBSim. The main purpose of Flash-DBSim is to provide a configurable virtual flash disk for upper systems, such as file system and DBMS, so that the algorithms in those systems can be easily evaluated on different types of flash disks. Moreover, it also offers a prototyping environment for those algorithms inside flash disk, e.g. the algorithms for garbage collection or wear-leveling. After an overview of the general features of Flash-DBSim, we discuss the architecture of Flash-DBSim. And finally, a case study of Flash-DBSim's demonstration is presented.
Identifying static analysis techniques for finding non-fix hunks in fix revisions
Authors: Yungbum Jung, Hakjoo Oh, Kwangkeun Yi
Venue: CIKM
Year: 2009

Mining software repositories for bug detection requires accurate techniques of identifying bug-fix revisions. There have been many researches to find exact bug-fix revisions. However there are still noises, we call these noises non-fix hunks, even in exactly identified bug-fix revisions. Our goal is to remove these non-fix hunks automatically. First we inspected every 50 bug-fix revisions of three open source projects (Eclipse, Lucene, and Columba). Among total 2146 hunks we found 179 non-fix hunks. We classified these non-fix hunks into 11 patterns. For all patterns we enumerate enabling static analysis techniques.
Query by analogical example: relational search using web search engine indices
Authors: Makoto P. Kato, Hiroaki Ohshima, Satoshi Oyama, Katsumi Tanaka
Venue: CIKM
Year: 2009

We describe methods to search with a query by example in a known domain for information in an unknown domain by exploiting Web search engines. Relational search is an effective way to obtain information in an unknown field for users. For example, if an Apple user searches for Microsoft products, similar Apple products are important clues for the search. Even if the user does not know keywords to search for specific Microsoft products, the relational search returns a product name by querying simply an example of Apple products. More specifically, given a tuple containing three terms, such as (Apple, iPod, Microsoft), the term Zune can be extracted from the Web search results, where Apple is to iPod what Microsoft is to Zune. As a previously proposed relational search requires a huge text corpus to be downloaded from the Web, the results are not up-to-date and the corpus has a high construction cost. We introduce methods for relational search by using Web search indices. We consider methods based on term co-occurrence, on lexico-syntactic patterns, and on combinations of the two approaches. Our experimental results showed that the combination methods got the highest precision, and clarified the characteristics of the methods.
Provenance query evaluation: what's so special about it?
Authors: Anastasios Kementsietsidis, Min Wang
Venue: CIKM
Year: 2009

While provenance has been extensively studied in the literature, the efficient evaluation of provenance queries remains an open problem. Traditional query optimization techniques, like the use of general-purpose indexes, or the materialization of provenance data, fail on different fronts to address the problem. Therefore, the need to develop provenance-aware access methods becomes apparent. This paper starts by identifying some key requirements that are to a large extent specific to provenance queries and are necessary for their efficient evaluation. The first such property, called duality, requires that a single access method is used to evaluate both backward provenance queries (which input items of some analysis generate an output item) and forward provenance queries (which outputs of some analysis does an input item generate). The second property, called locality, guarantees that provenance query evaluation times should depend mainly on the size of the provenance query results and should be largely independent of the total size of provenance data. Motivated by the above, we identify proper data structures with the aforementioned properties, we implement them, and through a detailed set of experiments, we illustrate their effectiveness on the evaluation of provenance queries.
Data-driven compound splitting method for english compounds in domain names
Authors: Sanjeet Khaitan, Arumay Das, Sandeep Gain, Adithi Sampath
Venue: CIKM
Year: 2009

Significant amount of literature is available on compound splitting of long words albeit for non-English languages- especially European. Not surprisingly, there has been not much work for English as it is not a compounding language like some of its European counterparts. However, Internet domain names in general are compound English words, e.g. bankofamerica.com". Compound splitting can be effectively employed to extract information from domain names. In this paper, an data-driven learning technique for splitting English compound words is described which among others uses features like normalized frequency, length of parts and n-gram. The splitting F-measure is higher than the published approaches. We applied this technique on a real life web search application where the queries are mistyped domain names routed through sources like ISPs and browsers. Relevant and meaningful keywords were extracted out and shown to the user as a value added search option. Results show a very high click-through rate and increased commercial value.
An empirical study on using hidden markov model for search interface segmentation
Authors: Ritu Khare, Yuan An
Venue: CIKM
Year: 2009

This paper describes a hidden Markov model (HMM) based approach to perform search interface segmentation. Automatic processing of an interface is a must to access the invisible contents of deep Web. This entails automatic segmentation, i.e., the task of grouping related components of an interface together. While it is easy for a human to discern the logical relationships among interface components, machine processing of an interface is difficult. In this paper, we propose an approach to segmentation that leverages the probabilistic nature of the interface design process. The design process involves choosing components based on the underlying database query requirements, and organizing them into suitable patterns. We simulate this process by creating an "artificial designer" in the form of a 2-layered HMM. The learned HMM acquires the implicit design knowledge required for segmentation. We empirically study the effectiveness of the approach across several representative domains of deep Web. In terms of segmentation accuracy, the HMM-based approach outperforms an existing state-of-the-art approach by at least 10% in most cases. Furthermore, our cross-domain investigation shows that a single HMM trained on data having varied and frequent design patterns can accurately segment interfaces from multiple domains.
Privacy-enhanced public view for social graphs
Authors: Hyoungshick Kim, Joseph Bonneau
Venue: CIKM
Year: 2009

We consider the problem of releasing a limited public view of a sensitive graph which reveals at least k edges per node. We are motivated by Facebook's public search listings, which expose user profiles to search engines along with a fixed number of each user's friends. If this public view is produced by uniform random sampling, an adversary can accurately approximate many sensitive features of the original graph, including the degree of individual nodes. We propose several schemes to produce public views which hide degree information. We demonstrate the practicality of our schemes using real data and show that it is possible to mitigate inference of degree while still providing useful public views.
Multivariate classification of urine metabolome profiles for breast cancer diagnosis
Authors: Younghoon Kim, Imhoi Koo, Byung Hwa Jung, Bong Chul Chung, Doheon Lee
Venue: CIKM
Year: 2009

Diagnosis techniques using urine are non-invasive, inexpensive, and easy to perform in clinical settings. The metabolites in urine, as the end products of cellular processes, are closely linked to phenotypes. Although research using urine metabolome has many advantages, there can also be problems, such as multiple characteristic signals mixing or averaging into undistinguishable signals. As a result, it seems that univariate methods cannot identify precise boundaries between two groups, such as cancerous and normal samples. Moreover, due to individual differences in genetic makeup and heterogeneity in cancer progression, the analysis of combinatorial information from many variables seems to be more suitable than univariate analysis. In this study, we therefore propose classification models using multivariate classification techniques and develop an analysis procedure for classification studies using metabolome data. Through this strategy, we identified five potential urinary biomarkers for breast cancer with high accuracy and also proposed potential diagnosis rules to help in clinical decision making. After further validation with independent cohorts and experimental confirmation, these marker candidates will likely lead to clinically applicable assays for earlier diagnoses of breast cancer. This multivariate classification research is the second trial in metabolome analysis after Denkert et al. and the first for urine metabolome studies.
A large-scale gene network inference system for systems biology on supercomputing resources
Authors: Younghoon Kim, Doheon Lee, Yongseong Cho, Sang Joo Lee
Venue: CIKM
Year: 2009

Motivation: Although gene expression data has been continuously accumulated and meta-analysis approaches have been developed to integrate independent expression profiles into larger datasets, the amount of information is still insufficient to infer large scale genetic networks. In addition, global optimization such as Bayesian network inference, one of the most representative techniques for genetic network inference, requires tremendous computational load far beyond the capacity of moderate workstations.Results: MONET is a Cytoscape plugin to infer genome-scale networks from gene expression profiles. It alleviates the shortage of information by incorporating pre-existing annotations. The current version of MONET utilizes thousands of parallel computational cores in the supercomputing center in KISTI, Korea, to cope with the computational requirement for large scale genetic network inference.Availability: A cytoscape plugin is available at http://cytoscape.org and a web service is at http://delsol.kaist.ac.kr/~monet/home
Opinion classification with tree kernel SVM using linguistic modality analysis
Authors: Takeshi S. Kobayakawa, Tadashi Kumano, Hideki Tanaka, Naoaki Okazaki, Jin-Dong Kim, Jun&apos, ichi Tsujii
Venue: CIKM
Year: 2009

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
Applying differential privacy to search queries in a policy based interactive framework
Authors: Palanivel A. Kodeswaran, Evelyne Viegas
Venue: CIKM
Year: 2009

Web search logs are of growing importance to researchers as they help understanding search behavior and search engine performance. However, search logs typically contain sensitive information about users and therefore considerable caution must be exercised when considering releasing the logs to the research community. Current approaches to releasing search logs focus on either protecting the privacy of users or enhancing the utility of data to researchers. In this work, we address the privacy-utility tradeoff by providing safe access to search logs, instead of releasing them. We propose a policy based safe interactive framework built on semantic policies and differential privacy to allow researchers access to search logs, while maintaining the privacy of the users. Semantic policies are used to infer the higher levels of information that can be mined from a dataset based on the fields accessed by a researcher. The accessed fields are then used to build research profile(s) that guide the amount of privacy to be enforced using differential privacy. We show the additional utility that can be obtained in our framework by two demonstrative experiments that involve access to user level information. Our results indicate that valid research can be conducted in our framework without forgoing the privacy of individuals.
OSSOBOOK: database and knowledgemanagement techniques for archaeozoology
Authors: Hans-Peter Kriegel, Peer Kröger, Henriette Obermaier, Joris Peters, Matthias Renz, Christiaan Hendrikus van der Meijden
Venue: CIKM
Year: 2009

This demo describes the OSSOBOOK database system developed for archaeozoology applications providing data storage, data retrieval, and data mining facilities. It shows a case study of integrating state-of-the-art database concepts like intermittently synchronized database system as well as concepts of information retrieval and knowledge representation like similarity search and data mining in order to provide a comprehensive system for an interesting application domain.
Utilizing inter-passage and inter-document similarities for re-ranking search results
Authors: Eyal Krikon, Oren Kurland, Michael Bendersky
Venue: CIKM
Year: 2009

We present a novel language-model-based approach to re-ranking an initially retrieved list so as to improve precision at top ranks. Our model integrates whole-document information with that induced from passages. Specifically, inter-passage, inter-document, and query-based similarities are integrated in our model. Empirical evaluation demonstrates the effectiveness of our approach.
Learning to rank from Bayesian decision inference
Authors: Jen-Wei Kuo, Pu-Jen Cheng, Hsin-Min Wang
Venue: CIKM
Year: 2009

Ranking is a key problem in many information retrieval (IR) applications, such as document retrieval and collaborative filtering. In this paper, we address the issue of learning to rank in document retrieval. Learning-based methods, such as RankNet, RankSVM, and RankBoost, try to create ranking functions automatically by using some training data. Recently, several learning to rank methods have been proposed to directly optimize the performance of IR applications in terms of various evaluation measures. They undoubtedly provide statistically significant improvements over conventional methods; however, from the viewpoint of decision-making, most of them do not minimize the Bayes risk of the IR system. In an attempt to fill this research gap, we propose a novel framework that directly optimizes the Bayes risk related to the ranking accuracy in terms of the IR evaluation measures. The results of experiments on the LETOR collections demonstrate that the framework outperforms several existing methods in most cases.
Maximal metric margin partitioning for similarity search indexes
Authors: Hisashi Kurasawa, Daiji Fukagawa, Atsuhiro Takasu, Jun Adachi
Venue: CIKM
Year: 2009

We propose a partitioning scheme for similarity search indexes that is called Maximal Metric Margin Partitioning (MMMP). MMMP divides the data on the basis of its distribution pattern, especially for the boundaries of clusters. A partitioning surface created by MMMP is likely to be at maximum distances from the two cluster boundaries. MMMP is the first similarity search index approach to focus on partitioning surfaces and data distribution patterns. We also present an indexing scheme, named the MMMP-Index, which uses MMMP and small ball partitioning. The MMMP-Index prunes many objects that are not relevant to a query, and it reduces the query execution cost. Our experimental results show that MMMP effectively indexes clustered data and reduces the search cost. For clustered vector data, the MMMP-Index reduces the computational cost to less than two thirds that of comparable schemes.
XCFS: an XML documents clustering approach using both the structure and the content
Authors: Sangeetha Kutty, Richi Nayak, Yuefeng Li
Venue: CIKM
Year: 2009

This paper introduces a clustering approach, XML Clustering using Frequent Substructures (XCFS) that considers both the structural and the content information of XML documents in clustering. XCFS uses frequent substructures in the form of a novel representation, Closed Frequent Embedded (CFE) subtrees to constrain the content in the clustering process. The empirical analysis ascertains that XCFS can effectively cluster even very large XML datasets and outperforms other existing methods.
An analysis of information diffusion in the blog world
Authors: Yong-Suk Kwon, Sang-Wook Kim, Sunju Park
Venue: CIKM
Year: 2009

In the blog world, bloggers produce information, establish relationships with other bloggers in order to exchange information, and form a blog network, an online social network. In social network theory, information diffusion is said to occur through the relationships of the social network's constituents. Contrary to the social network theory, however, when the history of information diffusion that occurs in the actual blog world is examined, a majority of information spreads between the constituents without any established relationship. Moreover the phenomenon of explosive information diffusion is also observed. Using the real-world blog data, this paper reveals that these two phenomena are related to each other and examines the causes that induce explosive information diffusion.
MRM: an adaptive framework for XML searching
Authors: Ho Lam Lau, Wilfred Ng
Venue: CIKM
Year: 2009

In order to deal with the diversified nature of XML documents as well as individual user preferences, we propose a novel Multi-Ranker Model (MRM), which is able to abstract a spectrum of important XML properties and adapt the features to different XML search needs. The model consists of a novel three-level ranking structure and a training module called Ranking Support Vector Machine in a voting Spy Na¨1ve Bayes Framework (RSSF). RSSF is effective in learning search preference and then ranks the returned results adaptively. In this demonstration, we present our prototype developed from the model, which we call it the MRM XML search engine. The MRM engine employs only a list of simple XML tagged keywords as a user query for searching XML fragments from a collection of real XML documents. The demonstration presents an indepth analyses of the effectiveness of adaptive rankers, tailored XML rankers and a spectrum of low level ranking features.
A term dependency-based approach for query terms ranking
Authors: Chia-Jung Lee, Ruey-Cheng Chen, Shao-Hang Kao, Pu-Jen Cheng
Venue: CIKM
Year: 2009

Formulating appropriate and effective queries has been regarded as a challenging issue, since a large number of candidate words or phrases could be chosen as query terms to convey users' information needs. In this paper, we propose an approach to rank a set of given query terms according their effectiveness, wherein top ranked terms will be selected as an effective query. Our ranking approach exploits and benefits from the underlying relationship between the query terms, and thereby the effective terms can be properly combined into the query. Two regression models which capture a rich set of linguistic and statistical properties are used in our approach. Experiments on NTCIR-4 ad-hoc retrieval tasks demonstrate that the proposed approach can significantly improve retrieval performance, and can be well applied to other problems such as query expansion and querying by text segments.
Tree-pattern-based duplicate code detection
Authors: Hyo-Sub Lee, Kyung-Goo Doh
Venue: CIKM
Year: 2009

This paper presents a tree-pattern-based method of automatically and accurately finding code clones in program files. Duplicate tree-patterns are first collected by anti-unification algorithm and redundancy-free exhaustive comparisons, and then finally clustered. The algorithm is designed in such a way that the same comparison is not repeated for speed, while thoroughly examining every possible pairs of tree patterns for accuracy. Our method maintains the syntax structure of code in tree-pattern clusters, which gives the flexibility of finding different types of clones while keeping the precision.
AnchorWoman: top-k structured mobile web search engine
Authors: Wookey Lee, James Jung-Hoon Lee, Young Kuk Kim, Carson Kai-Sang Leung
Venue: CIKM
Year: 2009

With advances in technology, mobile handheld devices-such as PDAs-have become very popular. In many real-life situations, users want to find structuring information using these mobile devices, which are convenient to use but have relatively limited resources. In this paper, we present a top-k structured mobile Web search engine. It uses a top-k adaptable search-tree method that utilizes hierarchical structure of hypermedia objects to effectively look for structuring information from the mobile Web model. The engine, which is implemented in the mobile environment, provides users with top-k adaptive Web search recommendations for mobile handheld devices.
Navigational path privacy protection: navigational path privacy protection
Authors: Ken C. K. Lee, Wang-Chien Lee, Hong Va Leong, Baihua Zheng
Venue: CIKM
Year: 2009

Navigational path query, one of the most popular location-based services (LBSs), determines a route from a source to a destination on a road network. However, issuing path queries to some non-trustworthy service providers may pose privacy threats to the users. For instance, given a query requesting for a path from a residential address to a psychiatrist, some adversaries may deduce "who is related to what disease". In this paper, we present an obfuscator framework that reduces the likelihood of path queries being revealed, while supporting different user privacy protection needs and retaining query evaluation efficiency. The framework consists of two major components, namely, an obfuscator and an obfuscated path query processor. The former formulates obfuscated path queries by intermixing true and fake sources and destinations and the latter facilitates efficient evaluation of the obfuscated path queries in an LBS server. The framework supports three types of obfuscated path queries, namely, independent obfuscated path query, shared obfuscated path query, and anti-collusion obfuscated path query. Our proposal strikes a balance between privacy protection strength and query processing overheads, while enhancing privacy protection against collusion attacks. Finally, we validate the proposed ideas and evaluate the performance of our framework based on an extensive set of empirical experiments.