No description available.

No description available.

Graph pattern matching is fundamental to social network analysis. Its effectiveness for identifying social communities and social positions, making recommendations and so on has been repeatedly demonstrated. However, the social network analysis raises new challenges to graph pattern matching. As real-life social graphs are typically large, it is often prohibitively expensive to conduct graph pattern matching over such large graphs, e.g., NP-complete for subgraph isomorphism, cubic time for bounded simulation, and quadratic time for simulation. These hinder the applicability of graph pattern matching on social network analysis. In response to these challenges, the thesis presents a series of effective techniques for querying large, dynamic, and distributively stored social networks. First of all, we propose a notion of query preserving graph compression, to compress large social graphs relative to a class Q of queries. We then develop both batch and incremental compression strategies for two commonly used pattern queries. Via both theoretical analysis and experimental studies, we show that (1) using compressed graphs Gr benefits graph pattern matching dramatically; and (2) the computation of Gr as well as its maintenance can be processed efficiently. Secondly, we investigate the distributed graph pattern matching problem, and explore parallel computation for graph pattern matching. We show that our techniques possess following performance guarantees: (1) each site is visited only once; (2) the total network traffic is independent of the size of G; and (3) the response time is decided by the size of largest fragment of G rather than the size of entire G. Furthermore, we show how these distributed algorithms can be implemented in the MapReduce framework. Thirdly, we study the problem of answering graph pattern matching using views since view based techniques have proven an effective technique for speeding up query evaluation. We propose a notion of pattern containment to characterise graph pattern matching using views, and introduce efficient algorithms to answer graph pattern matching using views. Moreover, we identify three problems related to graph pattern containment, and provide efficient algorithms for containment checking (approximation when the problem is intractable). Fourthly, we revise graph pattern matching by supporting a designated output node, which we treat as “query focus”. We then introduce algorithms for computing the top-k relevant matches w.r.t. the output node for both acyclic and cyclic pattern graphs, respectively, with early termination property. Furthermore, we investigate the diversified top-k matching problem, and develop an approximation algorithm with performance guarantee and a heuristic algorithm with early termination property. Finally, we introduce an expert search system, called ExpFinder, for large and dynamic social networks. ExpFinder identifies top-k experts in social networks by graph pattern matching, and copes with the sheer size of real-life social networks by integrating incremental graph pattern matching, query preserving compression and top-k matching computation. In particular, we also introduce bounded (resp. unbounded) incremental algorithms to maintain the weighted landmark vectors which are used for incremental maintenance for cached results.

Due to their binary nature, the Walsh functions have considerable advantages over the traditional sinusoidal functions used in Fourier analysis when the computations are carried out by a general purpose binary digital computer. The important properties of the Walsh functions which illustrate these advantages are examined and developed. The Walsh transform and spectrum are presented in relation to the problem of function approximation, and various computational procedures for effecting the transform are explained. The unconventional 'logical' transform is developed from the Walsh transform, and there is a discussion on the subject of interpreting the resulting spectrum. There are other functions, such as the Haar functions, which are closely related to the Walsh functions, and their advantages are indicated. The process of shape analysis is dealt with in terms of its relation to the more widely treated problem of pattern recognition. An application of shape analysis, using Walsh functions, to a study of leaf shapes is illustrated by experimental results. A completely different approach to shape analysis is taken in the chapter on Pattern Generation and Simulation of Growth Processes. Other applications of Walsh functions, particularly of the 'logical' transform, are discussed in the final chapter. Throughout, tested computer programs are used to provide examples, back up conjectures, and generally illustrate numerous points in the text.

A number of researchers have investigated the application of neural networks to visual recognition, with much of the emphasis placed on exploiting the network's ability to generalise. However, despite the benefits of such an approach it is not at all obvious how networks can be developed which are capable of recognising objects subject to changes in rotation, translation and viewpoint. In this study, we suggest that a possible solution to this problem can be found by studying aspects of visual psychology and in particular, perceptual organisation. For example, it appears that grouping together lines based upon perceptually significant features can facilitate viewpoint independent recognition. The work presented here identifies simple grouping measures based on parallelism and connectivity and shows how it is possible to train multi-layer perceptrons (MLPs) to detect and determine the perceptual significance of any group presented. In this way, it is shown how MLPs which are trained via backpropagation to perform individual grouping tasks, can be brought together into a novel, large scale network capable of determining the perceptual significance of the whole input pattern. Finally the applicability of such significance values for recognition is investigated and results indicate that both the NILP and the Kohonen Feature Map can be trained to recognise simple shapes described in terms of perceptual significances. This study has also provided an opportunity to investigate aspects of the backpropagation algorithm, particularly the ability to generalise. In this study we report the results of various generalisation tests. In applying the backpropagation algorithm to certain problems, we found that there was a deficiency in performance with the standard learning algorithm. An improvement in performance could however, be obtained when suitable modifications were made to the algorithm. The modifications and consequent results are reported here.

Pedestrian traffic monitoring is in its infancy, and the volatility of pedestrian traffic creates a need for guidance on site selection in traffic monitoring programs. A robust knowledge base surrounding pedestrian traffic patterns and the degree to which a single counting station is representative of a larger area are essential in developing an accurate program for estimating pedestrian traffic volumes. This research analysed long term hourly data from automated pedestrian counting devices on four consecutive blocks along an entertainment area corridor to determine the shifts in temporal pedestrian traffic characteristics and volumes along a corridor. Features of the built environment were identified that can aid in estimating pedestrian traffic patterns along a corridor. Results indicate daily pedestrian traffic volumes can vary significantly between consecutive city blocks, limiting the applicability of a single count location to represent a larger area. Additionally, shifts in temporal traffic patterns occur over short distances. / May 2016

No description available.

University of Macau / Faculty of Science and Technology. / Department of Computer and Information Science

Digitized by Kansas Correctional Industries

by Leung Kin Lap. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 70-72). / ACKNOWLEDGEMENTS --- p.I / ABSTRACT --- p.II / TABLE OF CONTENTS --- p.III / TABLE OF FIGURES --- p.IV / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Contributions of the thesis --- p.2 / Chapter 1.2 --- Organization of the thesis --- p.4 / Chapter Chapter 2 --- Previous Work --- p.5 / Chapter 2.1 --- An overview of 3-D interpretation --- p.5 / Chapter 2.1.1 --- Multiple-View Clues --- p.5 / Chapter 2.1.2 --- Single-View Clues --- p.6 / Chapter 2.2 --- Line Drawing Interpretation --- p.7 / Chapter 2.2.1 --- Qualitative Interpretation --- p.7 / Chapter 2.2.2 --- Quantitative Interpretation --- p.10 / Chapter 2.3 --- Previous Methods of Quantitative Interpretation by Optimization --- p.12 / Chapter 2.3.1 --- Extremum Principle for Shape from Contour --- p.12 / Chapter 2.3.2 --- MSDA Algorithm --- p.14 / Chapter 2.4 --- Comments on Previous Work on Line Drawing Interpretation --- p.17 / Chapter Chapter 3 --- An Iterative Clustering Procedure for Imperfect Line Drawings --- p.18 / Chapter 3.1 --- Shape Constraints --- p.19 / Chapter 3.2 --- Problem Formulation --- p.20 / Chapter 3.3 --- Solution Steps --- p.25 / Chapter 3.4 --- Nearest-Neighbor Clustering Algorithm --- p.37 / Chapter 3.5 --- Discussion --- p.38 / Chapter Chapter 4 --- Experimental Results --- p.40 / Chapter 4.1 --- Synthetic Line Drawings --- p.40 / Chapter 4.2 --- Real Line Drawing --- p.42 / Chapter 4.2.1 --- Recovery of real images --- p.42 / Chapter Chapter 5 --- Conclusion and Future Work --- p.65 / Appendix A --- p.67 / Chapter A. 1 --- Gradient Space Concept --- p.67 / Chapter A. 2 --- Shading of images --- p.69 / Appendix B --- p.70