Search

Sound and light show many similarities because they both propagate as waves. This means they share the same wave properties such as reflection, refraction, scattering, diffraction, and so on. The similarities between them bring a lot of opportunities for translating knowledge of one onto the other. When compared to ultrasound, and particularly in microscopy and micromanipulation, optics is a more-developed and better-understood area, partly due to the difficulty of producing complex ultrasonic beams. Hence it makes perfect sense to explore sound based on the research of optics. Differences between light and sound are mainly due to the nature variety of their mechanisms and different scale of their wavelength. Those difference makes either light or sound suitable for certain applications. This thesis will focus on the currently technology for beam shaping for acoustic and optical waves, making use of their similarities, especially for imaging and manipulation purposes. When light scattering and absorption is low, optical scattering is able to provide high resolution and suitable for imaging. A low-cost Light-Sheet Tomography imaging system is built for monitoring the growth of plant roots based on optical scattering from the roots. When optical scattering and absorption is severe it dramatically decreases spatial resolution, optical absorption can be employed to generate less-scattered acoustic signals to form high contrast images of the optical absorbing structure in a sample. A photoacoustic imaging system featuring light sheet illumination is built, along with an automatic data acquisition system. 2D images acquired with this system are reconstructed with inverse Radon transformation. The short wavelength of optical waves makes them suitable for interaction with micron-scale objects, but less suitable for macro objects because the force does not easily scale up with the size of the targets. On the other hand, ultrasonic waves have the suitable wavelength and power level for interaction with mm- or even cm- size objects. Various ultrasonic beams with vortex wavefront were generated with a 1000-element phase-control transducer array to levitate and rotate a macro acoustic absorber by transferring linear and angular momentum from the acoustic beam to the absorber. The ratio between linear and angular momentum in the beam was measured simultaneously. With the same ultrasound transducer array, the delivery of a controllable negative radiation force onto prism-shape target is demonstrated to pull the prism towards the sound source. This is the first demonstration of macroscopic and ultrasonic tractor beam. The study of ultrasound and optical beam shaping has proven that the similarities between sound and light waves can be utilized to extend our existing knowledge on them, and further provides more opportunities on wave-matter interaction applications.

The past decade has witnessed the emergence of massive graph data. Graph is an important data structure containing vertices and edges that can be used to model complex relationships among entities in real-life applications. In this thesis, we study the fundamental problem of graph pattern matching in graph analytics on massive graphs. It is also known as subgraph matching or subgraph enumeration. Specifically, given a query graph q and a data graph G, graph pattern matching is defined as finding all subgraph instances of G that are isomorphic to q. It is widely used in cheminformatics, bioinformatics, social science, and e-commerce. In addition, it is also a basic operation in graph databases and RDF engines. Although fundamentally important, it is challenging to efficiently process subgraph queries in large data graphs due to its NP-hardness. Firstly, we study the problem of distributed subgraph enumeration. We present HUGE, an efficient and scalable subgraph enumeration system in the distributed context. HUGE incorporates an optimiser to compute an advanced execution plan, and a novel architecture that supports pulling/pushing-hybrid communication. Together with a lock-free and zero-copy cache design, and a dynamic scheduling module, HUGE achieves high performance in both computation and communication with bounded memory. Secondly, we study the problem of subgraph enumeration in eternal memory. We present PatMatX, an efficient and parallel subgraph enumeration system on external memory for modern hardware. PatMatX employs the anti-cache design for buffer management. Specifically, it stores the graph in an on-disk CSR format and adopts an atomic reference counting cache to cache frequently used vertices in its buffer pool to achieve a zero-copy cache read. A task-based scheduler is designed for bounded-memory execution. We encounter a second level of parallelism by utilising SIMD (Single-Instruction-Multiple-Data) instructions in set intersections. In addition, dynamic work stealing is used for load balancing. Two optimisations are adopted to further improve its performance, including bitpacking-based data graph compressing and partial results compression. Experiments show that PatMatX outperforms the existing disk-based solution of subgraph enumeration. Thirdly, we further study the problem of subhypergraph matching on massive hypergraphs. We present HGMatch, an efficient parallel system for subhypergraph matching on a single machine. Observed that existing approach of subhypergraph matching with the match-by-vertex framework underutilise high-order information in hypergraphs to prune candidate and delay hyperedge verification, we propose a match-by-hyperedge framework in HGMatch to fully utilise the high-order information in hypergraphs. To speed up candidate generation process, HGMatch incorporates a partitioned hyperedge list structure and a light-weight inverted hyperedge index. Furthermore, we design a highly optimised parallel engine for HGMatch to handle queries in massive hypergraphs. Experimental results show that HGMatch significantly outperforms the existing match-by-vertex algorithms by 5 orders of magnitude on average when using only a single thread and achieve almost linear scalability with near perfect load balancing when the number of threads increase.