Lindex: a lattice-based index for graph databases

Subgraph querying has wide applications in various fields such as cheminformatics and bioinformatics. Given a query graph, q, a subgraph-querying algorithm retrieves all graphs, D(q), which have q as a subgraph, from a graph database, D. Subgraph querying is costly because it uses subgraph isomorphism tests, which are NP-complete. Graph indices are commonly used to improve the performance of subgraph querying in graph databases. Subgraph-querying algorithms first construct a candidate answer set by filtering out a set of false answers and then verify each candidate graph using subgraph isomorphism tests. To build graph indices, various kinds of substructure (subgraph, subtree, or path) features have been proposed with the goal of maximizing the filtering rate. Each of them works with a specifically designed index structure, for example, discriminative and frequent subgraph features work with gIndex, δ-TCFG features work with FG-index, etc. We propose Lindex, a graph index, which indexes subgraphs contained in database graphs. Nodes in Lindex represent key-value pairs where the key is a subgraph in a database and the value is a list of database graphs containing the key. We propose two heuristics that are used in the construction of Lindex that allows us to determine answers to subgraph queries conducting less subgraph isomorphism tests. Consequently, Lindex improves subgraph-querying efficiency. In addition, Lindex is compatible with any choice of features. Empirically, we demonstrate that Lindex used in conjunction with subgraph indexing features proposed in previous works outperforms other specifically designed index structures. As a novel index structure, Lindex (1) is effective in filtering false graphs (2) provides fast index lookups, (3) is fast with respect to index construction and maintenance, and (4) can be constructed using any set of substructure index features. These four properties result in a fast and scalable subgraph-querying infrastructure. We substantiate the benefits of Lindex and its disk-resident variation Lindex+ theoretically and empirically.     

Automated analysis of images in documents for intelligent document search

Authors use images to present a wide variety of important information in documents. For example, two-dimensional (2-D) plots display important data in scientific publications. Often, end-users seek to extract this data and convert it into a machine-processible form so that the data can be analyzed automatically or compared with other existing data. Existing document data extraction tools are semi-automatic and require users to provide metadata and interactively extract the data. In this paper, we describe a system that extracts data from documents fully automatically, completely eliminating the need for human intervention. The system uses a supervised learning-based algorithm to classify figures in digital documents into five classes: photographs, 2-D plots, 3-D plots, diagrams, and others. Then, an integrated algorithm is used to extract numerical data from data points and lines in the 2-D plot images along with the axes and their labels, the data symbols in the figure’s legend and their associated labels. We demonstrate that the proposed system and its component algorithms are effective via an empirical evaluation. Our data extraction system has the potential to be a vital component in high volume digital libraries.     

ENROUTE: An Entropy Aware Routing Scheme for Information-Centric Networks (ICN)

With the exponential growth of end users and web data, the internet is undergoing the change of paradigm from a user-centric model to a content-centric one, popularly known as information-centric networks (ICN). Current ICN research evolves around three key-issues namely (i) content request searching, (ii) content routing, and (iii) in-network caching scheme to deliver the requested content to the end user. This would improve the user experience to obtain requested content because it lowers the download delay and provides higher throughput. Existing researches have mainly focused on on-path congestion or expected delivery time of a content to determine the optimized path towards custodian. However, it ignores the cumulative effect of the link-state parameters and the state of the cache, and consequently it leads to degrade the delay performance. In order to overcome this shortfall, we consider both the congestion of a link and the state of on-path caches to determine the best possible routes. We introduce a generic term entropy to quantify the effects of link congestion and state of on-path caches. Thereafter, we develop a novel entropy dependent algorithm namely ENROUTE for searching of content request triggered by any user, routing of this content, and caching for the delivery this requested content to the user. The entropy value of an intra-domain node indicates how many popular contents are already cached in the node, which, in turn, signifies the degree of enrichment of that node with the popular contents. On the other hand, the entropy for a link indicates how much the link is congested with the traversal of contents. In order to have reduced delay, we enhance the entropy of caches in nodes, and also use path with low entropy for downloading contents. We evaluate the performance of our proposed ENROUTE algorithm against state-of-the-art schemes for various network parameters and observe an improvement of 29–52% in delay, 12–39% in hit rate, and 4–39% in throughput.

     

A comprehensive survey of industry practice in real-time systems

Real-Time Systems - This paper presents results and observations from a survey of 120 industry practitioners in the field of real-time embedded systems. The survey provides insights into the...     

Genetic algorithms based robust frequency estimation of sinusoidal signals with stationary errors

In this paper, we consider the fundamental problem of frequency estimation of multiple sinusoidal signals with stationary errors. We propose genetic algorithm and outlier-insensitive criterion function based technique for the frequency estimation problem. In the simulation studies and real life data analysis, it is observed that the proposed genetic algorithm based robust frequency estimators are able to resolve frequencies of the sinusoidal model with high degree of accuracy. Among the proposed methods, the genetic algorithm based least squares estimator, in the no-outlier scenario, provides efficient estimates, in the sense that their mean square errors attain the corresponding Cramér-Rao lower bounds. In the presence of outliers, the proposed robust methods perform quite well and seem to have a fairly high breakdown point with respect to level of outlier contamination. The proposed methods significantly do not depend on the initial guess values required for other iterative frequency estimation methods.     

A new social and momentum component adaptive PSO algorithm for image segmentation

In this paper, we present a new variant of Particle Swarm Optimization (PSO) for image segmentation using optimal multi-level thresholding. Some objective functions which are very efficient for bi-level thresholding purpose are not suitable for multi-level thresholding due to the exponential growth of computational complexity. The present paper also proposes an iterative scheme that is practically more suitable for obtaining initial values of candidate multilevel thresholds. This self iterative scheme is proposed to find the suitable number of thresholds that should be used to segment an image. This iterative scheme is based on the well known Otsu’s method, which shows a linear growth of computational complexity. The thresholds resulting from the iterative scheme are taken as initial thresholds and the particles are created randomly around these thresholds, for the proposed PSO variant. The proposed PSO algorithm makes a new contribution in adapting ‘social’ and ‘momentum’ components of the velocity equation for particle move updates. The proposed segmentation method is employed for four benchmark images and the performances obtained outperform results obtained with well known methods, like Gaussian-smoothing method (Lim, Y. K., & Lee, S. U. (1990). On the color image segmentation algorithm based on the thresholding and the fuzzy c-means techniques. Pattern Recognition, 23, 935–952; Tsai, D. M. (1995). A fast thresholding selection procedure for multimodal and unimodal histograms. Pattern Recognition Letters, 16, 653–666), Symmetry-duality method (Yin, P. Y., & Chen, L. H. (1993). New method for multilevel thresholding using the symmetry and duality of the histogram. Journal of Electronics and Imaging, 2, 337–344), GA-based algorithm (Yin, P. -Y. (1999). A fast scheme for optimal thresholding using genetic algorithms. Signal Processing, 72, 85–95) and the basic PSO variant employing linearly decreasing inertia weight factor.     

SmartCanvas: Context‐inferred Interpretation of Sketches for Preparatory Design Studies

In early or preparatory design stages, an architect or designer sketches out rough ideas, not only about the object or structure being considered, but its relation to its spatial context. This is an iterative process, where the sketches are not only the primary means for testing and refining ideas, but also for communicating among a design team and to clients. Hence, sketching is the preferred media for artists and designers during the early stages of design, albeit with a major drawback: sketches are 2D and effects such as view perturbations or object movement are not supported, thereby inhibiting the design process. We present an interactive system that allows for the creation of a 3D abstraction of a designed space, built primarily by sketching in 2D within the context of an anchoring design or photograph. The system is progressive in the sense that the interpretations are refined as the user continues sketching. As a key technical enabler, we reformulate the sketch interpretation process as a selection optimization from a set of context‐generated canvas planes in order to retrieve a regular arrangement of planes. We demonstrate our system (available at http:/geometry.cs.ucl.ac.uk/projects/2016/smartcanvas/ ) with a wide range of sketches and design studies.     

Experimental characterization of piezoelectrically actuated micromachined silicon valveless micropump

In this paper, performance of piezoelectrically actuated pyramidal valveless micropumps is studied experimentally in detail. Valveless micropumps based on silicon and glass substrate are fabricated using MEMS technology. Two different sizes of micropumps having overall dimensions of 5 mm × 5 mm × 1 mm and 10 mm × 10 mm × 1 mm are fabricated and characterized. In the fabricated micropumps, the thickness of silicon diaphragm is <20 µm which gives the advantage of operating pump at low voltage with excellent stability and consistency. The performance of micropumps in terms of flowrate and backpressure is evaluated for a wide range of driving frequency and actuating voltages. The maximum flowrate of water in the 10-mm micropump is 355 µl/min and backpressure of 3.1 kPa at zero flowrate for an applied voltage of 80 V at frequency 1.05 kHz. The reported micropumps have low footprint, high flowrate and backpressure. Thus, these micropumps are especially suited for biological applications as these can withstand adequate amount of backpressure. Comparative study of the performance of these micropumps with those available in the literature brings out the efficacy of these micropumps.     

Zodiac: A history-based interactive video authoring system

Easy-to-use audio/video authoring tools play a crucial role in moving multimedia software from research curiosity to mainstream applications. However, research in multimedia authoring systems has rarely been documented in the literature. This paper describes the design and implementation of an interactive video authoring system called Zodiac, which employs an innovative edit history abstraction to support several unique editing features not found in existing commercial and research video editing systems. Zodiac provides users a conceptually clean and semantically powerful branching history model of edit operations to organize the authoring process, and to navigate among versions of authored documents. In addition, by analyzing the edit history, Zodiac is able to reliably detect a composed video stream's shot and scene boundaries, which facilitates interactive video browsing. Zodiac also features a video object annotation capability that allows users to associate annotations to moving objects in a video sequence. The annotations themselves could be text, image, audio, or video. Zodiac is built on top of MMFS, a file system specifically designed for interactive multimedia development environments, and implements an internal buffer manager that supports transparent lossless compression/decompression. Shot/scene detection, video object annotation, and buffer management all exploit the edit history information for performance optimization.