1352172
Spectral Sequencing Based on Graph Distance
The construction of linear mesh layouts has found various applications, such as implicit mesh filtering and mesh streaming, where a variety of layout quality criteria, e.g., span and width, can be considered. While spectral sequencing, derived from the Fiedler vector, is one of the best-known heuristics for minimizing width, it does not perform as well as the Cuthill-Mckee (CM) scheme in terms of span. In this paper, we treat optimal mesh layout generation as a problem of preserving graph distances and propose to use the subdominant eigenvector of a kernel (affinity) matrix for sequencing. Despite the non-sparsity of the affinity operators we use, the layouts can be computed efficiently for large meshes through subsampling and eigenvector extrapolation. Our experiments show that the new sequences obtained outperform those derived from the Fiedler vector, in terms of spans, and those obtained from CM, in terms of widths and other important quality criteria. Therefore, in applications where several such quality criteria can influence algorithm performance simultaneously, e.g., mesh streaming and implicit mesh filtering, the new mesh layouts could potentially provide a better trade-off.
1875598
Segmentation of 3D meshes through spectral clustering
We formulate and apply spectral clustering to 3D mesh segmentation for the first time and report our preliminary findings. Given a set of mesh faces, an affinity matrix which encodes the likelihood of each pair of faces belonging to the same group is first constructed. Spectral methods then use selected eigenvectors of the affinity matrix or its closely related graph Laplacian to obtain data representations that can be more easily clustered. We develop an algorithm that favors segmentation along concave regions, which is inspired by human perception. Our algorithm is theoretically sound, efficient, simple to implement, andean achieve high-quality segmentation results on 3D meshes.
40972997
Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks
Topology control problems are concerned with the assignment of power values to the nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be NP-complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is developed. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.
40646883
Adaptive sampling for thresholding in document filtering and classification
Document filtering (DF) and document classification (DC) are often integrated together to classify suitable documents into suitable categories. A popular way to achieve integrated DF and DC is to associate each category with a threshold. A document d may be classified into a category c only if its degree of acceptance (DOA) with respect to c is higher than the threshold of c. Therefore, tuning a proper threshold for each category is essential. A threshold that is too high (low) may mislead the classifier to reject (accept) too many documents. Unfortunately, thresholding is often based on the classifier's DOA estimations, which cannot always be reliable, due to two common phenomena: (1) the DOA estimations made by the classifier cannot always be correct, and (2) not all documents may be classified without any controversy. Unreliable estimations are actually noises that may mislead the thresholding process. In this paper, we present an adaptive and parameter-free technique AS4T to sample reliable DOA estimations for thresholding. AS4T operates by adapting to the classifier's status, without needing to define any parameters. Experimental results show that, by helping to derive more proper thresholds, AS4T may guide various classifiers to achieve significantly better and more stable performances under different circumstances. The contributions are of practical significance for real-world integrated DF and DC.
9652055
Incremental context mining for adaptive document classification
Automatic document classification (DC) is essential for the management of information and knowledge. This paper explores two practical issues in DC: (1) each document has its context of discussion, and (2) both the content and vocabulary of the document database is intrinsically evolving. The issues call for adaptive document classification (ADC) that adapts a DC system to the evolving contextual requirement of each document category, so that input documents may be classified based on their contexts of discussion. We present an incremental context mining technique to tackle the challenges of ADC. Theoretical analyses and empirical results show that, given a text hierarchy, the mining technique is efficient in incrementally maintaining the evolving contextual requirement of each category. Based on the contextual requirements mined by the system, higher-precision DC may be achieved with better efficiency.
7031488
Algorithmic aspects of topology control problems for ad hoc networks
Topology control problems are concerned with the assignment of power values to the nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called textbf monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be bf NP -complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is obtained. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.
30610002
INQUIRY-BOUNDED MINING OF IMPRECISE DATA FOR ADAPTIVE INFORMATION MONITORING
Information monitoring (IM) is an essential activity for management and control. Generally speaking, an IM system aims to continuously check for information updates. Once an update is detected, it triggers suitable actions such as exception validation, exception handling, and user notification. Since information sources (e.g., individual persons and servers) often cannot notify the IM system of updates, the IM system needs to actively inquire about the current status of the items being monitored. However, data inquiry may be costly, and uncontrolled inquiry may even exhaust the information sources. IM should thus be conducted under an inquiry-bounded constraint (i.e., limiting the number of inquiries). Under such a constraint, an IM system should inquire the right targets at the right time by adapting to the update behavior (i.e., rough update frequency at each time period) of each information item. This requirement brings a significant challenge to the design of the IM system: mining the imprecise data that is sampled in an inquiry-bounded manner. The data is imprecise in the sense that information sources often cannot indicate when, how many, and how frequently updates really happened. We tackle the challenge by developing a scalable multiagent model in which each agent performs autonomous mining and cooperative monitoring. It significantly outperforms state-of-the-art IM techniques in capturing a higher percentage of updates in a timelier manner by conducting fewer inquiries.