Most clustering algorithms tend to separate large scale online communities into several meaningful sub-communities by extracting cut points and cut edges. However, these algorithms are not effective on dense and concentrated graphs which do not have any meaningful cut points. Common problems with the previous algorithms are as follows. First, the size of the first cluster is too large as it may contain many incompatible users. Second, the quality and the purity of the clusters are very low. Third, only the dominant first cluster is found to be meaningful. To address these problems, we first propose a graph transformation to separate large scale online communities into two different types of meaningful subgraphs. The first subgraph is the intimacy graph and the second is the reputation graph. Then, we present the effective algorithms for discovering good sub-communities and for excluding incompatible users in these subgraphs. The experimental results show that our algorithms allow for extracting more suitable and meaningful sub-communities than the previous work in dense online networks.

Finding similar users is one of the probable applications in social media. The similarity between users can be measured in two different approaches: the semantic similarity and the similarity in terms of social relations. These two approaches can be combined with different weight factors. However, the conventional combination scheme has a critical drawback that the weight factors are fixed for every user and thus it is not optimized at those users that are using rare terms or do not have sufficient relations with other users. To address this problem, in this paper, we propose an adaptive combination scheme of tag-based similarity and link-based similarity in which the weight factors are dynamically determined for each user by evaluating each user's characteristics such as tag commonness and link strength. The experimental results with a Flickr data set show that the proposed scheme consistently outperforms the previous work by about 20%.

Searching posts effectively has become an important issue in large-scale online communities. Especially, if search users have different inclinations when they search posts, they have different kinds of posts in their minds. To address this problem, in this paper, we propose a scheme of ranking posts based on search users' inclination. User ranking score is employed to capture posts that are relevant to a specific user inclination. Specifically, we present a scheme to rank posts in terms of user expertise and popularity. Experimental results show that different user inclinations can produce quite different search results and the proposed scheme achieves about 70% accuracy.

Community Web sites on specific topics are very popular on the Web. Some active Web communities are so huge and diverse that it becomes a challenging issue to efficiently mine meaningful knowledge from the Web communities. In this paper, we develop schemes to discover and browse power users by their activities in online communities. The novelties of this work are two-fold. 1) We define new features to describe user's social activities: statistical features to summarize userspsila activities and relationship-based features to describe interactions between individual users. And, through extensive user study and experiments to compare the performances of the ranking models based on various features, it is shown that the cross reference (CR) feature plays an unique and effective role in discovering power users in post-dominant online communities. 2) Thereafter, we develop a novel interface for effective exploration of power users based on the CR rank. Two schemes are proposed to incrementally navigate a large number of candidate power users with higher CR values: threshold-based navigation and traversal-based one. Experimental results shows that the proposed CR rank can be used for effective browsing of power users: about 70% precision is maintained while retrieving all the power users, which means that we can discover all the power users with relatively small number of false alarms.

Optimal evaluation of structural relationships between XML nodes is crucial for efficient processing of XML queries. Though stack-based structural join algorithms showed improved performance over the merge-based algorithms, the algorithms still suffer potential overhead in processing XML path expressions. This is mainly because the existing structural join algorithms have been designed for returning (ancestor, descendant) node pairs even when the actual processing of the XML path queries requires the structural join operators to return either descendant nodes only or ancestor nodes only, which makes a query processor further compute for elimination of unnecessary nodes from the results. To address this problem, this paper proposes a new operator called structural semi-join and the algorithms for efficient processing XML path queries. The experiments show that the proposed algorithms improve the performance of the XML path processing by up to an order of magnitude.

A spatial distance join is a relatively new type of operation introduced for spatial and multimedia database applications. Additional requirements for ranking and stopping cardinality are often combined with the spatial distance join in online query processing or Internet search environments. These requirements pose new challenges as well as opportunities for more efficient processing of spatial distance join queries. In this paper, we first present an efficient k-distance join algorithm that uses spatial indexes such as R-trees. Bidirectional node expansion and plane-sweeping techniques are used for fast pruning of distant pairs, and the plane-sweeping is further optimized by novel strategies for selecting a sweeping axis and direction. Furthermore, we propose adaptive multistage algorithms for k-distance join and incremental distance join operations. Our performance study shows that the proposed adaptive multistage algorithms outperform previous work by up to an order of magnitude for both k-distance, join and incremental distance join queries, under various operational conditions.

A spatial distance join is a relatively new type of operation introduced for spatial and multimedia database applications. Additional requirements for ranking and stopping cardinality are often combined with the spatial distance join in on-line query processing or internet search environments. These requirements pose new challenges as well as opportunities for more efficient processing of spatial distance join queries. In this paper, we first present an efficient k-distance join algorithm that uses spatial indexes such as R-trees. Bi-directional node expansion and plane-sweeping techniques are used for fast pruning of distant pairs, and the plane-sweeping is further optimized by novel strategies for selecting a sweeping axis and direction. Furthermore, we propose adaptive multi-stage algorithms for k-distance join and incremental distance join operations. Our performance study shows that the proposed adaptive multi-stage algorithms outperform previous work by up to an order of magnitude for both k-distance join and incremental distance join queries, under various operational conditions.