ALBERT

Description:    In this paper, two-stage machine learning-based noise detection scheme has been proposed for identification of salt-and- pepper impulse noise which gives excellent detection results for highly corrupted images. In the first stage, a window of size 3×3 is taken from image and some other features of this window are used as input to neural network. This scheme has distinction of having very low missed detection (MD) and false positives rates. In the second stage, decision tree-based algorithm (J48) is applied on some well-known statistical parameters to generate rules for noise detection. These noise detection methods give promising results for identification of noise from highly corrupted images. A modified version of switching median filter (directional weighted switching median filter) is proposed for noise removal. Performance of noise detector is measured using MD and false alarm FA. Filtering results are compared with state-of-the-art noise removal techniques in terms of peak signal-to-noise ratio and structural similarity index measure. Extensive experiments are performed to show that the proposed technique gives better results than state-of-the-art noise detection and filtering methods. Content Type Journal Article Category Regular Paper Pages 1-21 DOI 10.1007/s10115-012-0549-y Authors Sohail Masood, International Islamic University Islamabad, Islamabad, Pakistan Ayyaz Hussain, National University of Computer and Emerging Sciences, Islamabad, Pakistan M. Arfan Jaffar, International Islamic University Islamabad, Islamabad, Pakistan Anwar M. Mirza, King Saud University, Riyadh, Saudi Arabia Tae-Sun Choi, Gwangju Institute of Science and Technology, Gwangju, South Korea Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377

Description:    In recent years, a web phenomenon known as Volunteered Geographic Information (VGI) has produced large crowdsourced geographic data sets. OpenStreetMap (OSM), the leading VGI project, aims at building an open-content world map through user contributions. OSM semantics consists of a set of properties (called ‘tags’) describing geographic classes, whose usage is defined by project contributors on a dedicated Wiki website. Because of its simple and open semantic structure, the OSM approach often results in noisy and ambiguous data, limiting its usability for analysis in information retrieval, recommender systems and data mining. Devising a mechanism for computing the semantic similarity of the OSM geographic classes can help alleviate this semantic gap. The contribution of this paper is twofold. It consists of (1) the development of the OSM Semantic Network by means of a web crawler tailored to the OSM Wiki website; this semantic network can be used to compute semantic similarity through co-citation measures, providing a novel semantic tool for OSM and GIS communities; (2) a study of the cognitive plausibility (i.e. the ability to replicate human judgement) of co-citation algorithms when applied to the computation of semantic similarity of geographic concepts. Empirical evidence supports the usage of co-citation algorithms—SimRank showing the highest plausibility—to compute concept similarity in a crowdsourced semantic network. Content Type Journal Article Category Regular Paper Pages 1-21 DOI 10.1007/s10115-012-0571-0 Authors Andrea Ballatore, School of Computer Science and Informatics, University College Dublin, Belfield, Dublin 4, Ireland Michela Bertolotto, School of Computer Science and Informatics, University College Dublin, Belfield, Dublin 4, Ireland David C. Wilson, Department of Software and Information Systems, University of North Carolina, University City Boulevard, Charlotte, NC, USA Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377

Description:    Data uncertainty is inherent in emerging applications such as location-based services, sensor monitoring systems, and data integration. To handle a large amount of imprecise information, uncertain databases have been recently developed. In this paper, we study how to efficiently discover frequent itemsets from large uncertain databases, interpreted under the Possible World Semantics . This is technically challenging, since an uncertain database induces an exponential number of possible worlds. To tackle this problem, we propose a novel methods to capture the itemset mining process as a probability distribution function taking two models into account: the Poisson distribution and the normal distribution. These model-based approaches extract frequent itemsets with a high degree of accuracy and support large databases. We apply our techniques to improve the performance of the algorithms for (1) finding itemsets whose frequentness probabilities are larger than some threshold and (2) mining itemsets with the k highest frequentness probabilities. Our approaches support both tuple and attribute uncertainty models, which are commonly used to represent uncertain databases. Extensive evaluation on real and synthetic datasets shows that our methods are highly accurate and four orders of magnitudes faster than previous approaches. In further theoretical and experimental studies, we give an intuition which model-based approach fits best to different types of data sets. Content Type Journal Article Category Regular Paper Pages 1-37 DOI 10.1007/s10115-012-0561-2 Authors Thomas Bernecker, Department of Computer Science, Ludwig-Maximilians-Universität, Munchen, Germany Reynold Cheng, Department of Computer Science, University of Hong Kong, Pokfulam, Hong Kong David W. Cheung, Department of Computer Science, University of Hong Kong, Pokfulam, Hong Kong Hans-Peter Kriegel, Department of Computer Science, Ludwig-Maximilians-Universität, Munchen, Germany Sau Dan Lee, Department of Computer Science, University of Hong Kong, Pokfulam, Hong Kong Matthias Renz, Department of Computer Science, Ludwig-Maximilians-Universität, Munchen, Germany Florian Verhein, Department of Computer Science, Ludwig-Maximilians-Universität, Munchen, Germany Liang Wang, Department of Computer Science, University of Hong Kong, Pokfulam, Hong Kong Andreas Zuefle, Department of Computer Science, Ludwig-Maximilians-Universität, Munchen, Germany Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377

Description:    Maximizing bichromatic reverse nearest neighbor (MaxBRNN) is a variant of bichromatic reverse nearest neighbor (BRNN). The purpose of the MaxBRNN problem is to find an optimal region that maximizes the size of BRNNs. This problem has lots of real applications such as location planning and profile-based marketing. The best-known algorithm for the MaxBRNN problem is called MaxOverlap . In this paper, we study the MaxBRNN problem and propose a new approach called MaxSegment for a two-dimensional space when the L 2 -norm is used. Then, we extend our algorithm to other variations of the MaxBRNN problem such as the MaxBRNN problem with other metric spaces, and a three-dimensional space. Finally, we conducted experiments on real and synthetic datasets to compare our proposed algorithm with existing algorithms. The experimental results verify the efficiency of our proposed approach. Content Type Journal Article Category Regular Paper Pages 1-36 DOI 10.1007/s10115-012-0527-4 Authors Yubao Liu, Department of Computer Science, Sun Yat-Sen University, Guangzhou, China Raymond Chi-Wing Wong, Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Hong Kong, China Ke Wang, Department of Computer Science, Simon Fraser University, Burnaby, BC, Canada Zhijie Li, Department of Computer Science, Sun Yat-Sen University, Guangzhou, China Cheng Chen, Department of Computer Science, Sun Yat-Sen University, Guangzhou, China Zhitong Chen, Department of Computer Science, Sun Yat-Sen University, Guangzhou, China Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377

Description:    In this paper, we explore heterogenous information networks in which each vertex represents one entity and the edges reflect linkage relationships. Heterogenous information networks contain vertices of several entity types, such as papers, authors and terms, and hence can fully reflect multiple linkage relationships among different entities. Such a heterogeneous information network is similar to a mixed media graph (MMG). By representing a bibliographic dataset as an MMG, the performance obtained when searching relevant entities (e.g., papers) can be improved. Furthermore, our academic search enables multiple-entity search, where a variety of entity search results are provided, such as relevant papers, authors and conferences, via a one-time query. Explicitly, given a bibliographic dataset, we propose a Global-MMG, in which a global heterogeneous information network is built. When a user submits a query keyword, we perform a random walk with restart (RWR) to retrieve papers or other types of entity objects. To reduce the query response time, algorithm Net-MMG (standing for NetClus-based MMG) is developed. Algorithm Net-MMG first divides a heterogeneous information network into a collection of sub-networks. Afterward, the Net-MMG performs a RWR on a set of selected relevant sub-networks. We implemented our academic search and conducted extensive experiments using the ACM Digital Library. The experimental results show that by exploring heterogeneous information networks and RWR, both the Global-MMG and Net-MMG achieve better search quality compared with existing academic search services. In addition, the Net-MMG has a shorter query response time while still guaranteeing good quality in search results. Content Type Journal Article Category Regular Paper Pages 1-24 DOI 10.1007/s10115-012-0523-8 Authors Meng-Fen Chiang, National Chiao Tung University, Hsinchu, Taiwan Jiun-Jiue Liou, National Chiao Tung University, Hsinchu, Taiwan Jen-Liang Wang, National Chengchi University, Taipei, Taiwan Wen-Chih Peng, National Chiao Tung University, Hsinchu, Taiwan Man-Kwan Shan, National Chengchi University, Taipei, Taiwan Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377

Description:    We present an approach for mining frequent conjunctive in arbitrary relational databases. Our pattern class is the simple, but appealing subclass of simple conjunctive queries. Our algorithm, called Conqueror + , is capable of detecting previously unknown functional and inclusion dependencies that hold on the database relations as well as on joins of relations. These newly detected dependencies are then used to prune redundant queries. We propose an efficient database-oriented implementation of our algorithm using SQL and provide several promising experimental results. Content Type Journal Article Category Regular Paper Pages 1-30 DOI 10.1007/s10115-012-0526-5 Authors Bart Goethals, Department of Mathematics and Computer Science, University of Antwerp, 2020 Antwerp, Belgium Dominique Laurent, ETIS, CNRS, ENSEA, Université de Cergy Pontoise, 95000 Cergy-Pontoise, France Wim Le Page, Department of Mathematics and Computer Science, University of Antwerp, 2020 Antwerp, Belgium Cheikh Tidiane Dieng, ETIS, CNRS, ENSEA, Université de Cergy Pontoise, 95000 Cergy-Pontoise, France Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377

Description:    Reduced ordered binary decision diagram (ROBDD) is one of the most influential knowledge compilation languages. We generalize it by associating some implied literals with each node to propose a new language called ROBDD with implied literals (ROBDD- L ) and show that ROBDD- L can meet most of the querying requirements involved in the knowledge compilation map. Then, we discuss a kind of subsets of ROBDD- L called ROBDD- L i with precisely i implied literals (0 £ i £ ¥ ) , where ROBDD- L 0 is isomorphic to ROBDD. ROBDD- L i has uniqueness over any given linear order of variables. We mainly focus on ROBDD- L ¥ and demonstrate that: (a) it is a canonical representation on any given variable order; (b) it is the most succinct subset in ROBDD- L and thus also meets most of the querying requirements; (c) given any logical operation ROBDD supports in polytime, ROBDD- L ¥ can also support it in time polynomial in the sizes of the equivalent ROBDDs. Moreover, we propose an ROBDD- L i compilation algorithm for any i and an ROBDD- L ¥ compilation algorithm, and then we implement an ROBDD- L package called BDDjLu. Our preliminary experimental results indicate that: (a) the compilation results of ROBDD- L ¥ are significantly smaller than those of ROBDD; (b) the standard d-DNNF compiler c2d and our ROBDD- L ¥ compiler do not dominate the other, yet ROBDD- L ¥ has canonicity and supports more querying requirements and relatively efficient logical operations; and (c) the method that first compiles knowledge base into ROBDD- L ¥ and then converts ROBDD- L ¥ into ROBDD provides an efficient ROBDD compiler. Content Type Journal Article Category Regular Paper Pages 1-48 DOI 10.1007/s10115-012-0525-6 Authors Yong Lai, College of Computer Science and Technology, Jilin University, 130012  Changchun, People’s Republic of China Dayou Liu, Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, 30012  Changchun, People’s Republic of China Shengsheng Wang, College of Computer Science and Technology, Jilin University, 130012  Changchun, People’s Republic of China Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377

Description:    In this study, we introduce a new topology of radial basis function-based polynomial neural networks (RPNNs) that is based on a genetically optimized multi-layer perceptron with radial polynomial neurons (RPNs). This paper offers a comprehensive design methodology involving various mechanisms of optimization, especially fuzzy C-means (FCM) clustering and particle swarm optimization (PSO). In contrast to the typical architectures encountered in polynomial neural networks (PNNs), our main objective is to develop a topology and establish a comprehensive design strategy of RPNNs: (a) The architecture of the proposed network consists of radial polynomial neurons (RPN). These neurons are fully reflective of the structure encountered in numeric data, which are granulated with the aid of FCM clustering. RPN dwells on the concepts of a collection of radial basis function and the function-based nonlinear polynomial processing. (b) The PSO-based design procedure being applied to each layer of the RPNN leads to the selection of preferred nodes of the network whose local parameters (such as the number of input variables, a collection of the specific subset of input variables, the order of the polynomial, the number of clusters of FCM clustering, and a fuzzification coefficient of the FCM method) are properly adjusted. The performance of the RPNN is quantified through a series of experiments where we use several modeling benchmarks, namely a synthetic three-dimensional data and learning machine data (computer hardware data, abalone data, MPG data, and Boston housing data) already used in neuro-fuzzy modeling. A comparative analysis shows that the proposed RPNN exhibits higher accuracy in comparison with some previous models available in the literature. Content Type Journal Article Category Regular Paper Pages 1-31 DOI 10.1007/s10115-012-0551-4 Authors Sung-Kwun Oh, Department of Electrical Engineering, University of Suwon, Hwaseong-si, Gyeonggi-do, South Korea Ho-Sung Park, Honam Leading Industry Office, Gwangju, South Korea Wook-Dong Kim, Department of Electrical Engineering, University of Suwon, Hwaseong-si, Gyeonggi-do, South Korea Witold Pedrycz, Department of Electrical and Computer Engineering, University of Alberta, Edmonton, AB T6R 2G7, Canada Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377

Description:    The identification problem is concerned with the question whether two objects in an application refer to the same real-world entity. In this paper, the identification problem is investigated from a knowledge modelling point of view. We develop a framework of establishing knowledge-aware identity services by abstracting identity knowledge into an additional identity layer. The knowledge model in the identity service layer provides a capability for combining declarative formulae with concrete data and thus allows us to capture domain-specific identity knowledge at flexible levels of abstraction. By adding validation constraints to the identity service, we are also able to reason about inconsistency of identity knowledge. In doing so, the accuracy of identity knowledge can be improved over time, especially when utilising identity services provided by different communities in a service-oriented architecture. Our experimental study shows the effectiveness of the proposed knowledge modelling approach and the effects of domain-specific identity knowledge on data quality control. Content Type Journal Article Category Regular Paper Pages 1-23 DOI 10.1007/s10115-012-0533-6 Authors Klaus-Dieter Schewe, Software Competence Center Hagenberg, Hagenberg, Austria Qing Wang, Research School of Computer Science, The Australian National University, Acton, ACT 0200, Australia Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377

Description:    Web-based educational systems routinely collect vast quantities of data on students’ e-activity generating log files that offer researchers unique opportunities to apply data mining techniques and discover interesting information to improve the learning process. This paper proposes a friendly and intuitive tool called DRAL to detect the most relevant e-activities that a student needs to pass a course based on features extracted from logged data in an education web-based system. The method uses a more flexible representation of the available information based on multiple instance learning to prevent the appearance of a great number of missing values and is based on a multi-objective grammar guided genetic programming algorithm which obtains simple and clear classification rules which are markedly useful to identify the number, type and time of e-activities more relevant so that a student has a high probability to pass a course. To validate this approach, our proposal is compared with the most traditional proposals in multiple instance learning over the years. Experimental results demonstrate that the approach proposed successfully improves the accuracy of previous models by finding a balance between specificity and sensitivity values. Content Type Journal Article Category Regular Paper Pages 1-40 DOI 10.1007/s10115-012-0531-8 Authors Amelia Zafra, Department of Computer Science and Numerical Analysis, University of Cordoba, 14071 Cordoba, Spain Cristóbal Romero, Department of Computer Science and Numerical Analysis, University of Cordoba, 14071 Cordoba, Spain Sebastián Ventura, Department of Computer Science and Numerical Analysis, University of Cordoba, 14071 Cordoba, Spain Journal Knowledge and Information Systems Online ISSN 0219-3116 Print ISSN 0219-1377