Dergiler / Mathematical and Computational Applications / 2010 / Cilt: 15 - Sayı: 2

A new sorting algorithm for accelerating join-based queries

Sayfa
208–217
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

The performed experimental results have shown that the proposed algorithm outperforms other stable sorting algorithms that are designed for join-based queries.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez:The performance of several Database Management Systems (DBMSs) and Data Stream Management Systems (DSMSs) queries is dominated by the cost of the sorting algorithm.
📊
Temel Bulgular & Veri:Sorting is an integral component of most database management systems.
💡
Sonuç & Katkı:The performed experimental results have shown that the proposed algorithm outperforms other stable sorting algorithms that are designed for join-based queries.
🔬Tür:Araştırma Makalesi
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Alan Parametreleri

Abstract

The performance of several Database Management Systems (DBMSs) and Data Stream Management Systems (DSMSs) queries is dominated by the cost of the sorting algorithm. Sorting is an integral component of most database management systems. Stable sorting algorithms play an important role in DBMS queries since such operations requires stable sorting outputs. In this paper, we present a new stable sorting algorithm for internal sorting that scans an unsorted input array of length n and arranges it into m sorted sub-arrays. By using the m-way merge algorithm, the sorted m subarrays will be merged into the final output sorted array. The proposed algorithm keeps the stability of the keys intact. The scanning process requires linear time complexity (O(n)) in the best case, and O(n log m) in the worst case, and the m-way merge process requires O (n log m) time complexity. The proposed algorithm has a time complexity of O (n log m) element comparisons. The performed experimental results have shown that the proposed algorithm outperforms other stable sorting algorithms that are designed for join-based queries.

🔖

Bu Makaleye Atıf Yap

MATHKOUR, H. I. (2010). A new sorting algorithm for accelerating join-based queries. Mathematical and Computational Applications, Cilt: 15 - Sayı: 2, 208–217. https://ajindex.com/articles/279936

📄 Tam Metin PDF Okuyucu

📄

PDF görüntüleyici hazırlanıyor...

Kaynakça (17)

  1. Y. Azar, A. Broder, A. Karlin, and E. Upfal, Balanced allocations, in Proceedings of 26th ACM Symposium on the Theory of Computing, 593-602, 1994,
  2. R.A. Krishna, A. Das, J. Gehrke, F. Korn, S. Muthukrishnan, and D. Shrivastava, Efficient approximation of correlated sums on data streams, TKDE, 2003
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition MIT Press, Cambridge, MA, 2001
  4. D. Knuth, Sorting and Searching, Volume 3 of the Art of Computer Programming, Addison-Wesley Publishing Company, Reading, MA, 1973
  5. A. Broder and M. Mitzenmacher, Using multiple hash functions to improve IP lookups, in Proceedings of IEEE INFOCOM, 2001
  6. N. Bandi, C. Sun, D. Agrawal, and A. El Abbadi, Hardware acceleration in commercial databases: A case study of spatial operations, Proceedings of the Thirtieth international conference on Very large data bases, 30, 1021-1032, 2004
  7. S. Manegold, P.A. Boncz, and M.L. Kersten, What happens during a join? Dissecting CPU and memory optimization effects, in Proceedings of 26th International Conference on Very Large Data Bases, 26, 339–350, 2000
  8. A. LaMarca and R. E. Ladner, The influence of caches on the performance of heaps, ACM Journal of Experimental Algorithmics, 1, 4-es, 1996
  9. A. Das, J. Gehrke, and M. Riedewald, Approximate join processing over data streams, in Proceedings of the 2003 ACM SIGMOD international conference on Management of data, ACM Press, 40-51, 2003
  10. J.V. Lunteren, Searching very large routing tables in wide embedded memory, in Proceedings of IEEE Globecom, November 2001
  11. J.L. Bentley and R. Sedgewick, Fast algorithms for sorting and searching strings, ACM-SIAM SODA ’97, 360–369, 1997
  12. G. Franceschini and V. Geffert. An In-Place Sorting with O(n log n) Comparisons and O(n) Moves, IEEE FOCS ’03, 242–250, 2003
  13. L. Arge, P. Ferragina, R. Grossi, and J.S. Vitter, On sorting strings in external memory, ACM STOC ’97, 540–548, 1997
  14. R.C. Agarwal, A super scalar sort algorithm for RISC processors, SIGMOD Record (ACM Special Interest Group on Management of Data), 25(2), 240–246, June 1996
  15. A. Arasu and G. S. Manku, Approximate counts and quantiles over sliding windows, PODS, 2004
  16. M.A. Bender, E.D. Demaine, and M. Farach-Colton, Cache-oblivious B-trees, IEEE FOCS ’00, 399–409, 2000
  17. P.A. Boncz, S. Manegold, and M.L. Kersten, Database architecture optimized for the new bottleneck: Memory access, in Proceedings of the Twe