Many web sites have dynamic information objects whose topics change over time. Classifying these objects automatically and promptly is a challenging and important problem for site masters. Traditional content-based and link structure based classification techniques have intrinsic limitations for this task. This paper proposes a framework to classify an object into an existing category structure by analyzing the users' traversals in the category structure. The key idea is to infer an object's topic from the predicted preferences of users when they access the object. We compare two approaches using this idea. One analyzes collective user behavior and the other each user's accesses. We present experimental results on actual data that demonstrate a much higher prediction accuracy and applicability with the latter approach. We also analyze the correlation between classification quality and various factors such as the number of users accessing the object. To our knowledge, this work is the first effort in combining object classification with user access prediction.

In a categorized information space, predicting users ’ information needs at the category level can facilitate personalization, caching and other topic-oriented services. This paper presents a two-phase model to predict the category of a user’s next access based on previous accesses. Phase 1 generates a snapshot of a user’s preferences among categories based on a temporal and frequency analysis of the user’s access history. Phase 2 uses the computed preferences to make predictions at different category granularities. Several alternatives for each phase are evaluated, using the rating behaviors of on-line raters as the form of access considered. The results show that a method based on re-access pattern and frequency analysis of a user’s whole history has the best prediction quality, even over a path-based method (Markov model) that uses the combined history of all users.

We consider the resource-constrained scheduling of loops with interiteration dependencies. A loop is modeled as a data flow graph (DFG), where edges are labeled with the number of iterations between dependencies. We design a novel and flexible technique, called rotation scheduling, for scheduling cyclic DFGs using loop pipelining. The rotation technique repeatedly transforms a schedule to a more compact schedule. We provide a theoretical basis for the operations based on retiming. We propose two heuristics to perform rotation scheduling and give experimental results showing that they have very good performance.

We consider the resource-constrained scheduling of loops with inter-iteration dependencies.A loop is modeled as a data flow graph (DFG), where edges are labeled with the number oj iterations between dependencies.We design a novel and ji'exible technique, called rotation scheduling, for scheduling cyclic DFGs using loop pipelining.The rotation technique repeatedly transforms a schedule to a more compact schedule.We provide a theoretical basis for the operations based on retiming.We propose two heuristics to perform rotation scheduling, and give experimental results showing that they have very good performance.

This paper is concerned with a game on graphs called graph searching . The object of this game is to clear all edges of a contaminated graph. Clearing is achieved by moving searchers, a kind of token, along the edges of the graph according to clearing rules. Certain search strategies cause edges that have been cleared to become contaminated again. Megiddo et al. [9] conjectured that every graph can be searched using a minimum number of searchers without this recontamination occurring, that is, without clearing any edge twice. In this paper, this conjecture is proved. This places the graph-searching problem in NP, completing the proof by Megiddo et al. that the graph-searching problem is NP-complete. Furthermore, by eliminating the need to consider recontamination, this result simplifies the analysis of searcher requirements with respect to other properties of graphs.

The problem of storing a triangular matrix so that each row and column is stored as a vector, i.e. the locations form an arithmetic progression, is discussed. Storing rows and columns as vectors can speed up access significantly. It is shown that there is no such storage method that does not waste approximately one-half of the computer memory.>

Board layout is fully or partially automated, thanks to placement and routing systems. The higher levels of the design process-component selection, architectural design, software development-are still done manually. The authors' research program at Princeton University concentrates on synthesis algorithms for high-level board design tasks. Based on case studies of system designs made both within the university and in industry, they have chosen a skeleton-based methodology for board specification and synthesis and are researching a variety of problems posed by this approach. A skeleton-based synthesis methodology assumes that a few key design decisions-major architectural choices and key component selections-are part of the board specification. The synthesis system's task is to complete the board design, based on a functional description of the board plus constraints on speed, size, power consumption, and interface behavior. A skeleton-based synthesis methodology is realistic and effective.>

We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time. Although the general problem is NP-complete, we identify polynomial time solvable special cases and derive good performance bounds for several natural approximation algorithms, assuming the existence of a central controller. We also show how these bounds can be maintained in a distributed regime.

Abstract We give a simple linear‐time algorithm for finding even‐length simple paths between two specified nodes of a given graph. We show that the same problem for directed graphs is NP‐complete.

This paper investigates the optimal tradeoff between the degree of intermediate latching and cost in special-purpose VLSI chips, using the measure AP, where A is the chip area and P is the period (the reciprocal of throughput). The results show that significant reductions in AP-product (reciprocal of throughput per unit area) can be achieved by-intermediate latching in many typical signal processing applications, for a wide range of circuit parameters.

We consider a problem of scheduling file transfers in a network so as to minimize overall finishing time, which we formalize as a problem of scheduling the edges of a weighted multigraph. Although the general problem is NP-complete, we identify polynomial time solvable special eases and derive good performance bounds for several natural approximation algorithms. The above results assume the existence of a central controller, but we also show how the approximation algorithms, along with their performance guarantees, can be adapted to a distributed regime.

In this paper we present an algorithm for a special case of wire routing. Given a rectangular circuit component on a planar surface with terminals around its boundary, the algorithm finds an optimal set of paths in the plane connecting specified pairs of terminals. The paths are restricted to lie on the outside of the component and must consist of line segments orthogonal to the sides of the component. Paths may intersect at a point but may not overlap. The criterion for optimality is the area of a rectangle with sides orthogonal to those of the component which circumscribes the component and paths. The algorithm has running time O(t3), where t is the number of terminals on the component.

We investigate the problem of finding a homeomorphic image of a “pattern” graph H in a larger input graph G. We view this problem as finding specified sets of edge disjoint or node disjoint paths in G. Our main result is a linear time algorithm to determine if there exists a simple cycle containing three given nodes in G; here H is a triangle. No polynomial time algorithm for this problem was previously known. We also discuss a variety of reductions between related versions of this problem and a number of open problems.