Indexing high-dimensional data for main-memory similarity search

As RAM gets cheaper and larger, in-memory processing of data becomes increasingly affordable. In this paper, we propose a novel index structure, the CSR⁺-tree, to support efficient high-dimensional similarity search in main memory. We introduce quantized bounding spheres (QBSs) that approximate bounding spheres (BSs) or data points. We analyze the respective pros and cons of both QBSs and the previously proposed quantized bounding rectangles (QBRs), and take the best of both worlds by carefully incorporating both of them into the CSR⁺-tree. We further propose a novel distance computation scheme that eliminates the need for decompressing QBSs or QBRs, which results in significant cost savings. We present an extensive experimental evaluation and analysis of the CSR⁺-tree, and compare its performance against that of other representative indexes in the literature. Our results show that the CSR⁺-tree consistently outperforms other index structures.     

pest: Fast approximate keyword search in semantic data using eigenvector-based term propagation

We present pest, a novel approach to the approximate querying of graph-structured data such as RDF that exploits the data's structure to propagate term weights between related data items. We focus on data where meaningful answers are given through the application semantics, e.g., pages in wikis, persons in social networks, or papers in a research network such as Mendeley. The pest matrix generalizes the Google Matrix used in PageRank with a term-weight dependent leap and accommodates different levels of (semantic) closeness for different relations in the data, e.g., friend vs. co-worker in a social network. Its eigenvectors represent the distribution of a term after propagation. The eigenvectors for all terms together form a (vector space) index that takes the structure of the data into account and can be used with standard document retrieval techniques. In extensive experiments including a user study on a real life wiki, we show how pest improves the quality of the ranking over a range of existing ranking approaches, yet achieves a query performance comparable to a plain vector space index.     

The Omni-family of all-purpose access methods: a simple and effective way to make similarity search more efficient

Similarity search operations require executing expensive algorithms, and although broadly useful in many new applications, they rely on specific structures not yet supported by commercial DBMS. In this paper we discuss the new Omni-technique, which allows to build a variety of dynamic Metric Access Methods based on a number of selected objects from the dataset, used as global reference objects. We call them as the Omni-family of metric access methods. This technique enables building similarity search operations on top of existing structures, significantly improving their performance, regarding the number of disk access and distance calculations. Additionally, our methods scale up well, exhibiting sub-linear behavior with growing database size.     

Overlapping B-trees: An implementation of a transaction time access method

A new variation of Overlapping B⁺-trees is presented, which provides efficient indexing of transaction time and keys in a two dimensional key-time space. Modification operations (i.e. insertions, deletions and updates) are allowed at the current version, whereas queries are allowed to any temporal version, i.e. either in the current or in past versions. Using this structure, snapshot and range-timeslice queries can be answered optimally. However, the fundamental objective of the proposed method is to deliver efficient performance in case of a general pure-key query (i.e. ‘history of a key’). The trade-off is a small increase in time cost for version operations and storage requirements.     

An efficient method for multilevel color image thresholding using cuckoo search algorithm based on minimum cross entropy

Among various thresholding methods, minimum cross entropy is implemented for its effectiveness and simplicity. Although it is efficient and gives excellent result in case of bi-level thresholding, but its evaluation becomes computationally costly when extended to perform multilevel thresholding owing to the exhaustive search performed for the optimum threshold values. Therefore, in this paper, an efficient multilevel thresholding technique based on cuckoo search algorithm is adopted to render multilevel minimum cross entropy more practical and reduce the complexity. Experiments have been conducted over different color images including natural and satellite images exhibiting low resolution, complex backgrounds and poor illumination. The feasibility and efficiency of proposed approach is investigated through an extensive comparison with multilevel minimum cross entropy based methods that are optimized using artificial bee colony, bacterial foraging optimization, differential evolution, and wind driven optimization. In addition, the proposed approach is compared with thresholding techniques depending on between-class variance (Otsu) method and Tsalli’s entropy function. Experimental results based on qualitative results and different fidelity parameters depicts that the proposed approach selects optimum threshold values more efficiently and accurately as compared to other compared techniques and produces high quality of the segmented images.     

K: A heuristic search algorithm for finding the k shortest paths

We present a directed search algorithm, called K^?, for finding the k shortest paths between a designated pair of vertices in a given directed weighted graph. K^? has two advantages compared to current k-shortest-paths algorithms. First, K^? operates on-the-fly, which means that it does not require the graph to be explicitly available and stored in main memory. Portions of the graph will be generated as needed. Second, K^? can be guided using heuristic functions. We prove the correctness of K^? and determine its asymptotic worst-case complexity when using a consistent heuristic to be the same as the state of the art, , with respect to both runtime and space, where n is the number of vertices and m is the number of edges of the graph. We present an experimental evaluation of K^? by applying it to route planning problems as well as counterexample generation for stochastic model checking. The experimental results illustrate that due to the use of heuristic, on-the-fly search K^? can use less time and memory compared to the most efficient k-shortest-paths algorithms known so far.     

A method for detecting correspondences in a sequence of modifying shapes

It is interesting in many fields to analyze motion patterns generated by time-varying shape boundaries. When dealing with such a problem a possible initial approach consists of establishing a correspondence between segments obtained by decomposing boundary lines belonging to successive frames. In this work a mathematical model of moving shape boundaries is constructed. A technique for accomplishing related decompositions of such kinds of curves residing in contiguous frames is presented. Finally an algorithm based on the relaxation and tree search methods generates a correspondence process between tokens belonging to successive frames. Examples and results are displayed and discussed.     

LAF: a new XML encoding and indexing strategy for keyword‐based XML search

As a large number of corpuses are represented, stored and published in XML format, how to find useful information from XML databases has become an increasingly important issue. Keyword search enables web users to easily access XML data without the need to learn a structured query language or to study complex data schemas. Most existing indexing strategies for XML keyword search are based upon Dewey encoding. In this paper, we proposed a new encoding method called Level Order and Father (LAF) for XML documents. With LAF encoding, we devised a new index structure, called two‐layer LAF inverted index, which can greatly decrease the space complexity compared with Dewey encoding‐based inverted index. Furthermore, with two‐layer LAF inverted index, we proposed a new keyword query algorithm called Algorithm based on Binary Search (ABS) that can quickly find all Smallest Lowest Common Ancestor. We experimentally evaluate two‐layer LAF inverted index and ABS algorithm on four real XML data sets selected from Wikipedia. The experimental results prove the advantages of our index method and querying algorithm. The space consumed by two‐layer LAF index is less than half of that consumed by Dewey inverted index. Moreover, ABS is about one to two orders of magnitude faster than the classic Stack algorithm. Concurrency and Computation: Practice and Experience, 2012.© 2012 Wiley Periodicals, Inc.     

Unveiling the hidden bride: deep annotation for mapping and migrating legacy data to the Semantic Web

The success of the Semantic Web crucially depends on the easy creation, integration, and use of semantic data. For this purpose, we consider an integration scenario that defies core assumptions of current metadata construction methods. We describe a framework of metadata creation where Web pages are generated from a database and the database owner is cooperatively participating in the Semantic Web. This leads us to the deep annotation of the database—directly by annotation of the logical database schema or indirectly by annotation of the Web presentation generated from the database contents. From this annotation, one may execute data mapping and/or migration steps, and thus prepare the data for use in the Semantic Web. We consider deep annotation as particularly valid because: (i) dynamic Web pages generated from databases outnumber static Web pages, (ii) deep annotation may be a very intuitive way to create semantic data from a database, and (iii) data from databases should remain where it can be handled most efficiently—in its databases. Interested users can then query this data directly or choose to materialize the data as RDF files.     

The Navier–Stokes-αβ equations as a platform for a spectral multigrid method to solve the Navier–Stokes equations

This paper describes a spectral multigrid method for spatially periodic homogeneous and isotropic turbulent flows. The method uses the Navier–Stokes-αβ equations to accelerate convergence toward solutions of the Navier–Stokes equations. The Navier–Stokes-αβ equations are solved on coarse grids at various levels and the Navier–Stokes equations are solved on the “nest grid”. The method uses Crank–Nicolson time-stepping for the viscous terms, explicit time-stepping for the remaining terms, and Richardson iteration to solve linear systems encountered at each time step and on each grid level. To explore the computational efficiency of the method, comparisons are made with results obtained from an analogous spectral multigrid method for the Navier–Stokes equations. These comparisons are based on computing work units and residuals for multigrid cycles. Most importantly, we examine how choosing different values of the length scales α and β entering the Navier–Stokes-αβ equations influence the efficiency and accuracy of these multigrid schemes.     

The corridor map method: a general framework for real‐time high‐quality path planning

In many virtual environment applications, paths have to be planned for characters to traverse from a start to a goal position in the virtual world while avoiding obstacles. Contemporary applications require a path planner that is fast (to ensure real‐time interaction with the environment) and flexible (to avoid local hazards such as small and dynamic obstacles). In addition, paths need to be smooth and short to ensure natural looking motions. Current path planning techniques do not obey these criteria simultaneously. For example, A* approaches generate unnatural looking paths, potential field‐based methods are too slow, and sampling‐based path planning techniques are inflexible. We propose a new technique, the Corridor Map Method (CMM), which satisfies all the criteria. In an off‐line construction phase, the CMM creates a system of collision‐free corridors for the static obstacles in an environment. In the query phase, paths can be planned inside the corridors for different types of characters while avoiding dynamic obstacles. Experiments show that high‐quality paths for single characters or groups of characters can be obtained in real‐time. Copyright © 2007 John Wiley & Sons, Ltd.     

Vibration data analysis for a commercial aircraft: Multivariable vibration data from an aircraft is analyzed using modern system identification tools. The identified linear vibrational model accurately describes the measured motion.

Using data from extensive vibrational tests of the new Saab 2000 aircraft, a combined method for vibration analysis is studied. The method is based on a realization algorithm followed by standard prediction error methods (PEM). We find that the realization algorithm gives good initial model parameter estimates that can be further improved by the use of PEM. We use the method to get insights into the vibrational eigenmodes.     

Development of a Moodle course for schoolchildren’s table tennis learning based on Competence Motivation Theory: Its effectiveness in comparison to traditional training method

Based on Competence Motivation Theory (CMT), a Moodle course for schoolchildren’s table tennis learning was developed (The URL is http://www.bssepp.com, and this course allows guest access). The effects of the course on students’ knowledge, perceived competence and interest were evaluated through quantitative methods. The sample of the study consisted of 32 primary school students, who were randomly assigned to two groups, one of which used the Moodle course (Group M, N = 16) and the other one (Group C, N = 16) didn’t, and the intervention lasted 6 weeks. The result showed that (1) students made significant learning gains and demonstrated statistically significant higher perceived competence by participating in the Moodle course, (2) there was no statistically significant mean difference in table tennis interest between the two intervention groups. These positive effects on knowledge and perceived competence suggest that Moodle can be used as a tool to supplement traditional motor learning.     

A systematic method for 3D mapping of mangrove forests based on Shuttle Radar Topography Mission elevation data, ICEsat/GLAS waveforms and field data: Application to Ciénaga Grande de Santa Marta, Colombia

Mangrove forests are found within the intertropical zone and are one of the most biodiverse and productive wetlands on Earth. We focus on the Ciénaga Grande de Santa Marta (CGSM) in Colombia, the largest coastal lagoon–delta ecosystem in the Caribbean area with an extension of 1280 km², where one of the largest mangrove rehabilitation projects in Latin America is currently underway. Extensive man-made hydrological modifications in the region caused hypersaline soil (> 90 g kg^− 1) conditions since the 1960s triggering a large dieback of mangrove wetlands (~ 247 km²). In this paper, we describe a new systematic methodology to measure mangrove height and aboveground biomass by remote sensing. The method is based on SRTM (Shuttle Radar Topography Mission) elevation data, ICEsat/GLAS waveforms (Ice, Cloud, and Land Elevation Satellite/Geoscience Laser Altimeter System) and field data. Since the locations of the ICEsat and field datasets do not coincide, they are used independently to calibrate SRTM elevation and produce a map of mangrove canopy height. We compared height estimation methods based on waveform centroids and the canopy height profile (CHP). Linear relationships between ICEsat height estimates and SRTM elevation were derived. We found the centroid of the canopy waveform contribution (CWC) to be the best height estimator. The field data was used to estimate a SRTM canopy height bias (− 1.3 m) and estimation error (rms = 1.9 m). The relationship was applied to the SRTM elevation data to produce a mangrove canopy height map. Finally, we used field data and published allometric equations to derive an empirical relationship between canopy height and biomass. This relationship was used to scale the mangrove height map and estimate aboveground biomass distribution for the entire CGSM. The mean mangrove canopy height in CGSM is 7.7 m and most of the biomass is concentrated in forests around 9 m in height. Our biomass maps will enable estimation of regeneration rates of mangrove forests under hydrological rehabilitation at large spatial scales over the next decades. They will also be used to assess how highly disturbed mangrove forests respond to increasing sea level rise under current global climate change scenarios.