Network properties of folksonomies

Social resource sharing systems like YouTube and del.icio.us have acquired a large number of users within the last few years. They provide rich resources for data analysis, information retrieval, and knowledge discovery applications. A first step towards this end is to gain better insights into content and structure of these systems. In this paper, we will analyse the main network characteristics of two of the systems. We consider their underlying data structures – socalled folksonomies – as tri-partite hypergraphs, and adapt classical network measures like characteristic path length and clustering coefficient to them. Subsequently, we introduce a network of tag co-occurrence and investigate some of its statistical properties, focusing on correlations in node connectivity and pointing out features that reflect emergent semantics within the folksonomy. We show that simple statistical indicators unambiguously spot non-social behavior such as spam.

Network properties of folksonomies

Social resource sharing systems like YouTube and del.icio.us have acquired a large number of users within the last few years. They provide rich resources for data analysis, information retrieval, and knowledge discovery applications. A first step towards this end is to gain better insights into content and structure of these systems. In this paper, we will analyse the main network characteristics of two of these systems. We consider their underlying data structures – so-called folksonomies – as tri-partite hypergraphs, and adapt classical network measures like characteristic path length and clustering coefficient to them. Subsequently, we introduce a network of tag cooccurrence and investigate some of its statistical properties, focusing on correlations in node connectivity and pointing out features that reflect emergent semantics within the folksonomy. We show that simple statistical indicators unambiguously spot non-social behavior such as spam.

Interferometrische Sensoren mit Modulation der optischen Weglänge für die Fertigungsmesstechnik

Ziel dieser Dissertation ist es, eine Klasse interferometrischer Messgeräte zu charakterisieren und weiter zu entwickeln. Die Modulation der optischen Weglänge (OPLM) im Referenzarm eines interferometrischen Messsystems ist ein anpassungsfähiger Ansatz. Sie ist zur Messung von Oberflächenprofilen mit einer Auflösung bis in den sub-nm-Bereich bei einem Messbereich von bis zu 100 Mikrometer geeignet. Wird ein statisches Messobjekt gemessen, tritt durch die Modulation im Referenzarm am Detektor ein periodisches Interferenzmuster auf. Dies ist in der unten stehenden Abbildung schematisch dargestellt. Bei einer Veränderung des Abstandes zwischen Objekt und Messgerät kann aus der Phasen- und/oder Hüllkurvenverschiebung im Interferenzmuster die Abstandsänderung abgeleitet werden.Im Rahmen der Arbeit sind zwei funktionsfähige OPLM-Messsysteme entwickelt, aufgebaut und getestet worden. Diese demonstrieren, dass der OPLM-Ansatz ein breites Spektrum an Anwendungen durch eine optische Messung abdecken kann. Allerdings zeigen sich an den Messsystemen auch die Limitierungen des OPLM-Ansatzes. Die Systeme basieren auf einer Punktmessung mittels einer fasergekoppelten Sonde sowie auf einer linienförmigen Messung durch eine Zeilenkamera. Um eine hohe laterale Auflösung zu erzielen, wird die Zeilenkamera mit einem Mikroskop kombiniert. Damit flächenhaft gemessen werden kann, ist es notwendig, Messobjekt und Sensor zueinander zu verschieben. Daher wird eine Theorie entwickelt, unter welchen Randbedingungen bewegte Objekte von einem OPLM-Messsystem aufgelöst werden können. Die Theorie wird anschließend experimentell überprüft und bestätigt. Für die Auswertung der bei der Modulation der optischen Weglänge entstehenden Interferenzen existieren bereits einige erprobte Algorithmen, welche auf ihre Eignung hin untersucht und mit selbst entwickelten Algorithmen verglichen werden. Auch wird darauf eingegangen, welches die zentralen Herausforderungen bei der Planung von OPLM-Interferometern sind und wie sich insbesondere die Wahl des Aktors für die OPLM auf das gesamte Messsystem auswirkt. Bei den beiden Messsystemen werden jeweils wichtige Komponenten wie analoge Elektronik und Aktorik sowie ihre Funktionsweise erläutert. Es wird detailliert beschrieben, wie ein OPLM-Messsystem charakterisiert und kalibriert werden muss, um möglichst zuverlässige Messwerte zu liefern. Abschließend werden die Möglichkeiten der beiden entwickelten Systeme durch Beispielmessungen demonstriert, sowie ihre Messgenauigkeit charakterisiert.

Safe Distributed Coordination of Heterogeneous Robots through Dynamic Simple Temporal Networks

Research on autonomous intelligent systems has focused on how robots can robustly carry out missions in uncertain and harsh environments with very little or no human intervention. Robotic execution languages such as RAPs, ESL, and TDL improve robustness by managing functionally redundant procedures for achieving goals. The model-based programming approach extends this by guaranteeing correctness of execution through pre-planning of non-deterministic timed threads of activities. Executing model-based programs effectively on distributed autonomous platforms requires distributing this pre-planning process. This thesis presents a distributed planner for modelbased programs whose planning and execution is distributed among agents with widely varying levels of processor power and memory resources. We make two key contributions. First, we reformulate a model-based program, which describes cooperative activities, into a hierarchical dynamic simple temporal network. This enables efficient distributed coordination of robots and supports deployment on heterogeneous robots. Second, we introduce a distributed temporal planner, called DTP, which solves hierarchical dynamic simple temporal networks with the assistance of the distributed Bellman-Ford shortest path algorithm. The implementation of DTP has been demonstrated successfully on a wide range of randomly generated examples and on a pursuer-evader challenge problem in simulation.

On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan’s functional inverse of Ackermann’s function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T₁ time on a single processor can be checked on the fly for determinacy races in O(T₁) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks. By combining SP-order with Feng and Leiserson’s serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T₁ work, and a critical-path length of T[subscript ∞]. When executed on P processors, we prove that SP-hybrid runs in O((T₁/P + PT[subscript ∞]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T₁/T[subscript ∞]). In contrast, SP-hybrid obtains linear speed-up when P = O(√T₁/T[subscript ∞]), but the work is increased by a factor of O(lg n).

An improved method for discovering link criticality in transport networks

Quantitatively assessing the importance or criticality of each link in a network is of practical value to operators, as that can help them to increase the network's resilience, provide more efficient services, or improve some other aspect of the service. Betweenness is a graph-theoretical measure of centrality that can be applied to communication networks to evaluate link importance. However, as we illustrate in this paper, the basic definition of betweenness centrality produces inaccurate estimations as it does not take into account some aspects relevant to networking, such as the heterogeneity in link capacity or the difference between node-pairs in their contribution to the total traffic. A new algorithm for discovering link centrality in transport networks is proposed in this paper. It requires only static or semi-static network and topology attributes, and yet produces estimations of good accuracy, as verified through extensive simulations. Its potential value is demonstrated by an example application. In the example, the simple shortest-path routing algorithm is improved in such a way that it outperforms other more advanced algorithms in terms of blocking ratio

All-Optical Label Stacking: Easing the Trade-offs Between Routing and Architecture Cost in All-Optical Packet Switching

All-optical label swapping (AOLS) forms a key technology towards the implementation of all-optical packet switching nodes (AOPS) for the future optical Internet. The capital expenditures of the deployment of AOLS increases with the size of the label spaces (i.e. the number of used labels), since a special optical device is needed for each recognized label on every node. Label space sizes are affected by the way in which demands are routed. For instance, while shortest-path routing leads to the usage of fewer labels but high link utilization, minimum interference routing leads to the opposite. This paper studies all-optical label stacking (AOLStack), which is an extension of the AOLS architecture. AOLStack aims at reducing label spaces while easing the compromise with link utilization. In this paper, an integer lineal program is proposed with the objective of analyzing the softening of the aforementioned trade-off due to AOLStack. Furthermore, a heuristic aiming at finding good solutions in polynomial-time is proposed as well. Simulation results show that AOLStack either a) reduces the label spaces with a low increase in the link utilization or, similarly, b) uses better the residual bandwidth to decrease the number of labels even more

Inventory control exercises

Exercises and solutions in LaTex

MA230exam01pdf

Exam questions and solutions in PDF

MA230exam99pdf

Exam questions and solutions in PDF

MA230exam99

Exam questions and solutions in LaTex

Inventory control exercises pdf

Exercises and solutions in PDF

MA230exam01

Exam questions and solutions in LaTex

Generalized Higher-Order Voronoi Diagrams on Polyhedral Surfaces

We present an algorithm for computing exact shortest paths, and consequently distances, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex polyhedral surface in which polygonal chain or polygon obstacles are allowed. We also present algorithms for computing discrete Voronoi diagrams of a set of generalized sites (points, segments, polygonal chains or polygons) on a polyhedral surface with obstacles. To obtain the discrete Voronoi diagrams our algorithms, exploiting hardware graphics capabilities, compute shortest path distances defined by the sites

Random walk radiosity with generalized absorption probabilities

The author studies random walk estimators for radiosity with generalized absorption probabilities. That is, a path will either die or survive on a patch according to an arbitrary probability. The estimators studied so far, the infinite path length estimator and finite path length one, can be considered as particular cases. Practical applications of the random walks with generalized probabilities are given. A necessary and sufficient condition for the existence of the variance is given, together with heuristics to be used in practical cases. The optimal probabilities are also found for the case when one is interested in the whole scene, and are equal to the reflectivities