Mathematics

Research

12 pages, 2791 KiB

Open AccessArticle

Interpolation Once Binary Search over a Sorted List

by Jun-Lin Lin

Mathematics 2024, 12(9), 1394; https://doi.org/10.3390/math12091394 - 2 May 2024

Viewed by 1230

Abstract

Searching over a sorted list is a classical problem in computer science. Binary Search takes at most

⌊\log_{2} n⌋ + 1

tries to find an item in a sorted list of size n. Interpolation Search achieves an average time complexity [...] Read more.

Searching over a sorted list is a classical problem in computer science. Binary Search takes at most

⌊\log_{2} n⌋ + 1

tries to find an item in a sorted list of size n. Interpolation Search achieves an average time complexity of

O (\log \log n)

for uniformly distributed data. Hybrids of Binary Search and Interpolation Search are also available to handle data with unknown distributions. This paper analyzes the computation cost of these methods and shows that interpolation can significantly affect their performance—accordingly, a new method, Interpolation Once Binary Search (IOBS), is proposed. The experimental results show that IOBS outperforms the hybrids of Binary Search and Interpolation Search for nonuniformly distributed data. Full article

(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

► Show Figures

Figure 1

14 pages, 2531 KiB

Open AccessArticle

Efficient List Intersection Algorithm for Short Documents by Document Reordering

by Lianyin Jia, Dongyang Li, Haihe Zhou and Fengling Xia

Mathematics 2024, 12(9), 1328; https://doi.org/10.3390/math12091328 - 26 Apr 2024

Viewed by 689

Abstract

List intersection plays a pivotal role in various domains such as search engines, database systems, and social networks. Efficient indexes and query strategies can significantly enhance the efficiency of list intersection. Existing inverted index-based algorithms fail to utilize the length information of documents [...] Read more.

List intersection plays a pivotal role in various domains such as search engines, database systems, and social networks. Efficient indexes and query strategies can significantly enhance the efficiency of list intersection. Existing inverted index-based algorithms fail to utilize the length information of documents and require excessive list intersections, resulting in lower efficiency. To address this issue, in this paper, we propose the LDRpV (Length-based Document Reordering plus Verification) algorithm. LDRpV filters out documents that are unlikely to satisfy the intersection results by reordering documents based on their length, thereby reducing the number of candidates. Additionally, to minimize the number of list intersection operations, an intersection and verification strategy is designed, where only the first

m

lists are intersected, and the resulting candidate set is directly verified. This approach effectively improves the efficiency of list intersection. Experimental results on four real datasets demonstrate that LDRpV can achieve a maximum efficiency improvement of 46.69% compared to the most competitive counterparts. Full article

(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

► Show Figures

Figure 1

16 pages, 1049 KiB

Open AccessArticle

An Improved Fault Diagnosis Algorithm for Highly Scalable Data Center Networks

by Wanling Lin, Xiao-Yan Li, Jou-Ming Chang and Xiangke Wang

Mathematics 2024, 12(4), 597; https://doi.org/10.3390/math12040597 - 17 Feb 2024

Viewed by 853

Abstract

Fault detection and localization are vital for ensuring the stability of data center networks (DCNs). Specifically, adaptive fault diagnosis is deemed a fundamental technology in achieving the fault tolerance of systems. The highly scalable data center network (HSDC) is a promising structure of [...] Read more.

Fault detection and localization are vital for ensuring the stability of data center networks (DCNs). Specifically, adaptive fault diagnosis is deemed a fundamental technology in achieving the fault tolerance of systems. The highly scalable data center network (HSDC) is a promising structure of server-centric DCNs, as it exhibits the capacity for incremental scalability, coupled with the assurance of low cost and energy consumption, low diameter, and high bisection width. In this paper, we first determine that both the connectivity and diagnosability of the m-dimensional complete HSDC, denoted by

H S D C_{m} (m)

, are m. Further, we propose an efficient adaptive fault diagnosis algorithm to diagnose an

H S D C_{m} (m)

within three test rounds, and at most

N + 4 m (m - 2)

tests with

m \geq 3

(resp. at most nine tests with

m = 2

), where

N = m \cdot 2^{m}

is the total number of nodes in

H S D C_{m} (m)

. Our experimental outcomes demonstrate that this diagnosis scheme of HSDC can achieve complete diagnosis and significantly reduce the number of required tests. Full article

(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

► Show Figures

Figure 1

12 pages, 1366 KiB

Open AccessArticle

A Novel Conditional Connectivity and Hamiltonian Connectivity of BCube with Various Faulty Elements

by Yali Lv, Cheng-Kuan Lin and Lantao You

Mathematics 2023, 11(15), 3404; https://doi.org/10.3390/math11153404 - 4 Aug 2023

Viewed by 918

Abstract

BCube is one of the main data center networks because it has many attractive features. In practical applications, the failure of components or physical connections is inevitable. In data center networks in particular, switch failures are unavoidable. Fault-tolerance capability is one main aspect [...] Read more.

BCube is one of the main data center networks because it has many attractive features. In practical applications, the failure of components or physical connections is inevitable. In data center networks in particular, switch failures are unavoidable. Fault-tolerance capability is one main aspect to measure the performance of data center networks. Connectivity, fault tolerance Hamiltonian connectivity, and fault tolerance Hamiltonicity are important parameters that assess the fault tolerance of networks. In general, the distribution of fault elements is scattered, and it is necessary to consider the distribution of fault elements in different dimensions. We research the fault tolerance of BCube when considering faulty switches and faulty links/edges that distribute in different dimensions. We also investigate the connectivity, fault tolerance Hamiltonian connectivity, and Hamiltonicity. This study better evaluates the fault-tolerant performance of data center networks. Full article

(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

► Show Figures

Figure 1

14 pages, 2694 KiB

Open AccessArticle

Three Edge-Disjoint Hamiltonian Cycles in Folded Locally Twisted Cubes and Folded Crossed Cubes with Applications to All-to-All Broadcasting

by Kung-Jui Pai

Mathematics 2023, 11(15), 3384; https://doi.org/10.3390/math11153384 - 2 Aug 2023

Viewed by 1279

Abstract

All-to-all broadcasting means to distribute the exclusive message of each node in the network to all other nodes. It can be handled by rings, and a Hamiltonian cycle is a ring that visits each vertex exactly once. Multiple edge-disjoint Hamiltonian cycles, abbreviated as [...] Read more.

All-to-all broadcasting means to distribute the exclusive message of each node in the network to all other nodes. It can be handled by rings, and a Hamiltonian cycle is a ring that visits each vertex exactly once. Multiple edge-disjoint Hamiltonian cycles, abbreviated as EDHCs, have two application advantages: (1) parallel data broadcast and (2) edge fault-tolerance in network communications. There are three edge-disjoint Hamiltonian cycles on n-dimensional locally twisted cubes and n-dimensional crossed cubes while n ≥ 6, respectively. Locally twisted cubes, crossed cubes, folded locally twisted cubes (denoted as FLTQ_n), and folded crossed cubes (denoted as FCQ_n) are among the hypercube-variant network. The topology of hypercube-variant network has more wealth than normal hypercubes in network properties. Then, the following results are presented in this paper: (1) Using the technique of edge exchange, three EDHCs are constructed in FLTQ₅ and FCQ₅, respectively. (2) According to the recursive structure of FLTQ_n and FCQ_n, there are three EDHCs in FLTQ_n and FCQ_n while n ≥ 6. (3) Considering that multiple faulty edges will occur randomly, the data broadcast performance of three EDHCs in FLTQ_n and FCQ_n is evaluated by simulation when 5 ≤ n ≤ 9. Full article

(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

► Show Figures

Figure 1

17 pages, 2167 KiB

Open AccessArticle

Task Scheduling Mechanism Based on Reinforcement Learning in Cloud Computing

by Yugui Wang, Shizhong Dong and Weibei Fan

Mathematics 2023, 11(15), 3364; https://doi.org/10.3390/math11153364 - 1 Aug 2023

Cited by 8 | Viewed by 2540

Abstract

The explosive growth of users and applications in IoT environments has promoted the development of cloud computing. In the cloud computing environment, task scheduling plays a crucial role in optimizing resource utilization and improving overall performance. However, effective task scheduling remains a key [...] Read more.

The explosive growth of users and applications in IoT environments has promoted the development of cloud computing. In the cloud computing environment, task scheduling plays a crucial role in optimizing resource utilization and improving overall performance. However, effective task scheduling remains a key challenge. Traditional task scheduling algorithms often rely on static heuristics or manual configuration, limiting their adaptability and efficiency. To overcome these limitations, there is increasing interest in applying reinforcement learning techniques for dynamic and intelligent task scheduling in cloud computing. How can reinforcement learning be applied to task scheduling in cloud computing? What are the benefits of using reinforcement learning-based methods compared to traditional scheduling mechanisms? How does reinforcement learning optimize resource allocation and improve overall efficiency? Addressing these questions, in this paper, we propose a Q-learning-based Multi-Task Scheduling Framework (QMTSF). This framework consists of two stages: First, tasks are dynamically allocated to suitable servers in the cloud environment based on the type of servers. Second, an improved Q-learning algorithm called UCB-based Q-Reinforcement Learning (UQRL) is used on each server to assign tasks to a Virtual Machine (VM). The agent makes intelligent decisions based on past experiences and interactions with the environment. In addition, the agent learns from rewards and punishments to formulate the optimal task allocation strategy and schedule tasks on different VMs. The goal is to minimize the total makespan and average processing time of tasks while ensuring task deadlines. We conducted simulation experiments to evaluate the performance of the proposed mechanism compared to traditional scheduling methods such as Particle Swarm Optimization (PSO), random, and Round-Robin (RR). The experimental results demonstrate that the proposed QMTSF scheduling framework outperforms other scheduling mechanisms in terms of the makespan and average task processing time. Full article

(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

► Show Figures

Figure 1

14 pages, 3404 KiB

Open AccessArticle

Dual Protection Routing Trees on Graphs

by Kung-Jui Pai

Mathematics 2023, 11(14), 3255; https://doi.org/10.3390/math11143255 - 24 Jul 2023

Viewed by 1102

Abstract

In IP networks, packet forwarding is destination-based and hop-by-hop, and routes are built as needed. Kwong et al. introduced a protection routing in which packet delivery to the destination node can proceed uninterrupted in the event of any single node or link failure. [...] Read more.

In IP networks, packet forwarding is destination-based and hop-by-hop, and routes are built as needed. Kwong et al. introduced a protection routing in which packet delivery to the destination node can proceed uninterrupted in the event of any single node or link failure. He then showed that “whether there is a protection routing to the destination” is NP-complete. Tapolcai found that two completely independent spanning trees, abbreviated as CISTs, can be used to configure the protection routing. In this paper, we proposed dual protection routing trees, denoted as dual-PRTs to replace CISTs, which are less restrictive than CISTs. Next, we proposed a transformation algorithm that uses dual-PRTs to configure the protection routing. Taking complete graphs K_n, complete bipartite graphs K_m,n, hypercubes Q_n, and locally twisted cubes LTQ_n as examples, we provided a recursive method to construct dual-PRTs on them. This article showed that there are no two CISTs on K_3,3, Q₃, and LTQ₃, but there exist dual-PRTs that can be used to configure the protection routing. As shown in the performance evaluation of simulation results, for both Q_n and LTQ_n, we get the average path length of protection routing configured by dual-PRTs is shorter than that by two CISTs. Full article

(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

► Show Figures

Figure 1

12 pages, 295 KiB

Open AccessArticle

The Diagnosability of the Generalized Cartesian Product of Networks

by Meirun Chen and Cheng-Kuan Lin

Mathematics 2023, 11(12), 2615; https://doi.org/10.3390/math11122615 - 7 Jun 2023

Cited by 2 | Viewed by 1163

Abstract

Motivated by two typical ways to construct multiprocessor systems, matching composition networks and cycle composition networks, we generalize the definition of the Cartesian product of networks and consider the classical diagnosability of the generalized Cartesian product of networks (GCPNs). In this paper, we [...] Read more.

Motivated by two typical ways to construct multiprocessor systems, matching composition networks and cycle composition networks, we generalize the definition of the Cartesian product of networks and consider the classical diagnosability of the generalized Cartesian product of networks (GCPNs). In this paper, we determine the accurate value of the classical diagnosability of the generalized Cartesian product of networks (GCPNs) under the PMC model and the MM

^{*}

model. Full article

(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

► Show Figures

Figure 1

12 pages, 606 KiB

Open AccessArticle

Super Spanning Connectivity of the Folded Divide-and-SwapCube

by Lantao You, Jianfeng Jiang and Yuejuan Han

Mathematics 2023, 11(11), 2581; https://doi.org/10.3390/math11112581 - 5 Jun 2023

Cited by 1 | Viewed by 1118

Abstract

A

k^{*}

-container of a graph G is a set of k disjoint paths between any pair of nodes whose union covers all nodes of G. The spanning connectivity of G,

κ^{*} (G)

, is the largest [...] Read more.

A

k^{*}

-container of a graph G is a set of k disjoint paths between any pair of nodes whose union covers all nodes of G. The spanning connectivity of G,

κ^{*} (G)

, is the largest k, such that there exists a

j^{*}

-container between any pair of nodes of G for all

1 \leq j \leq k

. If

κ^{*} (G) = κ (G)

, then G is super spanning connected. Spanning connectivity is an important property to measure the fault tolerance of an interconnection network. The divide-and-swap cube

D S C_{n}

is a newly proposed hypercube variant, which reduces the network cost from

O (n^{2})

to

O (n {log}_{2} n)

compared with the hypercube and other hypercube variants. The folded divide-and-swap cube

F D S C_{n}

is proposed based on

D S C_{n}

to reduce the diameter of

D S C_{n}

. Both

D S C_{n}

and

F D S C_{n}

possess many better properties than hypercubes. In this paper, we investigate the super spanning connectivity of

F D S C_{n}

where

n = 2^{d}

and

d \geq 1

. We show that

κ^{*} (F D S C_{n}) = κ (F D S C_{n}) = d + 2

, which means there exists an m-DPC(node-disjoint path cover) between any pair of nodes in

F D S C_{n}

for all

1 \leq m \leq d + 2

. Full article

(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

► Show Figures

Figure 1

14 pages, 472 KiB

Open AccessArticle

All-to-All Broadcast Algorithm in Galaxyfly Networks

by Hongbin Zhuang, Jou-Ming Chang, Xiao-Yan Li, Fangying Song and Qinying Lin

Mathematics 2023, 11(11), 2459; https://doi.org/10.3390/math11112459 - 26 May 2023

Viewed by 1153

Abstract

The design of interconnection networks is a fundamental aspect of high-performance computing (HPC) systems. Among the available topologies, the Galaxyfly network stands out as a low-diameter and flexible-radix network for HPC applications. Given the paramount importance of collective communication in HPC performance, in [...] Read more.

The design of interconnection networks is a fundamental aspect of high-performance computing (HPC) systems. Among the available topologies, the Galaxyfly network stands out as a low-diameter and flexible-radix network for HPC applications. Given the paramount importance of collective communication in HPC performance, in this paper, we present two different all-to-all broadcast algorithms for the Galaxyfly network, which adhere to the supernode-first rule and the router-first rule, respectively. Our performance evaluation validates their effectiveness and shows that the first algorithm has a higher degree of utilization of network channels, and that the second algorithm can significantly reduce the average time for routers to collect packets from the supernode. Full article

(This article belongs to the Special Issue Advances of Computer Algorithms and Data Structures)

► Show Figures

Figure 1

Journal Menu

Journal Browser

Advances of Computer Algorithms and Data Structures

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Benefits of Publishing in a Special Issue

Published Papers (10 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI