Search

Abstract A Top-k retrieval algorithm returns the k best answers of a query according to a given ranking. From a theoretical point of view, the solution of this query is straightforward if we do not take into consideration execution time. However, in many practical situations, execution time is a substantial issue. In such a case, the process of getting the top k in an optimal time becomes an interesting and non-trivial task. This paper presents an algorithm to retrieve the top-k associated to an arbitrary ranking function. The idea is to decompose the ranking function as a supremum of a certain set of functions where an efficient top-k retrieval procedure can be easily applied. Besides the theoretical presentation of the algorithm, the paper provides a set of experiments to validate the approach. [ABSTRACT FROM AUTHOR]

K-nearest neighbors search (K-NNS) is a fundamental problem in many areas of machine learning and data mining. In an attempt to solve NNS problems by locality-sensitive hashing (LSH)-based algorithms and avoid the F1-trap, in this paper, we theoretically prove the necessity of maintaining close edges of each dimension, the independence of the partition location and the precision of retrieval. Based on the theories, a new method is proposed for constructing the hash function family. Then, a volume-balancing locality-sensitive hashing (VBLSH) algorithm is implemented. In this algorithm, the problem of constructing the hash function family is transformed into an optimization problem under a fixed number of hypercubes. By solving the optimization problem, different hyperplane intervals are set for each dimension to ensure that the hash functions can evenly segment the data space, where each segmented hypercube has a close volume and close side lengths. Finally, the analysis of the algorithm shows that the VBLSH algorithm has a high index coding efficiency and hash code calculation efficiency. The experimental results show that the VBLSH algorithm can simultaneously take into account the efficiency, precision and recall rate, and avoid the F1-trap; it shows excellent effectiveness on 4 datasets. [ABSTRACT FROM AUTHOR]

Abstract: Flow matrices are widely used in many disciplines, but few methods can estimate them. This paper presents a knowledge-based system as capable of estimating and updating large-size time-evolving flow matrix. The system in this paper consists of two major components with the purposes of matrix estimation and parallel optimization. The matrix estimation algorithm interprets and follows users’ query scripts, retrieves data from various sources and integrates them for the matrix estimation. The parallel optimization component is built upon a supercomputing facility to utilize its computational power to efficiently process a large amount of data and estimate a large-size complex matrix. The experimental results demonstrate its outstanding performance and the acceptable accuracy by directly and indirectly comparing the estimation matrix with the actual matrix constructed by surveys. [Copyright &y& Elsevier]

Document Information retrieval consists of finding the documents in a collection of documents that are the most relevant to a user query. Information retrieval techniques are widely-used by organizations to facilitate the search for information. However, applying traditional information retrieval techniques is time consuming for large document collections. Recently, cluster-based information retrieval approaches have been developed. Although these approaches are often much faster than traditional approaches for processing large document collections, the quality of the documents retrieved by cluster-based approaches is often less than that of traditional approaches. To address this drawback of cluster-based approaches, and improve the performance of information retrieval both in terms of runtime and quality of retrieved documents, this paper proposes a new cluster-based information retrieval approach named ICIR (Intelligent Cluster-based Information Retrieval). The proposed approach combines k-means clustering with frequent closed itemset mining to extract clusters of documents and find frequent terms in each cluster. Patterns discovered in each cluster are then used to select the most relevant document clusters to answer each user query. Four alternative heuristics are proposed to select the most relevant clusters, and two alternative heuristics for choosing documents in the selected clusters. Thus, eight versions of the proposed approach are obtained. To validate the proposed approach, extensive experiments have been carried out on well-known document collections. Results show that the designed approach outperforms traditional and cluster-based information retrieval approaches both in terms of execution time and quality of the returned documents. [ABSTRACT FROM AUTHOR]

The salient region is the most important part of an image. The salient portion in images also attracts the most attention when people search for images in large-scale datasets. However, to improve image retrieval accuracy, considering only the most salient object in an image is insufficient because the background also influences the accuracy of image retrieval. To address this issue, this paper proposes a novel concept called the extended salient region (ESR). First, the salient region of an input image is detected using a Region Contrast (RC) algorithm. Then, a polar coordinate system is constructed; the centroid of the salient region is set as the pole. Next, the regions surrounding the salient region are determined by the neighboring regions, moving in a counterclockwise direction. The resulting combination of the salient region and its surrounding regions is defined as the ESR. We extract the visual content from the ESR using the well-known Bag of Words (BoW) model based on Gabor, SIFT and HSVH features and propose a graph model of the visual content nodes to represent the input image. Then, we design a novel algorithm to perform matching between two images. We also define a new similarity measure by combining the similarities of the salient region and the surrounding regions using weights. Finally, to better evaluate the image retrieval accuracy, an improved measure called the mean label average precision (MLAP) is proposed. The results of experiments on three benchmark datasets (Corel, TU Darmstadt, and Caltech 101) demonstrate that our proposed ESR model and region-matching algorithm are highly effective at image retrieval, and can achieve more accurate query results than current state-of-the-art methods. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of retrieving a ranked list of top-N items to a target user in recommender systems. We first develop a novel preference model by distinguishing different rating patterns of users, and then apply it to existing collaborative filtering ( CF ) algorithms. Our preference model, which is inspired by a voting method, is well-suited for representing qualitative user preferences. In particular, it can be easily implemented with less than 100 lines of codes on top of existing CF algorithms such as user-based, item-based, and matrix-factorization-based algorithms. When our preference model is combined to three kinds of CF algorithms, experimental results demonstrate that the preference model can improve the accuracy of all existing CF algorithms such as ATOP and NDCG@25 by 3–24% and 6–98%, respectively. [ABSTRACT FROM AUTHOR]

Abstract: Modern information technologies and Internet services are suffering from the problem of selecting and managing a growing amount of textual information, to which access is often critical. Machine learning techniques have recently shown excellent performance and flexibility in many applications, such as artificial intelligence and pattern recognition. Question answering (QA) is a method of locating exact answer sentences from vast document collections. This paper presents a machine learning-based question-answering framework, which integrates a question classifier, simple document/passage retrievers, and the proposed context-ranking models. The question classifier is trained to categorize the answer type of the given question and instructs the context-ranking model to re-rank the passages retrieved from the initial retrievers. This method provides flexible features to learners, such as word forms, syntactic features, and semantic word features. The proposed context-ranking model, which is based on the sequential labeling of tasks, combines rich features to predict whether the input passage is relevant to the question type. We employ TREC-QA tracks and question classification benchmarks to evaluate the proposed method. The experimental results show that the question classifier achieves 85.60% accuracy without any additional semantic or syntactic taggers, and reached 88.60% after we employed the proposed term expansion techniques and a predefined related-word set. In the TREC-10 QA task, by using the gold TREC-provided relevant document set, the QA model achieves a 0.563 mean reciprocal rank (MRR) score, and a 0.342 MRR score is achieved after using the simple document and passage retrieval algorithms. [Copyright &y& Elsevier]

Abstract: This paper presents a new approach for memory-based collaborative filtering algorithms. In general, user-based rating prediction is a process in which each neighbor suggests a rating for the target item and the suggestions are combined by weighting the contribution of each neighbor. We present a new alternative that is independent of user rating scales and is based on what we call predictive probabilities. We explore how these probabilities can be used to select nearest neighbors for recommendations and integrate different types of dependence in the ratings. The neighborhood selection criterion depends on the capability of a user to predict past ratings. Our hypothesis is that if a user was good when predicting past ratings for an active user, then his predictions will also be helpful in recommending ratings for the same user in the future. [Copyright &y& Elsevier]

Abstract: Skyline queries return a set of objects, or a skyline, that are not dominated by any other objects. While providing users with an intuitive query formulation, the skyline queries may incur too many results, especially, for high dimensional data. To tackle this problem, subspace skyline queries, which deals with a subset of dimensions, have been recently studied. To identify interesting skylines, users can iteratively refine multiple relevant subspaces for skyline queries. Existing work focuses primarily on supporting efficient subspace skyline computation in centralized databases. In clear contrast, this paper aims to address subspace skyline computation in distributed environments such as the Web. Toward this goal, we make use of pre-computed subspace skylines as views in databases, called skyline views. Specifically, we propose distributed subspace skyline computation which minimizes the total access cost by leveraging the skyline views. Our experimental results validate that our proposed algorithms significantly outperform state-of-the-art algorithms in extensive synthetic datasets. [Copyright &y& Elsevier]

Abstract: In a world with vast information overload, well-optimized retrieval of relevant information has become increasingly important. Dividing large, multiple topic spanning documents into sets of coherent subdocuments facilitates the information retrieval process. This paper presents a novel technique to automatically subdivide a textual document into consistent components based on a coherence quantification function. This function is based on stem or term chains linking document entities, such as sentences or paragraphs, based on the reoccurrences of stems or terms. Applying this function on a document results in a coherence graph of the document linking its entities. Spectral graph partitioning techniques are used to divide this coherence graph into a number of subdocuments. A novel technique is introduced to obtain the most suitable number of subdocuments. These subdocuments are an aggregation of (not necessarily adjacent) entities. Performance tests are conducted in test environments based on standardized datasets to prove the algorithm’s capabilities. The relevance of these techniques for information retrieval and text mining is discussed. [Copyright &y& Elsevier]

Abstract: Effective ranking algorithms for mobile Web searches are being actively pursued. Due to the peculiar and troublesome properties of mobile contents such as scant text, few outward links, and few input keywords, conventional Web search techniques using bag-of-words ranking functions or link-based algorithms are not good enough for mobile Web searches. Our solution is to use click logs to clarify access-concentrated search results for each query and to utilize the titles and snippets to expand the queries. Many previous works regard the absolute click numbers as the degree of access concentration, but they are strongly biased such that higher-ranked search results are more easily clicked than lower-ranked ones. Therefore, it is considered that only higher-ranked search results are access-concentrated ones and that only terms extracted from them can be used to expand a query. In this paper, we introduce a new measure that is capable of estimating the degree of access concentration. This measure is used to precisely extract access concentration sites from many search results and to expand queries with terms extracted from them. We conducted an experiment using the click logs and data from an actual mobile Web search site. Results obtained show that our proposed method is a more effective way to boost the search precision than using other query expansion methods such as the top K search results or the most-often-clicked search results. [Copyright &y& Elsevier]

Abstract: Mining frequent itemsets from transactional data streams is challenging due to the nature of the exponential explosion of itemsets and the limit memory space required for mining frequent itemsets. Given a domain of I unique items, the possible number of itemsets can be up to 2 I −1. When the length of data streams approaches to a very large number N, the possibility of an itemset to be frequent becomes larger and difficult to track with limited memory. The existing studies on finding frequent items from high speed data streams are false-positive oriented. That is, they control memory consumption in the counting processes by an error parameter ϵ, and allow items with support below the specified minimum support s but above s − ϵ counted as frequent ones. However, such false-positive oriented approaches cannot be effectively applied to frequent itemsets mining for two reasons. First, false-positive items found increase the number of false-positive frequent itemsets exponentially. Second, minimization of the number of false-positive items found, by using a small ϵ, will make memory consumption large. Therefore, such approaches may make the problem computationally intractable with bounded memory consumption. In this paper, we developed algorithms that can effectively mine frequent item(set)s from high speed transactional data streams with a bound of memory consumption. Our algorithms are based on Chernoff bound in which we use a running error parameter to prune item(set)s and use a reliability parameter to control memory. While our algorithms are false-negative oriented, that is, certain frequent itemsets may not appear in the results, the number of false-negative itemsets can be controlled by a predefined parameter so that desired recall rate of frequent itemsets can be guaranteed. Our extensive experimental studies show that the proposed algorithms have high accuracy, require less memory, and consume less CPU time. They significantly outperform the existing false-positive algorithms. [Copyright &y& Elsevier]

In many information retrieval applications, it is necessary to be able to adopt a trie search for looking at the input character by character. As a fast and compact data structure for a trie, a double-array is presented. However, the insertion time is not faster than other dynamic retrieval methods because the double-array is a semi-static retrieval method that cannot treat high frequent updating. Further, the space efficiency of the double-array degrades with the number of deletions because it keeps empty elements produced by deletion. This paper presents a fast insertion algorithm by linking empty elements to find inserting positions quickly and a compression algorithm by reallocating empty elements for each deletion. From the simulation results for 100 thousands keys, it turned out that the insertion time and the space efficiency are achieved. [Copyright &y& Elsevier]

Many consumers purchase multi-functional products according to their individual preferences. Consumers are normally aware of their basic needs, but often have no idea of product types, functions, usage and terminology showing important information. This paper presents a method to translate customer needs into applicable alternative combinations for the products of customers’ desire. In this research, the theory of the analytic hierarchy process is utilized to evaluate the importance of customer needs, which are generally rated and described by qualitative expressions. A fuzzy inference model is employed to establish the relationship between customer needs and alternatives for a multi-functional product. Then a fuzzy synthetic distance method is used to perform optimal searching for possible alternative combinations in the product. Based on the above-mentioned methods and associated algorithms, a consultative interface is setup on the Internet for a case study to demonstrate effectiveness. Although a baby stroller is taken as an example in this study, this method can also be used on other products. [Copyright &y& Elsevier]

By a data conflict in a distributed system we understand a situation (or a state of the system) in which the system sites generate and store different versions of data which represent the same subject (problem solution, event scenario, etc.). Thus in purpose to solve this problem the management system should determine one proper version for the data. The final data version is called a consensus of given versions. In this paper for given conflict situation we propose to solve a consensus problem by means of a consensus function. We present elements of a consensus system, the postulates for consensus choice functions, their analysis and algorithms for consensus determining. [Copyright &y& Elsevier]