Search

Your search keyword '"Radix sort"' showing total 327 results
Start Over Descriptor "Radix sort"
327 results on '"Radix sort"'

1. ECG arrhythmia classification based on the fast ant colony clustering algorithm with improved spatiotemporal feature perception ability

Author

Shuguang Qin, Linyue Liu, Xinhong Wang, Ning Dong, Ning Li, and Qiangsun Zheng

Subjects
ECG arrhythmia classification, The ant colony clustering algorithm, Dynamic time warping, LSTM, Dynamic pheromone volatility coefficient, Radix sort, Science (General), Q1-390, Social sciences (General), H1-99
Abstract

Electrocardiograph (ECG) is one of the most critical physiological signals used for arrhythmia diagnosis. In recent years, ECG arrhythmia classification devices consisting of multi-module sensors, clustering algorithms and neural networks play an important role in monitoring and diagnosing cardiovascular diseases. However, the commonly used ECG arrhythmia classification methods are still facing some problems such as the complex model structure and long running time. To address the above problems, this paper proposes an ECG arrhythmia classification method based on the fast ant colony clustering algorithm with improved spatiotemporal feature perception ability (SFP-FACC), which uses LSTM to fit the cluster centers and avoids the time consumption of updating the cluster centers during the classification process. The spatiotemporal feature perception ability of this model with the dynamic time warping (DTW) algorithm is improved. The classification is achieved by applying the combination of Euclidean distance and DTW. The convergence speed of the model is improved by using dynamic pheromone volatility coefficient; and finally the optimal solution of the model is determined by using radix sort. Based on the MIT-BIH arrhythmia dataset, the overall accuracy of the proposed classification method in this paper achieves 99.04 %, and even the accuracy of certain types of classification achieves 100 %, and the running time is about 3.5 times faster than that of the basic models. The experiments show that the method proposed in this paper has certain advantages.

Published
2024
Full Text
View/download PDF

2. A Parallel Implementation of FastBit Radix Sort Using MPI and CUDA

Author

Raghunandan, Aishwarya, B., Ashwath Rao, B., Aithal, Prakash K., Kini, Gopalakrishna N., Angrisani, Leopoldo, Series Editor, Arteaga, Marco, Series Editor, Panigrahi, Bijaya Ketan, Series Editor, Chakraborty, Samarjit, Series Editor, Chen, Jiming, Series Editor, Chen, Shanben, Series Editor, Chen, Tan Kay, Series Editor, Dillmann, Rüdiger, Series Editor, Duan, Haibin, Series Editor, Ferrari, Gianluigi, Series Editor, Ferre, Manuel, Series Editor, Hirche, Sandra, Series Editor, Jabbari, Faryar, Series Editor, Jia, Limin, Series Editor, Kacprzyk, Janusz, Series Editor, Khamis, Alaa, Series Editor, Kroeger, Torsten, Series Editor, Li, Yong, Series Editor, Liang, Qilian, Series Editor, Martín, Ferran, Series Editor, Ming, Tan Cher, Series Editor, Minker, Wolfgang, Series Editor, Misra, Pradeep, Series Editor, Möller, Sebastian, Series Editor, Mukhopadhyay, Subhas, Series Editor, Ning, Cun-Zheng, Series Editor, Nishida, Toyoaki, Series Editor, Pascucci, Federica, Series Editor, Qin, Yong, Series Editor, Seng, Gan Woon, Series Editor, Speidel, Joachim, Series Editor, Veiga, Germano, Series Editor, Wu, Haitao, Series Editor, Zamboni, Walter, Series Editor, Zhang, Junjie James, Series Editor, Mallick, Pradeep Kumar, editor, Bhoi, Akash Kumar, editor, González-Briones, Alfonso, editor, and Pattnaik, Prasant Kumar, editor

Published
2022
Full Text
View/download PDF

3. The Curious Case of Modified Merge Sort

Author

Garg, Harsh Sagar, Jain, Vanita, Chaudhary, Gopal, Kacprzyk, Janusz, Series Editor, Pal, Nikhil R., Advisory Editor, Bello Perez, Rafael, Advisory Editor, Corchado, Emilio S., Advisory Editor, Hagras, Hani, Advisory Editor, Kóczy, László T., Advisory Editor, Kreinovich, Vladik, Advisory Editor, Lin, Chin-Teng, Advisory Editor, Lu, Jie, Advisory Editor, Melin, Patricia, Advisory Editor, Nedjah, Nadia, Advisory Editor, Nguyen, Ngoc Thanh, Advisory Editor, Wang, Jun, Advisory Editor, Bansal, Poonam, editor, Tushir, Meena, editor, Balas, Valentina Emilia, editor, and Srivastava, Rajeev, editor

Published
2021
Full Text
View/download PDF

4. ECG arrhythmia classification based on the fast ant colony clustering algorithm with improved spatiotemporal feature perception ability.

Author

Qin S, Liu L, Wang X, Dong N, Li N, and Zheng Q

Abstract

Electrocardiograph (ECG) is one of the most critical physiological signals used for arrhythmia diagnosis. In recent years, ECG arrhythmia classification devices consisting of multi-module sensors, clustering algorithms and neural networks play an important role in monitoring and diagnosing cardiovascular diseases. However, the commonly used ECG arrhythmia classification methods are still facing some problems such as the complex model structure and long running time. To address the above problems, this paper proposes an ECG arrhythmia classification method based on the fast ant colony clustering algorithm with improved spatiotemporal feature perception ability (SFP-FACC), which uses LSTM to fit the cluster centers and avoids the time consumption of updating the cluster centers during the classification process. The spatiotemporal feature perception ability of this model with the dynamic time warping (DTW) algorithm is improved. The classification is achieved by applying the combination of Euclidean distance and DTW. The convergence speed of the model is improved by using dynamic pheromone volatility coefficient; and finally the optimal solution of the model is determined by using radix sort. Based on the MIT-BIH arrhythmia dataset, the overall accuracy of the proposed classification method in this paper achieves 99.04 %, and even the accuracy of certain types of classification achieves 100 %, and the running time is about 3.5 times faster than that of the basic models. The experiments show that the method proposed in this paper has certain advantages., Competing Interests: The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper., (© 2024 The Authors.)

Published
2024
Full Text
View/download PDF

6. A novel quantum anonymous ranking protocol.

Author

Li, Yue-Ran, Jiang, Dong-Huan, and Liang, Xiang-Qian

Abstract

A novel index distribution protocol based on single-particle state is proposed in this paper. Compared with the existing index distribution scheme, this protocol is not limited by the dimension of the quantum system. Based on the proposed index distribution protocol, we also propose a new quantum anonymous ranking protocol. This protocol can complete multi-user and multi-data anonymous ranking tasks in low-dimensional quantum systems. Security analysis shows that eavesdroppers cannot secretly obtain user's private information without being discovered. In addition, we analyze and compare the protocol of this article with the existing anonymous ranking protocols. For different practical conditions, we give the general criteria of how to choose an appropriate anonymous ranking protocol. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

7. Novel algorithms for LDD motif search

Author

Peng Xiao, Martin Schiller, and Sanguthevar Rajasekaran

Subjects
Motif search, Radix sort, Neighborhood tree, Biotechnology, TP248.13-248.65, Genetics, QH426-470
Abstract

Abstract Background Motifs are crucial patterns that have numerous applications including the identification of transcription factors and their binding sites, composite regulatory patterns, similarity between families of proteins, etc. Several motif models have been proposed in the literature. The (l,d)-motif model is one of these that has been studied widely. However, this model will sometimes report too many spurious motifs than expected. We interpret a motif as a biologically significant entity that is evolutionarily preserved within some distance. It may be highly improbable that the motif undergoes the same number of changes in each of the species. To address this issue, in this paper, we introduce a new model which is more general than (l,d)-motif model. This model is called (l,d 1,d 2)-motif model (LDDMS) and is NP-hard as well. We present three elegant as well as efficient algorithms to solve the LDDMS problem, i.e., LDDMS1, LDDMS2 and LDDMS3. They are all exact algorithms. Results We did both theoretical analyses and empirical tests on these algorithms. Theoretical analyses demonstrate that our algorithms have less computational cost than the pattern driven approach. Empirical results on both simulated datasets and real datasets show that each of the three algorithms has some advantages on some (l,d 1,d 2) instances. Conclusions We proposed LDDMS model which is more practically relevant. We also proposed three exact efficient algorithms to solve the problem. Besides, our algorithms can be nicely parallelized. We believe that the idea in this new model can also be extended to other motif search problems such as Edit-distance-based Motif Search (EMS) and Simple Motif Search (SMS).

Published
2019
Full Text
View/download PDF

8. Sorting Data on Ultra-Large Scale with RADULS : New Incarnation of Radix Sort

Author

Kokot, Marek, Deorowicz, Sebastian, Debudaj-Grabysz, Agnieszka, Diniz Junqueira Barbosa, Simone, Series editor, Chen, Phoebe, Series editor, Du, Xiaoyong, Series editor, Filipe, Joaquim, Series editor, Kara, Orhun, Series editor, Kotenko, Igor, Series editor, Liu, Ting, Series editor, Sivalingam, Krishna M., Series editor, Washio, Takashi, Series editor, Kozielski, Stanisław, editor, Mrozek, Dariusz, editor, Kasprowski, Paweł, editor, Małysiak-Mrozek, Bożena, editor, and Kostrzewa, Daniel, editor

Published
2017
Full Text
View/download PDF

9. OpenCL-Based 6D-Vision on Heterogeneous System on Chips

Author

Bromberger, Michael, Ehrle, Steffen, Scharrer, Michael, Erlinghagen, Lukas, Schick, Jens, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Knoop, Jens, editor, Karl, Wolfgang, editor, Schulz, Martin, editor, Inoue, Koji, editor, and Pionteck, Thilo, editor

Published
2017
Full Text
View/download PDF

10. Recombinant Sort: N-Dimensional Cartesian Spaced Algorithm Designed from Synergetic Combination of Hashing, Bucket, Counting and Radix Sort.

Author

Kumar, Peeyush, Gangal, Ayushe, Kumari, Sunita, and Tiwari, Sunita

Subjects
SORTING (Electronic computers), COMPUTER algorithms, SOCIAL networks
Abstract

Sorting is an essential operation which is widely used and is fundamental to some very basic day to day utilities like searches, databases, social networks and much more. Optimizing this basic operation in terms of complexity as well as efficiency is cardinal. Optimization is achieved with respect to space and time complexities of the algorithm. In this paper, a novel left-field N-dimensional cartesian spaced sorting method is proposed by combining the best characteristics of bucket sort, counting sort and radix sort, in addition to employing hashing and dynamic programming for making the method more efficient. Comparison between the proposed sorting method and various existing sorting methods like bubble sort, insertion sort, selection sort, merge sort, heap sort, counting sort, bucket sort, etc., has also been performed. The time complexity of the proposed model is estimated to be linear i.e. O(n) for the best, average and worst cases, which is better than every sorting algorithm introduced till date. [ABSTRACT FROM AUTHOR]

Published
2020
Full Text
View/download PDF

11. Using the Complete Sequences for Sorting Natural Numbers

Author

Y. N. Artamonov

Subjects
complete sequences, sorting algorithms for linear time, radix sort, nontraditional number systems, algorithms for searching and storing of numerical data, Mathematics, QA1-939
Abstract

Complete sequences are defined as infinite sequences of natural numbers, with the help of which it is possible to represent any other natural number. The most significant result, allowing to judge the completeness of any sequence, was obtained by D. Brown. The article poses the problem of representing the complete sequence of all natural numbers up to a certain limit as a sum of elements (such initial segments of complete sequences are called generating sequences). Then there is the problem of finding generating sequences of minimal length for a given limit N. The article proposes algorithms for generation of generating sequences of minimal length. A class of algorithms for generation of generating sequences containing a given generating sequence of shorter length is proposed, it allows us to introduce regular algorithms of generating complete sequences. The proposed regular algorithms for generating complete sequences are used in the development of the algorithm for sorting natural numbers without comparing them, which is the development of the radix sorting algorithm with interpretation of the bits as elements of a suitable complete sequence. The article demonstrates approaches of adapting the work of this algorithm for sorting a specific sorted sequence.

Published
2017
Full Text
View/download PDF

12. RadixInsert, a much faster stable algorithm for sorting floating-point numbers.

Author

Maus, Arne

Subjects
COMPUTER science, COMPUTER algorithms, SMART cards, COMPUTER operating systems, INTEGERS
Abstract

The problem addressed in this paper is that we want to sort an array a[] of n floating point numbers conforming to the IEEE 754 standard, both in the 64bit double precision and the 32bit single precision formats on a multi core computer with p real cores and shared memory (an ordinary PC). This we do by introducing a new stable, sorting algorithm, RadixInsert, both in a sequential version and with two parallel implementations. RadixInsert is tested on two different machines, a 2 core laptop and a 4 core desktop, outperforming the not stable Quicksort based algorithms from the Java library -- both the sequential Arrays.sort() and a merge-based parallel version Arrays.parallelsort() for 5001.5). RadixInsert is in practice O(n), but as with Quicksort it might be possible to construct numbers where RadixInsert degenerates to an O(n²) algorithm. However, this worst case for RadixInsert was not found when sorting seven quite different distributions reported in this paper. Finally, the extra memory used by RadixInsert both in its sequential and parallel versions, is n + some minor arrays whereas the sequential Quicksort in the Java library needs basically no extra memory. However, the merge based Arrays.parallelsort() in the Java library needs the same amount of n extra memory as RadixInsert. [ABSTRACT FROM AUTHOR]

Published
2019

14. BWTCP: A Parallel Method for Constructing BWT in Large Collection of Genomic Reads

Author

Wang, Heng, Peng, Shaoliang, Lu, Yutong, Wu, Chengkun, Wen, Jiajun, Liu, Jie, Zhu, Xiaoqian, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Kunkel, Julian M., editor, and Ludwig, Thomas, editor

Published
2015
Full Text
View/download PDF

15. Efficient Local Alignment Discovery amongst Noisy Long Reads

Author

Myers, Gene, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Istrail, Sorin, Series editor, Pevzner, Pavel, Series editor, Waterman, Michael S., Series editor, Brown, Dan, editor, and Morgenstern, Burkhard, editor

Published
2014
Full Text
View/download PDF

16. Loop Nesting Forests, Dominators, and Applications

Author

Georgiadis, Loukas, Laura, Luigi, Parotsidis, Nikos, Tarjan, Robert E., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Gudmundsson, Joachim, editor, and Katajainen, Jyrki, editor

Published
2014
Full Text
View/download PDF

17. One machine, one minute, three billion tetrahedra.

Author

Marot, Célestin, Pellerin, Jeanne, and Remacle, Jean‐François

Subjects
TETRAHEDRA, GEOMETRIC vertices, ALGORITHMS, SYNCHRONIZATION
Abstract

Summary: This paper presents a new scalable parallelization scheme to generate the 3D Delaunay triangulation of a given set of points. Our first contribution is an efficient serial implementation of the incremental Delaunay insertion algorithm. A simple dedicated data structure, an efficient sorting of the points, and the optimization of the insertion algorithm have permitted to accelerate reference implementations by a factor three. Our second contribution is a multithreaded version of the Delaunay kernel that is able to concurrently insert vertices. Moore curve coordinates are used to partition the point set, avoiding heavy synchronization overheads. Conflicts are managed by modifying the partitions with a simple rescaling of the space‐filling curve. The performances of our implementation have been measured on three different processors: an Intel core‐i7, an Intel Xeon Phi, and an AMD EPYC, on which we have been able to compute three billion tetrahedra in 53 seconds. This corresponds to a generation rate of over 55 million tetrahedra per second. We finally show how this very efficient parallel Delaunay triangulation can be integrated in a Delaunay refinement mesh generator, which takes as input the triangulated surface boundary of the volume to mesh. [ABSTRACT FROM AUTHOR]

Published
2019
Full Text
View/download PDF

18. Survey of GPU Based Sorting Algorithms.

Author

Singh, Dhirendra Pratap, Joshi, Ishan, and Choudhary, Jaytrilok

Subjects
*SORTING (Electronic computers), *ALGORITHMS, *GRAPHICS processing units, *PARALLEL processing, *SEQUENCE analysis
Abstract

Parallel sorting algorithms are widely studied nowadays. After the introduction of parallel processors such as graphics processing unit (GPU) and easy to use parallel programming languages such as CUDA and OpenCL, literature on parallel sorting algorithms has become vast and richer with new ideas and techniques applied to solve the famous problem of sorting. This paper presents a survey of GPU based sorting algorithms. Four sorting algorithms have been selected for this survey: Radix sort, Merge sort, Sample sort and Quick sort. Methods used in those algorithms are described in brief. The performance of these algorithms as claimed by their authors is also presented. A comparative analysis based on the literature is depicted. [ABSTRACT FROM AUTHOR]

Published
2018
Full Text
View/download PDF

19. Parallel String Sample Sort

Author

Bingmann, Timo, Sanders, Peter, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bodlaender, Hans L., editor, and Italiano, Giuseppe F., editor

Published
2013
Full Text
View/download PDF

20. Sorting and Searching by Distribution: From Generic Discrimination to Generic Tries

Author

Henglein, Fritz, Hinze, Ralf, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Shan, Chung-chieh, editor

Published
2013
Full Text
View/download PDF

23. Simpler Linear-Time Kernelization for Planar Dominating Set

Author

Hagerup, Torben, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Marx, Dániel, editor, and Rossmanith, Peter, editor

Published
2012
Full Text
View/download PDF

24. Implementation Of Bubble Sort Algorithm On 2 Fruit Models Of Data Selection Using The Java Program Language

Author

Endang Sunandar

Subjects
Insertion sort, Bubble sort, Theoretical computer science, Selection sort, Java, Computer science, Descending, Radix sort, Variants, Process (computing), Heapsort, Bubble Sort, Ascending, Data_FILES, General Earth and Planetary Sciences, sort, computer, General Environmental Science, computer.programming_language
Abstract

There are various kinds of data sorting methods that we know of which are the Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Shell Sort, Heap Sort, and Radix Sort methods. All of these methods have advantages and disadvantages of each, whose use is determined based on needs. Each method has a different algorithm, where different algorithms affect the execution time. One interesting algorithm to be implemented on 2 variant models of data sorting is the Bubble Sort algorithm, the reason is that this algorithm has a fairly long and detailed process flow to produce an ordered data sequence from a previously unordered data sequence. Two (2) data sorting variant models that will be implemented using the Bubble Sort algorithm are: Ascending data sorting variants moving from left to right, and Descending data sorting variants moving from left to right. And the device used in implementing the Bubble Sort algorithm is the Java programming language.

Published
2021
Full Text
View/download PDF

26. Engineering a Multi-core Radix Sort

Author

Wassenberg, Jan, Sanders, Peter, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Jeannot, Emmanuel, editor, Namyst, Raymond, editor, and Roman, Jean, editor

Published
2011
Full Text
View/download PDF

28. Design of an Efficient Out-of-Core Read Alignment Algorithm

Author

Konagurthu, Arun S., Allison, Lloyd, Conway, Thomas, Beresford-Smith, Bryan, Zobel, Justin, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Istrail, Sorin, editor, Pevzner, Pavel, editor, Waterman, Michael S., editor, Moulton, Vincent, editor, and Singh, Mona, editor

Published
2010
Full Text
View/download PDF

29. Automated Tuning in Parallel Sorting on Multi-core Architectures

Author

Lin, Haibo, Li, Chao, Wang, Qian, Zhao, Yi, Pan, Ninghe, Zhuang, Xiaotong, Shao, Ling, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, D’Ambra, Pasqua, editor, Guarracino, Mario, editor, and Talia, Domenico, editor

Published
2010
Full Text
View/download PDF

30. Efficient Strategies for Acceleration Structure Updates in Interactive Ray Tracing Applications on the Cell Processor

Author

Weier, Martin, Roth, Thorsten, Hinkenjann, André, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bebis, George, editor, Boyle, Richard, editor, Parvin, Bahram, editor, Koracin, Darko, editor, Kuno, Yoshinori, editor, Wang, Junxian, editor, Wang, Jun-Xuan, editor, Pajarola, Renato, editor, Lindstrom, Peter, editor, Hinkenjann, André, editor, Encarnação, Miguel L., editor, Silva, Cláudio T., editor, and Coming, Daniel, editor

Published
2009
Full Text
View/download PDF

31. Engineering Radix Sort for Strings

Author

Kärkkäinen, Juha, Rantala, Tommi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Amir, Amihood, editor, Turpin, Andrew, editor, and Moffat, Alistair, editor

Published
2009
Full Text
View/download PDF

33. Statistical Substring Reduction in Linear Time

Author

Lü, Xueqiang, Zhang, Le, Hu, Junfeng, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carbonell, Jaime G., editor, Siekmann, Jörg, editor, Su, Keh-Yih, editor, Tsujii, Jun’ichi, editor, Lee, Jong-Hyeok, editor, and Kwong, Oi Yee, editor

Published
2005
Full Text
View/download PDF

34. On Adaptive Integer Sorting

Author

Pagh, Anna, Pagh, Rasmus, Thorup, Mikkel, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Albers, Susanne, editor, and Radzik, Tomasz, editor

Published
2004
Full Text
View/download PDF

35. Using Compact Tries for Cache-Efficient Sorting of Integers

Author

Sinha, Ranjan, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Ribeiro, Celso C., editor, and Martins, Simone L., editor

Published
2004
Full Text
View/download PDF

38. Algorithms for sorting and recognizing of undercut features in plastic products

Author

Sunil I. Sangolli, B.G. Koujalagi, Chandrashekhar V. Adake, S.C. Pilli, and Amith Gadagi

Subjects
010302 applied physics, Sorting algorithm, Computer science, Radix sort, Sorting, CAD, 02 engineering and technology, General Medicine, 021001 nanoscience & nanotechnology, 01 natural sciences, Boundary representation, Product (mathematics), 0103 physical sciences, Feature (machine learning), Undercut, 0210 nano-technology, Algorithm, ComputingMethodologies_COMPUTERGRAPHICS
Abstract

The automatic recognition of features in injection molded parts and assemblies are a crucial step in design to improve efficiency and effectiveness during the development and manufacturing stages. . When an internal undercut is present in the ejecting direction the finished plastic product cannot be directly ejected from the mold. Algorithms using the geometry of the undercut and the molded product are developed to avoid interference between the mould and the molded product when the product is ejected from its mould. The CAD models are developed using both the boundary representation as well as the CSG approach. This paper presents the development of computer algorithms in Java for sorting and recognizing undercut and mold features. The STEP AP 203 translator is used to communicate with various CAD systems. The proposed algorithm takes multiple feature models of plastic products as input and sorts the features using the Radix sort algorithm and then recognizes the features of the undercuts and the molds. Through the volumetric decomposition and the sorting algorithm the proposed approach can automatically recognize undercut features and efficiently calculate the undercut locations and dimensions using the feature parameters.

Published
2021

42. Self-Tuning Parallelism

Author

Werner-Kytölä, Otilia, Tichy, Walter F., Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Bubak, Marian, editor, Afsarmanesh, Hamideh, editor, Hertzberger, Bob, editor, and Williams, Roy, editor

Published
2000
Full Text
View/download PDF

43. Partitioned Parallel Radix Sort

Author

Lee, Shin-Jae, Jeon, Minsoo, Sohn, Andrew, Kim, Dongseung, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Valero, Mateo, editor, Joe, Kazuki, editor, Kitsuregawa, Masaru, editor, and Tanaka, Hidehiko, editor

Published
2000
Full Text
View/download PDF

45. Scalable energy-efficient parallel sorting on a fine-grained many-core processor array

Author

Brent Bohnenstiehl, Lucas Stillmaker, Bevan M. Baas, and Aaron Stillmaker

Subjects
Computer Networks and Communications, Computer science, Library sort, Radix sort, 020206 networking & telecommunications, 02 engineering and technology, Parallel computing, External sorting, Processor array, Theoretical Computer Science, Artificial Intelligence, Hardware and Architecture, 0202 electrical engineering, electronic engineering, information engineering, sort, 020201 artificial intelligence & image processing, Throughput (business), Software, Efficient energy use
Abstract

Three parallel sorting applications and two list output protocols for the first phase of an external sort execute on a fine-grained many-core processor array that contains no algorithm-specific hardware acting as a co-processor with a variety of array sizes. Results are generated using a cycle-accurate model based on measured data from a fabricated many-core chip, and simulated for different processor array sizes. The data shows most energy efficient first-phase many-core sort requires over 65 × lower energy than GNU C++ standard library sort performed on an Intel laptop-class processor and over 105 × lower energy than a radix sort running on an Nvidia GPU. In addition, the highest first-phase throughput many-core sort is over 9.8 × faster than the std::sort and over 14 × faster than the radix sort. Both phases of a 10 GB external sort require 6.2 × lower energy × time energy delay product than the std::sort and over 13 × lower energy × time than the radix sort.

Published
2020

49. Oblivious Linear Group Actions and Applications

Author

Hiraku Morita, Goichiro Hanaoaka, Nuttapong Attrapadung, Kazunari Tozawa, Takahiro Matsuda, Tadanori Teruya, Kazuma Ohara, and Jacob C. N. Schuldt

Subjects
TheoryofComputation_MISCELLANEOUS, Protocol (science), Theoretical computer science, Chase, Computer science, Radix sort, Server, Secure multi-party computation, computer science, Secret sharing, Matrix multiplication, Block (data storage)
Abstract

In this paper we propose efficient two-party protocols for obliviously applying a (possibly random) linear group action to a data set. Our protocols capture various applications such as oblivious shuffles, circular shifts, matrix multiplications, to name just a few. A notable feature enjoyed by our protocols, is that they admit a round-optimal (more precisely, one-round) online computation phase, once an input-independent off-line computation phase has been completed. Our oblivious shuffle is the first to achieve a round-optimal online phase. The most efficient instantiations of our protocols are obtained in the so-called client-aided client-server setting, where the offline phase is run by a semi-honest input party (client) who will then distribute the generated correlated randomness to the computing parties (servers). When comparing the total running time to the previous best two-party oblivious shuffle protocol by Chase et al. (Asiacrypt 2020), our shuffle protocol in this client-aided setting is up to 105 times and 152 times faster, in the LAN and WAN setting, respectively. We additionally show how the Chase et al. protocol (which is a standard two-party protocol) can be modified to leverage the advantages of the client-aided setting, but show that, even doing so, our scheme is still two times faster in the online phase and 1.34 times faster in total on average. An additional feature of our protocols is that they allow to re-invoke a previously generated group action, or its inverse, in subsequent runs. This allows us to utilize randomize-then-reveal techniques, which are crucial for constructing efficient protocols in complex applications. As an application, we construct a new oblivious sorting protocol implementing radix sort. Our protocol is based on a similar approach to the three-party protocol by Chida et al. (IACR ePrint 2019/965), but using our oblivious shuffle as a building block as well as various optimizations, we obtain a two-party protocol (in the client-aided setting) with improved online running time and a reduced number of rounds. As other applications, we also obtain efficient protocols for oblivious selection, oblivious unit-vectorization, oblivious multiplexer, oblivious polynomial evaluation, arithmetic-to-boolean share conversions, and more.

Published
2021

Catalog

Books, media, physical & digital resources
See catalog results