Search results

This paper aims to develop a parallel fast neighbor search method and communication strategy for particle-based methods with adaptive smoothing-length on distributed-memory computing systems.

With a multi-resolution-based hierarchical data structure, the parallel neighbor search method is developed to detect and construct ghost buffer particles, i.e. neighboring particles on remote processor nodes. To migrate ghost buffer particles among processor nodes, an undirected graph is established to characterize the sparse data communication relation and is dynamically recomposed. By the introduction of an edge coloring algorithm from graph theory, the complex sparse data exchange can be accomplished within optimized frequency. For each communication substep, only efficient nonblocking point-to-point communication is involved.

Two demonstration scenarios are considered: fluid dynamics based on smoothed-particle hydrodynamics with adaptive smoothing-length and a recently proposed physics-motivated partitioning method [Fu et al., JCP 341 (2017): 447-473]. Several new concepts are introduced to recast the partitioning method into a parallel version. A set of numerical experiments is conducted to demonstrate the performance and potential of the proposed parallel algorithms.

The proposed methods are simple to implement in large-scale parallel environment and can handle particle simulations with arbitrarily varying smoothing-lengths. The implemented smoothed-particle hydrodynamics solver has good parallel performance, suggesting the potential for other scientific applications.

This paper aims to present performance comparison between O(n²) and O(n) neighbor search algorithms, studies their effects for different particle shape complexity and computational granularity (CG) and investigates the influence on superlinear speedup of 3D discrete element method (DEM) for complex-shaped particles. In particular, it aims to answer the question: O(n²) or O(n) neighbor search algorithm, which performs better in parallel 3D DEM computational practice?

The O(n²) and O(n) neighbor search algorithms are carefully implemented in the code paraEllip3d, which is executed on the Department of Defense supercomputers across five orders of magnitude of simulation scale (2,500; 12,000; 150,000; 1 million and 10 million particles) to evaluate and compare the performance, using both strong and weak scaling measurements.

The more complex the particle shapes (from sphere to ellipsoid to poly-ellipsoid), the smaller the neighbor search fraction (NSF); and the lower is the CG, the smaller is the NSF. In both serial and parallel computing of complex-shaped 3D DEM, the O(n²) algorithm is inefficient at coarse CG; however, it executes faster than O(n) algorithm at fine CGs that are mostly used in computational practice to achieve the best performance. This means that O(n²) algorithm outperforms O(n) in parallel 3D DEM generally.

Taking for granted that O(n) outperforms O(n²) unconditionally, complex-shaped 3D DEM is a misconception commonly encountered in the computational engineering and science literature.

The paper clarifies that performance of O(n²) and O(n) neighbor search algorithms for complex-shaped 3D DEM is affected by particle shape complexity and CG. In particular, the O(n²) algorithm outperforms the O(n) algorithm in large-scale parallel 3D DEM simulations generally, even though this outperformance is counterintuitive.

This paper describes the simulation of a nearest neighbour searching algorithm for document retrieval using a pool of microprocessors. The documents in a database are organised in a multi‐dimensional binary search tree, and the algorithm identifies the nearest neighbour for a query by a backtracking search of this tree. Three techniques are described which allow parallel searching of the tree. A PASCAL‐based, general purpose simulation system is used to simulate these techniques, using a pool of Transputer‐like microprocessors with three standard document test collections. The degree of speed‐up and processor utilisation obtained is shown to be strongly dependent upon the characteristics of the documents and queries used. The results support the use of pooled microprocessor systems for searching applications in information retrieval.

Develop a new three‐dimensional discrete element code (BLOKS3D) for efficient simulation of polyhedral particles of any size. The paper describes efficient algorithms for the most important ingredients of a discrete element code.

New algorithms are presented for contact resolution and detection (including neighbor search and contact detection sections), contact point and force detection, and contact damping. In contact resolution and detection, a new neighbor search algorithm called TLS is described. Each contact is modeled with multiple contact points. A non‐linear force‐displacement relationship is suggested for contact force calculation and a dual‐criterion is employed for contact damping. The performance of the algorithm is compared to those currently available in the literature.

The algorithms are proven to significantly improve the analysis speed. A series of examples are presented to demonstrate and evaluate the performance of the proposed algorithms and the overall discrete element method (DEM) code.

Long computational times required to simulate large numbers of particles have been a major hindering factor in extensive application of DEM in many engineering applications. This paper describes an effort to enhance the available algorithms and further the engineering application of DEM.

INSTRUCT is a multi‐user, text retrieval system which was developed as an interactive teaching package for demonstrating modern information retrieval techniques, these including natural language query processing, best match searching and automatic relevance feedback based on probabilistic term weighting. INSTRUCT has recently been extended and now additionally has facilities for query expansion using both relevance and term co‐occurrence data, for cluster‐based searching and for two browsing search strategies. These retrieval mechanisms are used to search a file of 26,280 titles and abstracts from the Library and Information Science Abstracts database; both menu‐based and command‐based searching are allowed.

The major search, display, and related features of WILSONLINE are described. A more detailed description can be found in WILSONLINE: Guide and Documentation (The H. W. Wilson Co., 1984. $30.)

The purpose of this paper is to utilize document expansion techniques for improving image representation and retrieval. This paper proposes a concise framework for tag-based image retrieval (TBIR).

The proposed approach includes three core components: a strategy of selecting expansion (similar) images from the whole corpus (e.g. cluster-based or nearest neighbor-based); a technique for assessing image similarity, which is adopted for selecting expansion images (text, image, or mixed); and a model for matching the expanded image representation with the search query (merging or separate).

The results show that applying the proposed method yields significant improvements in effectiveness, and the method obtains better performance on the top of the rank and makes a great improvement on some topics with zero score in baseline. Moreover, nearest neighbor-based expansion strategy outperforms the cluster-based expansion strategy, and using image features for selecting expansion images is better than using text features in most cases, and the separate method for calculating the augmented probability P(q|R_D) is able to erase the negative influences of error images in R_D.

Despite these methods only outperform on the top of the rank instead of the entire rank list, TBIR on mobile platforms still can benefit from this approach.

Unlike former studies addressing the sparsity, vocabulary mismatch, and tag relatedness in TBIR individually, the approach proposed by this paper addresses all these issues with a single document expansion framework. It is a comprehensive investigation of document expansion techniques in TBIR.

With the ever‐increasing volume of text data via the internet, it is important that documents are classified as manageable and easy to understand categories. This paper proposes the use of binary k‐nearest neighbour (BKNN) for text categorization.

The paper describes the traditional k‐nearest neighbor (KNN) classifier, introduces BKNN and outlines experiemental results.

The experimental results indicate that BKNN requires much less CPU time than KNN, without loss of classification performance.

The paper demonstrates how BKNN can be an efficient and effective algorithm for text categorization. Proposes the use of binary k‐nearest neighbor (BKNN ) for text categorization.

The purpose of this paper is to demonstrate a real time 3D localization and mapping approach for the USAR (Urban Search and Rescue) robotic application, focusing on the performance and the accuracy of the General‐purpose computing on graphics processing units (GPGPU)‐based iterative closest point (ICP) 3D data registration implemented using modern GPGPU with FERMI architecture.

The authors put all the ICP computation into GPU, and performed the experiments with registration up to 106 data points. The main goal of the research was to provide a method for real‐time data registration performed by a mobile robot equipped with commercially available laser measurement system 3D. The main contribution of the paper is a new GPGPU based ICP implementation with regular grid decomposition. It guarantees high accuracy as equivalent CPU based ICP implementation with better performance.

The authors have shown an empirical analysis of the tuning of GPUICP parameters for obtaining much better performance (acceptable level of the variance of the computing time) with minimal lost of accuracy. Loop closing method is added and demonstrates satisfactory results of 3D localization and mapping in urban environments. This work can help in building the USAR mobile robotic applications that process 3D cloud of points in real time.

This work can help in developing real time mapping for USAR robotic applications.

The paper proposes a new method for nearest neighbor search that guarantees better performance with minimal loss of accuracy. The variance of computational time is much less than SoA.

The purpose of this paper is to model group advertising decisions, which are the collective decisions of every single advertiser within the set of advertisers who are competing in the same auction or vertical industry, and examine resulting market outcomes, via a proposed simulation framework named Experimental Platform for Search Engine Advertising (EXP-SEA) supporting experimental studies of collective behaviors in the context of search engine advertising.

The authors implement the EXP-SEA to validate the proposed simulation framework, also conduct three experimental studies on the aggregate impact of electronic word-of-mouth (eWOM), the competition level and strategic bidding behaviors. EXP-SEA supports heterogeneous participants, various auction mechanisms and also ranking and pricing algorithms.

Findings from the three experiments show that both the market profit and advertising indexes such as number of impressions and number of clicks are larger when the eWOM effect is present, meaning social media certainly has some effect on search engine advertising outcomes, the competition level has a monotonic increasing effect on the market performance, thus search engines have an incentive to encourage both the eWOM among search users and competition among advertisers, and given the market-level effect of the percentage of advertisers employing a dynamic greedy bidding strategy, there is a cut-off point for strategic bidding behaviors.

This is one of the first research works to explore collective group decisions and resulting phenomena in the complex context of search engine advertising via developing and validating a simulation framework that supports assessments of various advertising strategies and estimations of the impact of mechanisms on the search market.