Search

Community detection in social networks is one of the most active problems with lots of applications. Most of the existing works on the problem have focused on detecting the community considering only the closeness between community members. In the real world, however, it is also important to consider bad relationships between members. In this paper, we propose a new variant of the community detection problem, called friendly community search. In the proposed problem, for a given graph, we aim to not only find a densely connected subgraph that contains a given set of query nodes but also minimizes the number of nodes involved in bad relationships in the subgraph. We prove that is Non-deterministic Polynomial-time hard (NP-hard), and develop two novel algorithms, called GREEDY and STEINERSWAP that return the near optimal solutions. Experimental results show that two proposed algorithms outperform the algorithm adapted from an existing algorithm for the optimal quasi-clique problem. [ABSTRACT FROM AUTHOR]

This article studies I/O-efficient algorithms for the triangle listing problem and the triangle counting problem, whose solutions are basic operators in dealing with many other graph problems. In the former problem, given an undirected graph G, the objective is to find all the cliques involving 3 vertices in G. In the latter problem, the objective is to report just the number of such cliques without having to enumerate them. Both problems have been well studied in internal memory, but still remain as difficult challenges when G does not fit in memory, thus making it crucial to minimize the number of disk I/Os performed. Although previous research has attempted to tackle these challenges, the state-of-the-art solutions rely on a set of crippling assumptions to guarantee good performance. Motivated by this, we develop a new algorithm that is provably I/O and CPU efficient at the same time, without making any assumption on the input G at all. The algorithm uses ideas drastically different from all the previous approaches, and outperforms the existing competitors by a factor of over an order of magnitude in our extensive experimentation. [ABSTRACT FROM AUTHOR]

Modeling and simulation (M&S) are widely used for design, analysis, and optimization of complex systems and natural phenomena in various areas such as the defense industry and the weather system. In many cases, the environment is a key part of complex systems and natural phenomena. It includes physical aspects of the real world which provide the context for a specific simulation. Recently, several simulation systems are integrated to work together when they have needs for exchanging information. Interoperability of heterogeneous simulations depends heavily on sharing complex environmental data in a consistent and complete manner. SEDRIS (Synthetic Environmental Data Representation and Interchange Specification) is an ISO standard for representation and interchange of environmental data and widely adopted in M&S area. As the size of the simulation increases, the size of the environmental data which should be exchanged between simulations increases. Therefore, an efficient management of the environmental data is very important. In this paper, the authors propose storing and retrieval methods of SEDRIS transmittals using a relational database system in order to be able to retrieve data efficiently in the environmental data server cooperating with many heterogeneous distributed simulations. By analyzing the structure and the content of SEDRIS transmittals, relational database schemas are designed. To reduce query processing time of SEDRIS transmittals, direct storing and retrieval methods which do not require the type conversion of SEDRIS transmittals are proposed. Experimental analyses are conducted to show the efficiency of the proposed approach. The results confirm that the proposed approach greatly reduces the storing time and retrieval time compared to comparison approaches. [ABSTRACT FROM AUTHOR]

This article studies the MaxRS problem in spatial databases. Given a set O of weighted points and a rectangle r of a given size, the goal of the MaxRS problem is to find a location of r such that the sum of the weights of all the points covered by r is maximized. This problem is useful in many location-based services such as finding the best place for a new franchise store with a limited delivery range and finding the hotspot with the largest number of nearby attractions for a tourist with a limited reachable range. However, the problem has been studied mainly in the theoretical perspective, particularly in computational geometry. The existing algorithms from the computational geometry community are in-memory algorithms that do not guarantee the scalability. In this article, we propose a scalable external-memory algorithm (ExactMaxRS) for the MaxRS problem that is optimal in terms of the I/O complexity. In addition, we propose an approximation algorithm (ApproxMaxCRS) for the MaxCRS problem that is a circle version of the MaxRS problem. We prove the correctness and optimality of the ExactMaxRS algorithm along with the approximation bound of the ApproxMaxCRS algorithm. Furthermore, motivated by the fact that all the existing solutions simply assume that there is no tied area for the best location, we extend the MaxRS problem to a more fundamental problem, namely AllMaxRS, so that all the locations with the same best score can be retrieved. We first prove that the AllMaxRS problem cannot be trivially solved by applying the techniques for the MaxRS problem. Then we propose an outputsensitive external-memory algorithm (TwoPhaseMaxRS) that gives the exact solution for the AllMaxRS problem through two phases. Also, we prove both the soundness and completeness of the result returned from TwoPhaseMaxRS. From extensive experimental results, we show that ExactMaxRS and ApproxMaxCRS are several orders of magnitude faster than methods adapted from existing algorithms, the approximation bound in practice is much better than the theoretical bound of ApproxMaxCRS, and TwoPhaseMaxRS is not only much faster but also more robust than the straightforward extension of ExactMaxRS. [ABSTRACT FROM AUTHOR]

Although there have been many compression schemes for reducing data effectively, most schemes do not consider the reordering of data. In the case of unordered data, if the users change the data order in a given data set, the compression ratio may be improved compared to the original compression before reordering data. However, in the case of ordered data, the users need a mapping table that maps the original position to the changed position in order to recover the original order. Therefore, reordering ordered data may be disadvantageous in terms of space. In this paper, the authors consider two compression schemes, run-length encoding and bucketing scheme as bases for showing the impact of data reordering in compression schemes. Also, the authors propose various optimization techniques related to data reordering. Finally, the authors show that the compression schemes with data reordering are better than the original compression schemes in terms of the compression ratio. [ABSTRACT FROM AUTHOR]

Recently, databases have been used to store multimedia data such as images, maps, video clips, and music clips. In order to search them, they should be represented by various features, which are composed of high-dimensional vectors. As a result, the dimensionality of data is increased considerably, which causes 'the curse of dimensionality'. The increase of data dimensionality causes poor performance of index structures. To overcome the problem, the research on the dimensionality reduction has been conducted. However, some reduction methods do not guarantee no false dismissal, while others incur high computational cost. This paper proposes dimensionality reduction techniques that guarantee no false dismissal while providing efficiency considerable by approximating distances with a few values. To provide the no false dismissal property, approximated distances should always be smaller than original distances. The Cauchy-Schwarz inequality and two trigonometrical equations are used as well as the dimension partitioning technique is applied to approximate distances in such a way to reduce the difference between the approximated distance and the original distance. As a result, the proposed techniques reduce the candidate set of a query result for efficient query processing. [ABSTRACT FROM AUTHOR]

Contextual advertising is an important part of today’s Web. It provides benefits to all parties: Web site owners and an advertising platform share the revenue, advertisers receive new customers, and Web site visitors get useful reference links. The relevance of selected ads for a Web page is essential for the whole system to work. Problems such as homonymy and polysemy, low intersection of keywords and context mismatch can lead to the selection of irrelevant ads. Therefore, a simple keyword matching technique gives a poor accuracy. In this paper, we propose a method for improving the relevance of contextual ads. We propose a novel “Wikipedia matching” technique that uses Wikipedia articles as “reference points” for ads selection. We show how to combine our new method with existing solutions in order to increase the overall performance. An experimental evaluation based on a set of real ads and a set of pages from news Web sites is conducted. Test results show that our proposed method performs better than existing matching strategies and using the Wikipedia matching in combination with existing approaches provides up to 50% lift in the average precision. TREC standard measure bpref-10 also confirms the positive effect of using Wikipedia matching for the effective ads selection. [ABSTRACT FROM AUTHOR]

A mobile asset with a sensor node in a mobile asset tracking system moves around a monitoring area, leaves it, and then returns to the region repeatedly. The system monitors the in/out status of the mobile asset. Due to the continuous movement of the mobile asset, the system may generate an error for the in/out status of the mobile asset. When the mobile asset is inside the region, the system might determine that it is outside, or vice versa. In this paper, we propose a method to detect and correct the incorrect in/out status of the mobile asset. To solve this problem, our approach uses data about the connection state transition and the battery lifetime of the mobile node attached to the mobile asset. The connection state transition is used to classify the mobile node as normal or abnormal. The battery lifetime is used to predict a valid working period for the mobile node. We evaluate our method using real data generated by a medical asset tracking system. The experimental results show that our method, by using the estimated battery life time or by using the invalid connection state, can detect and correct most cases of incorrect in/out statuses generated by the conventional approach. [ABSTRACT FROM AUTHOR]

The article explores the proposed recommender system from expert groups that are formed to recommend domain-specific documents for general users. The groups evaluate web documents to propose the system for general users and their authority and make-up are adjusted through user feedback. It is found that the proposed system is efficient if there is a major support from experts and general users and it is especially effective if there is a limited amount of evaluation data from the users. The expert groups are also considered effective for recommender systems.

Abstract  Relevance feedback is commonly incorporated into content-based image retrieval systems with the objective of improving retrieval accuracy via user feedback. One effective method for improving retrieval performance is to perform feature re-weighting based on the obtained feedback. Previous approaches to feature re-weighting via relevance feedback assume the feature data for images can be represented in fixed-length vectors. However, many approaches are invalidated with the recent development of features that cannot be represented in fixed-length vectors. In addition, previous approaches use only the information from the set of images returned in the latest query result for feature re-weighting. In this paper, we propose a feature re-weighting approach that places no restriction on the representation of feature data and utilizes the aggregate set of images returned over the iterations of retrieval to obtain feature re-weighting information. The approach analyzes the feature distances calculated between the query image and the resulting set of images to approximate the feature distances for the entire set of images in the database. Two-sided confidence intervals are used with the distances to obtain the information for feature re-weighting. There is no restriction on how the distances are calculated for each feature. This provides freedom for how the feature representations are structured. The experimental results show the effectiveness of the proposed approach and in comparisons with other work, it is shown that our approach outperforms previous work. [ABSTRACT FROM AUTHOR]

Like HTML, many XML documents are resident on native file systems. Since XML data is irregular and verbose, the disk space and the network bandwidth are wasted. To overcome the verbosity problem, research on compressors for XML data has been conducted. Some XML compressors do not support querying compressed data, while other XML compressors which support querying compressed data blindly encode tags and data values using predefined encoding methods. Existing XML compressors do not provide the facility for updates on compressed XML data. In this article, we propose XPRESS, an XML compressor which supports direct updates and efficient evaluations of queries on compressed XML data. XPRESS adopts a novel encoding method called reverse arithmetic encoding, which encodes label paths of XML data and applies diverse encoding methods depending on the types of data values. Experimental results with real-life data sets show that XPRESS achieves significant improvements on query performance for compressed XML data and reasonable compression ratios. On average, the query performance of XPRESS is 2.13 times better than that of an existing XML compressor, and the compression ratio of XPRESS is about 71%. Additionally, we demonstrate the efficiency of the updates performed directly on compressed XML data. [ABSTRACT FROM AUTHOR]

In recent years, spatio-temporal databases have been studied intensively. This paper proposes how to process k closest pair queries in spatio-temporal databases for the first time. A spatio-temporal k closest pair query continuously searches the k closest pairs between a set of spatial objects and a set of moving objects for a specified time interval of the query. To maintain the order of the kclosest pairs, we use a time function that can represent the change in distance between a spatial object and a moving object as time passes. For efficient processing of k closest pair queries, we present an event-based structure, instead of a simple split list structure to avoid unnecessary computations, along with a distance bound used to prune unnecessary node accesses. Our event-based method is 9 to 43 times faster, compared to a method using a simple split list structure. Also, our event-based structure can be applied to process spatio-temporal k nearest neighbor queries. In various experiments, our event-based approach is 11 to 46 times faster than an existing approach for processing spatio-temporal k nearest neighbor queries. [ABSTRACT FROM AUTHOR]

We propose a new dynamic index structure called the GC-tree (or the grid cell tree) for efficient similarity search in image databases. The GC-tree is based on a special subspace partitioning strategy which is optimized for a clustered high-dimensional image dataset. The basic ideas are threefold: 1) we adaptively partition the data space based on a density function that identifies dense and sparse regions in a data space; 2) we concentrate the partition on the dense regions, and the objects in the sparse regions of a certain partition level are treated as if they lie within a single region; and 3) we dynamically construct an index structure that corresponds to the space partition hierarchy. The resultant index structure adapts well to the strongly clustered distribution of high-dimensional image datasets. To demonstrate the practical effectiveness of the GC-tree, we experimentally compared the GC-tree with the IQ-tree, LPC-file, VA-file, and linear scan. The result of our experiments shows that the GC-tree outperforms all other methods. [ABSTRACT FROM PUBLISHER]

Deals with the interoperability of heterogeneous information management systems. Elements of the integrated knowledge-object-oriented data model; Interface between the object-oriented database and the relational database.

Discusses the Hilbert Grid tree, a data structure for organizing multidimensional data which are typically points in some domain space. Performance improvement through suppression of node splitting and reduction of directory coverage; Performance experiments and comparison with buddy tree; Development of an adaptation to the variation of the dimensionality of the domain space.

Outlines the approaches to various aspects of heterogeneous distributed data management. Characteristics and architectures of seven heterogeneous distributed database systems developed for production use; Status of the systems targeted for production environments as opposed to research prototypes.