2763612
Information Marginalization on Subgraphs
Real-world data often involves objects that exhibit multiple relationships; for example, ‘papers' and ‘authors' exhibit both paper-author interactions and paper-paper citation relationships. A typical learning problem requires one to make inferences about a subclass of objects (e.g. ‘papers'), while using the remaining objects and relations to provide relevant information. We present a simple, unified mechanism for incorporating information from multiple object types and relations when learning on a targeted subset. In this scheme, all sources of relevant information are marginalized onto the target subclass via random walks. We show that marginalized random walks can be used as a general technique for combining multiple sources of information in relational data. With this approach, we formulate new algorithms for transduction and ranking in relational data, and quantify the performance of new schemes on real world data—achieving good results in many problems.
16721854
Learning from labeled and unlabeled data on a directed graph
We propose a general framework for learning from labeled and unlabeled data on a directed graph in which the structure of the graph including the directionality of the edges is considered. The time complexity of the algorithm derived from this framework is nearly linear due to recently developed numerical techniques. In the absence of labeled instances, this framework can be utilized as a spectral clustering method for directed graphs, which generalizes the spectral clustering approach for undirected graphs. We have applied our framework to real-world web classification problems and obtained encouraging results.
806919
Using Learning to Facilitate the Evolution of Features for Recognizing Visual Concepts
This paper describes a hybrid methodology that integrates genetic algorithms (GAs) and decision tree learning in order to evolve useful subsets of discriminatory features for recognizing complex visual concepts. A GA is used to search the space of all possible subsets of a large set of candidate discrimination features. Candidate feature subsets are evaluated by using C4.5, a decision tree learning algorithm, to produce a decision tree based on the given features using a limited amount of training data. The classification performance of the resulting decision tree on unseen testing data is used as the fitness of the underlying feature subset. Experimental results are presented to show how increasing the amount of learning significantly improves feature set evolution for difficult visual recognition problems involving satellite and facial image data. In addition, we also report on the extent to which other more subtle aspects of the Baldwin effect are exhibited by the system.
8770859
K-relevance: a spectrum of relevance for data sources impacting a query
Applications ranging from grid management to sensor nets to web-based information integration and extraction can be viewed as receiving data from some number of autonomous remote data sources and then answering queries over this collected data. In such environments it is helpful to inform users which data sources are "relevant" to their query results. It is not immediately obvious what "relevant" should mean in this context, as different users will have different requirements. In this paper, rather than proposing a single definition of relevance, we propose a spectrum of definitions, which we term "k-relevance", for k ≥ 0. We give algorithms for identifying k-relevant data sources for relational queries and explore their efficiency both analytically and experimentally. Finally, we explore the impact of integrity constraints (including dependencies) and materialized views on the problem of computing and maintaining relevant data sources.
21658897
A QoS-aware transcoding proxy using on-demand data broadcasting
The high diversity in the capabilities of various mobile devices such as display capabilities and computation power makes the design of mobile information systems more challenging. A transcoding proxy is placed between a client and an information server to coordinate the mismatch between what the server provides and what the client prefers. However, most research works in transcoding proxies in mobile computing environments are under the traditional client-server architecture and do not employ the data broadcast technique which is has been deemed a promising technique to design a power conservation, high scalable and high band-width utilization. In addition, the issue of QoS provision is also not addressed. In view of this, we design in this paper a QoS-aware transcoding proxy by utilizing the on-demand broadcasting technique. We first propose a QoS-aware transcoding proxy architecture, abbreviated as QTP, and model it as a queueing network. By analyzing the queueing network, several theoretical results are derived. We then propose a version decision policy and a service admission control scheme to provide QoS in QTP. The derived results are used to guide the execution of the proposed version decision policy and service admission control scheme to achieve the given QoS requirement. To measure the performance of QTP, several experiments are conducted. Experimental results show that the proposed scheme is more scalable than traditional client-server systems. In addition, the proposed scheme is able to effectively control the system load to attain the desired QoS
37411387
Automatic generation of memory built-in self-test cores for system-on-chip
Memory testing is becoming the dominant factor in testing a system-on-chip (SoC), with the rapid growth of the size and density of embedded memories. To minimize the test effort, we present an automatic generation framework of memory built-in self-test (BIST) cores for SoC designs. The BIST generation framework is a much improved one of our previous work. Test integration of heterogeneous memory architectures and clusters of memories are focused on. The automatic test grouping and scheduling optimize the overhead in test time, performance, power consumption, etc. Furthermore, with our novel BIST architecture, the BIST cores can be accessed via an on-chip bus interface (e.g., AMBA), which eases the control of testing and diagnosis in a typical SoC scenario. With a configurable and extensible architecture, the proposed framework facilitates easy memory test integration for core providers as well as system integrators.
10932878
Thread Transparency in Information Flow Middleware
Applications that process continuous information flows are challenging to write because the application programmer must deal with flow-specific concurrency and timing requirements, necessitating the explicit management of threads, synchronization, scheduling and timing. We believe that middleware can ease this burden, but middleware that supports control-flow centric interaction models such as remote method invocation does not match the structure of these applications. Indeed, it abstracts away from the very things that the information-flow centric programmer must control