Jinhua Cui

Weiguo Wu
email: wgwu@xjtu.edu.cn

Shiqiang Nie

Jianhang Huang

Zhuang Hu

Nianjun Zou

Yinfeng Wang

VIOS: A Variation-aware I/O Scheduler for Flash-based Storage Systems

Keywords: process variation, solid state drive, I/O scheduling, flash memory, parallelism

NAND flash memory has gained widespread acceptance in storage systems because of its superior write/read performance, shockresistance and low-power consumption. I/O scheduling for Solid State Drives (SSDs) has received much attention in recent years for its ability to take advantage of the rich parallelism within SSDs. However, most state-of-the-art I/O scheduling algorithms are oblivious to the increasingly significant inter-block variation introduced by the advanced technology scaling. This paper proposes a variation-aware I/O scheduler by exploiting the speed variation among blocks to minimize the access conflict latency of I/O requests. The proposed VIOS schedules I/O requests into a hierarchical-batch structured queue to preferentially exploit channel-level parallelism, followed by chip-level parallelism. Moreover, conflict write requests are allocated to faster blocks to reduce access conflict of waiting requests. Experimental results shows that VIOS reduces write latency significantly compared to state-of-the-art I/O schedulers while attaining high read efficiency.

Introduction

As NAND flash storage capacity becomes cheaper, NAND flash-based SSDs are being regarded as powerful alternatives to traditional Hard Disk Drives (HDDs) in a wide variety of storage systems [START_REF] Min | SFS: random write considered harmful in solid state drives[END_REF]. However, SSDs introduce an out-of-place update mechanism and exhibit asymmetric I/O properties. In addition, a typical SSD usually offers rich parallelism by consisting of a number of channels with each channel connecting to multiple NAND flash chips [START_REF] Hu | Exploring and exploiting the multilevel parallelism inside SSDs for improved performance and endurance[END_REF][START_REF] Chen | Essential roles of exploiting internal parallelism of flash memory based solid state drives in high-speed data processing[END_REF]. Most of conventional I/O schedulers including NOOP, CFQ and Anticipatory are designed to mitigate the high seek and rotational costs in mechanical disks, leading to many barriers to take full advantage of SSDs. Thus, I/O scheduling for SSDs has received much attention for its ability to take advantage of the unique properties within SSDs to maximize read and write performance.

Most of existing I/O scheduling algorithms for SSDs, such as PAQ [START_REF] Jung | Physically addressed queueing (PAQ): improving parallelism in solid state disks[END_REF], PIQ [START_REF] Gao | Exploiting parallelism in i/o scheduling for access conflict minimization in flash-based solid state drives[END_REF] and AOS [START_REF] Li | AOS: Adaptive Out-of-order Scheduling for Write-caused Interference Reduction in Solid State Disks[END_REF], focus on avoiding resource contention resultant from shared SSD resources, while others take special consideration of Flash-Translation-Layer (FTL) [START_REF] Wang | An I/O scheduler based on fine-grained access patterns to improve SSD performance and lifespan[END_REF] and garbage collection [START_REF] Jung | HIOS: a host interface I/O scheduler for solid state disks[END_REF]. These works have demonstrated the importance of I/O scheduling for SSDs to reduce the number of read and write requests enrolled in conflict, which are the major contributors to access latency. However, little attention has been paid to dynamically optimize the data transfer latency, which could naturally reduce the access conflict latency when conflicts are unavoidable anymore.

The capacity of NAND flash memory is increasing continuously, as a result of technology scaling from 65nm to the latest 10nm technology and the bit density improvement from 1 bit per cell to the latest 6 bits per cell [9, 10, ?]. Unfortunately, for newer technology nodes, the memory block P/E cycling endurance has significantly dropped and process variation has become relatively much more significant. Recently many works have been proposed to exploit the process variation from different perspectives. Pan et al. [START_REF] Pan | Error rate-based wear-leveling for NAND flash memory at highly scaled technology nodes[END_REF] presented a dynamic BER-based greedy wear-leveling algorithm that uses BER statistics as the measurement of memory block wear-out pace by taking into account of inter-block P/E cycling endurance variation. Woo et al. [START_REF] Woo | Diversifying wear index for MLC NAND flash memory to extend the lifetime of SSDs[END_REF] introduced a new measure that predicts the remaining lifetime of a flash block more accurately than the erase count based on the findings that all the flash blocks could survive much longer than the guaranteed numbers and the number of P/E cycles varies significantly among blocks. Shi et al. [START_REF] Shi | Exploiting Process Variation for Write Performance Improvement on NAND Flash Memory Storage Systems[END_REF] further exploited the process variation by detecting supported write speeds during the lifetime of each flash block and allocating blocks in a way that hotter data are matched with faster blocks, but they did not reorder the requests in the I/O scheduling layer. Therefore, none of these works focuses on incorporating the awareness of inter-block variation into I/O scheduling to minimize the access conflict latency of I/O requests. This paper proposes a variation-aware I/O scheduler to exploit the speed variation among blocks for write performance improvement without degrading read performance. The key insight behind the design of VIOS is that a variation-aware scheduler can organize the blocks of each chip in a red-black tree according to their detected write speeds and maintain a global chip-state vector, where the current number of requests for each chip is recorded, so as to identify conflict requests. By scheduling arrived requests into hierarchicalbatch structured queues to give channel-level parallelism a higher priority than chip-level parallelism and allocating conflict write requests to faster blocks to exploit inter-block speed variation, access conflict latency of waiting requests is reduced significantly. Trace-based simulations are carried out to demonstrate the effectiveness of the proposed variation-aware I/O scheduling algorithm.

The rest of the paper presents the background and related works in Section 2. Section 3 describes the design techniques and implementation issues of our VIOS for flash storage devices. In Section 4, experimental evaluation and comparison with several alternative I/O schedulers are illustrated. Section 5 concludes this paper.

RAM

BACKGROUND AND RELATED WORK

SSD Organization

Flash memory chips are organized in channels and ways, as shown in Figure 1. Within each flash memory chip are one or more dies, each further consisting of multiple planes, which are the smallest unit to be accessed independently and concurrently. Each plane is composed of a number of erase units, called blocks, and a block is usually comprised of multiple pages, which are the smallest unit to read/write. There are four main levels of parallelism which can be exploited to accelerate the read/write bandwidth of SSDs. Actually, the importance of exploiting parallelism on read/write performance improvement has been testified by numerous research works from different perspectives. For example, Roh et al. [START_REF] Roh | B+-tree index optimization by exploiting internal parallelism of flash-based solid state drives[END_REF] explored to enhance B+-trees insert and point-search performance by integrating a new I/O request concept (psync I/O) into the B+-tree which can exploit the internal parallelism of SSDs in a single process, Hu et al. [START_REF] Hu | Exploring and exploiting the multilevel parallelism inside SSDs for improved performance and endurance[END_REF] argued that the utilization of parallelism, primarily determined by different advanced commands, allocation schemes, and the priority order of exploiting the four levels of parallelism, will directly and significantly impact the performance and endurance of SSDs.

Since the advance command support required by the die and plane level parallelism is not widely supported by most of SSDs, the degree of parallelism is usually governed by the number of channels multiplied by the number of flash memory chips in a channel, without taking the die and plane level parallelism into consideration. In this paper, our VIOS also exploit both channel-level parallelism and chip-level parallelism by scheduling arrived requests into hierarchical-batch structured queues.

Process Variation of Flash Memory

Along with the bit density developments and technology scaling of NAND flash memory, the aggravating process variation (PV) among blocks has been mag-nified, which results in largely different P/E cycling endurance within different memory blocks when given the same ECC. PV is caused by the naturally occurring variation in the attributes of transistors, such as gate length, width and oxide thickness, when integrated circuits are fabricated. The distribution of the Bit Error Rates (BER) of flash blocks is characterized as the log Gaussian distribution by measuring 1000 blocks of a MLC NAND Flash memory chip manufactured in 35-nm technology at the same 15K P/E cycles [START_REF] Pan | Error rate-based wear-leveling for NAND flash memory at highly scaled technology nodes[END_REF].

Besides, there is a close relationship between BER and the speed of write operations. Typically, when program operations are carried out to write data into flash memory cells, the incremental step pulse programming (ISPP) scheme is introduced to appropriately optimize program voltage with the certain step size ∆V p that triggers a trade-off between write speed and BER. Using larger ∆V p , fewer steps are used to the desired level, thus the write latency is shorter. As the promising effect of reducing the write latency of write requests, however, the margin for tolerating retention errors is also reduced, resulting in higher BER. Therefore, with the awareness of both process variation and the BERspeed relationship, write speed for lower-BER blocks can be increased at the cost of reduced noise margins, while that for higher-BER blocks should be carefully optimized without exceeding the capability of the deployed ECC. The challenge to detect the proper write speed for each block at its current worn out state is also solved by periodically reading out the written data to find out the number of faulty bits, and the analysis indicates that overhead is negligible [START_REF] Shi | Exploiting Process Variation for Write Performance Improvement on NAND Flash Memory Storage Systems[END_REF]. In this paper, the blocks of each chip are sorted according to their detected write speeds and conflict write requests are allocated to faster blocks to reduce access conflict of waiting requests.

I/O Scheduler for Flash-Based SSDs

An increasing number of I/O scheduling algorithms have been proposed to improve flash memory storage system performance from different perspectives. The first two algorithms for Flash-Based SSDs called IRBW-FIFO and IRBW-FIFO-RP were designed by Kim et al. [START_REF] Kim | Disk schedulers for solid state drivers[END_REF]. The basic idea is to arrange write requests into bundles of an appropriate size while read requests are independently scheduled by taking the read/write interference into consideration. Numerous research works enhanced the IRBW-FIFO and IRBW-FIFO-RP by exploiting rich parallelism in I/O scheduling, such as PAQ [START_REF] Jung | Physically addressed queueing (PAQ): improving parallelism in solid state disks[END_REF] and PIQ [START_REF] Gao | Exploiting parallelism in i/o scheduling for access conflict minimization in flash-based solid state drives[END_REF]. In addition, there is also recognition on the importance of fairness in multi-programmed computer systems and multi-tenant cloud systems, such as FIOS [START_REF] Park | FIOS: a fair, efficient flash I/O scheduler[END_REF] and FlashFQ [START_REF] Shen | FlashFQ: A Fair Queueing I/O Scheduler for Flash-Based SSDs[END_REF].

However, little attention has been paid to optimize the data transfer latency dynamically, which could naturally reduce the access conflict latency when conflicts can not be avoided anymore. Our VIOS focuses on incorporating the awareness of inter-block variation into I/O scheduling to minimize the access conflict latency of I/O requests. Fortunately, all these existing algorithms are somewhat orthogonal to our work, and can be used concurrently with the proposed VIOS to optimize the efficiency of flash-based I/O scheduling. Motivated by the increasingly significant inter-block variation introduced by the advanced technology scaling, a variation-aware I/O scheduler is proposed to minimize the access conflict latency of I/O requests. The proposed VIOS scheduler is implemented in the host interface logic (HIL), where the knowledge of both the interface protocols and SSD specific characteristics contributes to better device-specific scheduling decisions for I/O requests. The main idea behind the design of VIOS is to allocate conflict write requests to faster blocks so as to reduce access conflict latency of waiting requests. To achieve this, our scheduler organizes the blocks of each chip in a red-black tree according to their detected write speeds and maintains a global chip-state vector, where the current number of requests for each chip is recorded, so as to identify conflict requests.

Block Management

After detecting the proper write speed for each block at its current worn out state by periodically reading out the written data to find out the number of faulty bits, it is important to manage blocks with different write speeds for VIOS to easily schedule requests to appropriate blocks. In VIOS, the red-black tree structure is adopted as the main data structure to sort its blocks in detected speed order. Since the advance command support required by the die and plane level parallelism is not widely supported by most of SSDs and the relatively higher chip-level conflicts are the major contributors to access latency, the blocks of each chip are associated with a red-black tree respectively. Figure 2 shows the main data structures associated with VIOS. Once all the pages of a block have been programmed, it will be set as an invalid node in the red-black tree. When the prepared empty blocks are used up, a time-consuming task called Garbage Collection (GC) is triggered to reclaim stale pages for free write space and then the states of erased blocks become valid again. The blocks are evicted and inserted into another place of the red-black tree only when the write speed detection process is triggered and its ∆V p is decreased, corresponding to reduced write speed.

Global Chip-state Vector

To build a scheduling algorithm that can identify conflicts and exploit the speed variation based on the degree of conflicts, we propose a global chip-state vector to track the current number of requests for each chip. The global chip-state vector mainly depends on the location of data, which is determined by different data allocation schemes and the logical sector number (LSN) of I/O requests. Lets take an SSD where the number of chips is ChipNum and the size of each page is PageSize as an example. For a given static allocation scheme where the priority order of parallelism is channel-level parallelism first, followed by the chip-level parallelism [START_REF] Hu | Performance impact and interplay of SSD parallelism through advanced commands, allocation strategy and data granularity[END_REF], the assemblage of chips accessed by request r can be defined as:

A r = µ|µ = lsn(r)+λ * SectorSize PageSize %ChipNum where 0 ≤ λ < len(r) (1)
Where lsn(r) and len(r) are the accessed logical sector number and data size in sectors of request r respectively, while SectorSize is the sector size in bytes.

For a global chip-state vector defined as (NR 0 , NR 1 , ... , NR i ) where NR i is the current number of requests for chip i, when pushing arrived requests into the queue or issuing chosen requests to SSDs, the NR of each chip accessed by requests is updated as follows:

NR i = NR i + 1 arriving NR i -1 issued , i ∈ A r (2)

Conflict Optimized Scheduling Mechanism

Next, we propose the conflict optimized scheduling technique, which aims to reduce access conflict latency by exploiting the rich parallelism within SSDs and the speed variation among blocks. It consists of two components: 1) a hierarchical-batch structured queue to avoid conflicts from chip to channel. 2) a variation-aware block allocation technique that assigns conflict write requests to faster blocks to reduce access conflict of waiting requests.

Hierarchical-batch Structured Queue Since there are four main levels of parallelism which can be exploited to accelerate the read/write bandwidth of SSDs, the conflicts can also be classified into four types based on the physical resources contended by arrived requests. Among them, channel conflicts and chip conflicts are taken into account for the reason that the advance command support required by the die and plane level parallelism is not widely supported by most of SSDs. In the hierarchical-batch structured queue, the requests are grouped Fig. 3. An example that shows VIOS conflict reduction with the hierarchical-batch structured queue into batches from bottom up based on the chip-level and channel-level conflict detection respectively. Requests in the same chip batch can be serviced in chiplevel parallel, while requests belong to the same channel batch can be executed in completely independent channel-level parallel. Each chip batch and channel batch use A chip and A channel respectively to track the assemblage of chips and channels accessed by all its requests. Each time when a new request r arrives, the detection of chip-level conflicts is enabled by repeated intersection operations of A chip with A r , whose resulting assemblage of conflict chips (A conf lict ) can be modeled as:

A conf lict = A chip ∩ A r (3)
Once a chip batch that has no conflict with r is found, which means A conf lict is empty, the request is added to the chip batch and A chip is updated. Otherwise, a new chip batch is created for the new request. After that, the detection of channel-level conflicts is performed in the same manner to further exploit channel-level parallelism of requests within the same chip batch. For example, after scheduling the first five requests into the hierarchical-batch structured queue shown in Figure 3, if one more request accessing chips {6, 7} arrives, it is found that there is no chip-level conflict between the new request and the first chip batch, where the new request is thus added and A chip is updated to {0, 1, 2, 4, 5, 6, 7}. Then each channel batch of the first chip batch is checked and the second channel batch where the new request has no channel-level conflict is chosen with A channel being updated to {0, 1, 2, 3}.

Variation-aware Block Allocation Motivated by the findings that speed variation among blocks can be easily detected, we propose a variation-aware block allocation algorithm to optimize the data transfer latency dynamically, which could naturally reduce the access conflict latency when conflicts can not be avoided anymore. Each time when a request is issued, the NR of each chip accessed by the request is checked and then updated. Since a request processing may access multiple chips in NAND flash memory, we scatter the request into separate sub-requests. Each sub-request is only able to gain access to one chip. The sub-request accessing the chip whose NR is more than 1 will be allocated to a faster block from the red-black tree of the chip. Otherwise, a slower block is chosen for the sub-request. Figure 4 shows the process of scheduling three conflict sub-requests when only three pages in three blocks with different speeds are empty. As the Figure 4(a) shows, the variation-aware block allocation algorithm assigns the first two sub-requests to currently faster blocks for the reason that one or more sub-requests are still waiting in the queue. The last sub-request is allocated to a slower block because no conflict sub-request is waiting at this moment. Assuming that the write latency of fast, medium and slow blocks are 150µs, 180µs, and 210µs respectively, the average request response time of the proposed algorithm is (150+330+540)/3 = 340 µs, while that of the normal algorithm (Figure 4(b)) which distributes blocks in order is (180+390+540)/3 = 370 µs. Therefore, by incorporating the awareness of inter-block variation into I/O scheduling, the access conflict latency of I/O requests is reduced significantly.

Overhead Analysis

The overheads of the proposed I/O scheduler are analyzed as follows. According to the detailed descriptions of components above, the implementation of VIOS needs to maintain hierarchical-batch structured queues in the I/O queue. Since the number of channels and chips in NAND flash memory is limited, all sets can be stored as binary words and the set-intersection/set-union operation can be performed as an O(1)-time bitwise-AND/OR operation. This storage overhead is negligible for an I/O queue. Furthermore, the complexity of adding an incoming I/O request into the hierarchical-batch structured queues is proportional to the sum of the number of chip batches and the number of channel batches, and it is less than the queue length of I/O scheduler, which also has negligible cost.

Experimental Results

To evaluate our proposed variation-aware I/O scheduler, we perform a series of trace driven simulations and analysis. We implement VIOS as well as baseline NOOP scheduling and state-of-the-art PIQ scheduling within an event-driven simulator named as SSDSim [START_REF] Hu | Performance impact and interplay of SSD parallelism through advanced commands, allocation strategy and data granularity[END_REF], which provides the detailed and accurate simulation of each level of parallelism. Note that write speed detection technique is implemented with all of the schedulers. We simulate a 128GB SSD with 8 channels, each of which is connected to 8 chips. For the flash micro-architecture configuration, each flash chip employs 2 dies, where each die contains 4 planes and each plane consists of 2048 blocks. Each flash block contains 64 pages with a page size of 2KB. All these settings are consistent with previous works [START_REF] Gao | Exploiting parallelism in i/o scheduling for access conflict minimization in flash-based solid state drives[END_REF]. Page mapping FTL is configured to maintain a full map of logical pages to physical ones and greedy garbage collection scheme is implemented.

The BER growth rate that follows Bounded Gaussian distribution is used to simulate the process variation of flash memory, where the mean µ and the standard deviation σ are set as 3.7×10 -4 and 9×10 -5 respectively [START_REF] Pan | Error rate-based wear-leveling for NAND flash memory at highly scaled technology nodes[END_REF]. The maximal possible write step size is set to 0.6 and the step of decreasing ∆V p is set to 0.03. We use 600µs as the 2bit/cell NAND flash memory program latency when ∆V p is 0.3, 20µs as memory sensing latency and 1.5ms as erase time. Four different wear-out stages corresponding to 15K, 12K, 9K and 6K P/E cycles are evaluated. We evaluate our design using real world workloads from MSR Cambridge traces [START_REF] Narayanan | Migrating server storage to SSDs: analysis of tradeoffs[END_REF] and the write-dominated Financial1 trace [21], where 500000 I/Os of each trace are used in accordance with previous work.

Performance Analysis of VIOS

Our experiments evaluate scheduling performance with read and write latency. Figure 5 shows the average read latency for NOOP, PIQ and VIOS tested under the P/E cycling of 12K. As can be observed, VIOS improves the average read latency by about 17.66% compared to NOOP, indicating that the hierarchicalbatch structured read queue helps VIOS exploit multilevel parallelism inside SSDs by resolving resource conflicts. However, the improvements in average read latency brought by VIOS are not significantly higher than those obtained when using PIQ. This is because the variation-aware block allocation technique of VIOS mainly serves write request, and read requests are always preferentially scheduled in both PIQ and VIOS without being affected by write performance improvement.

Figure 6 plots the simulation results on average write latency when different scheduling algorithms are used in the variation-induced SSDs. To facilitate the comparison, the average write latency is normalized against the case of using NOOP algorithm. The first thing to observe is that VIOS outperforms NOOP and PIQ with write latency reduction by 22.93% and by 7.71% on average, respectively. This is because both the hierarchical-batch structured write queue and the variation-aware block allocation algorithm reduce access conflict of write requests. However, the write performance improvements under different traces Fig. 7. A comparison of the write latency reduction relative to PIQ among four different wear-out stages vary greatly. For example, compared to PIQ, the greatest improvement made in the src trace is 17.17%, but the slightest improvement made in the mds trace is only 2.73%. This is due to the different percentages of requests enrolled in conflict -VIOS works for I/O intensive applications where more requests can be processed in parallel and optimized. Table I shows the percentages of conflicts collected under the P/E cycling of 12K with NOOP scheduler. One can also observe that the percentage of conflicts in src is 77.74%, which has an impact on improving efficiency of VIOS. In contrast, that of mds is 4.70%, indicating that fewer conflicts lead to slighter write performance improvement. Figure 7 gives a comparison of the write latency reduction relative to PIQ among four different wear-out stages. One can observe from these results that the write latency reduction is positive all the time, which means VIOS always outperforms PIQ under four different wear-out stages. Furthermore, VIOS improves write performance by 2.25%, 5.25%, 7.71% and 9.63% on average under the P/E cycling of 6K, 9K, 12K and 15K respectively. As can be observed, with the increased number of P/E cycling, the write performance improvement brought by VIOS gets greater. This is a very reasonable result since BER spread grows as flash memory cells gradually wear out with the P/E cycling, corresponding to more significant variation among blocks, which improves the efficiency of the variation-aware block allocation strategy in VIOS. Overall, these results clearly demonstrate the effectiveness of VIOS in reducing the write latency during the entire flash memory lifetime.

Sensitivity Analysis of VIOS

To measure the sensitivity of VIOS to the I/O intensity, we repeated our experiments by varying the number of chips and the baseline program latency. Either fewer chips or slower program speeds increase the probability of access conflict. Figure 8 plots the normalized average write latency for each trace under 64, 56, 48, 40 and 32 chips when using VIOS. From the plots, it can be seen that the write latency increases as the number of chips decreases. For most traces, varying the number of chips from 64 to 32 increases the write latency by less than 25%. However, for traces src and wdev, the increase in write latency is 59.48% and 36.09% respectively. By comparing the results with the percentages of write conflicts shown in Table I, it can be observed that the increment in average write latency is greater when the number of write conflicts is larger. For example, the write latency of src that has most write conflicts (360549) is increased with maximum rate (59.48%), while these of mds, ts and usr which have fewer write conflicts (12570, 7161 and 9068) are increased with minimum rate (6.05%, 5.29% and 4.91%). On one hand, the number of conflicts is proportional to the quotient of access density and the number of chips, which means that more conflicts occur when reducing chips for traces with more intensive I/O. On the other hand, the average write latency is proportional to the square of the number of write conflicts, amplifying the effect of each new conflict. Figure 9 plots the impact of the baseline program latency on the write latency reduction relative to PIQ. The x-axis is the baseline program latency for ∆V p =0.3, varying from 200µs to 550µs. The number of conflict requests increases as the program latency is delayed, thus improving the benefit from hierarchicalbatch structured queues and variation-aware block allocation technique. However, the effect of program latency delay is greater than that of reduction in the number of chips. For example, from 200µs to 550µs, the write latency reduction for rsrch varies from 4.83% to 10.85%, compared to a slighter variation from 10.92% to 13.63% as the number of chips varies from 64 to 32. The major reason is that delaying program latency not only increases the number of conflict requests, but also amplifies the access conflict latency, which is the dominant factor for slow write operations.

Conclusion

In this paper, we propose a variation-aware I/O scheduler (VIOS) for NAND flash-based storage systems. The process variation is exploited to reduce the access conflict latency of SSDs when conflicts are unavoidable anymore. VIOS organizes the blocks of each chip in a red-black tree according to their detected write speeds and allocate conflict write requests to faster blocks to exploit interblock speed variation. In addition, the hierarchical-batch structured queue that focuses on the exploration of the parallelism of SSDs is presented. Furthermore, with diverse system configurations such as wear-out stages, the number of chips and the baseline program latency, VIOS reduces write latency significantly compared to the state-of-the-art NOOP and PIQ while attaining high read efficiency.

Fig. 1 .

 1 Fig. 1. SSD hardware diagram

Fig. 2 .

 2 Fig. 2. Organizational view of the VIOS scheduler

Fig. 4 .

 4 Fig. 4. Block allocation process. Program speed represented by Slow (S), Medium (M) and Fast (F).

NFig. 5 .NFig. 6 .

 56 Fig. 5. Average read latencies for three different types of schedulers (normalized to the NOOP scheduler)

Fig. 8 .Fig. 9 .

 89 Fig.8. Average write latencies for five different numbers of chips when using VIOS (normalized to 32 chips)

Table 1 .

 1 Characteristics of used workloads T races ReadI/O W riteI/O ReadConf licts W riteConf licts Conf lictsRatio

	prn	61422	438578	37678	261787	59.89
	fin	129342 370658	12135	129379	28.30
	hm	139527 360473	54387	168864	44.65
	mds	26301	473699	10947	12570	4.70
	proj	151549 348451	38615	32852	14.29
	rsrch 43803	456197	19413	217828	47.45
	src	81377	418623	28146	360549	77.74
	stg	43818	456182	21657	210355	46.40
	ts	76687	423313	27566	7161	6.95
	usr	206983 293017	91391	9068	20.09
	wdev 102663 397337	48986	170202	43.84
	web	239458 260542	89753	19184	21.79

Acknowledgment

The authors would like to thank the anonymous reviewers for their detailed and thoughtful feedback which improved the quality of this paper significantly. This work was supported in part by the National Natural Science Foundation of China under grant NO.91330117, the National High-tech R&D Program of China (863 Program) under grant No.2014AA01A302, the Shaanxi Social Development of Science and Technology Research Project under grant No. 2016SF-428, the Shenzhen Scientific Plan under grant No.JCYJ20130401095947230 and No.JSGG20140519141854753.


Zhaoyang Wang

Beihong Jin

Fusang Zhang

Ruiyang Yang

Qiang Ji

Discovering Trip Patterns from Incomplete Passenger Trajectories for Inter-zonal Bus Line Planning

Collecting the trajectories occurring in the city and mining the patterns implied in the trajectories can support the ITS (Intelligent Transportation System) applications and foster the development of smart cities. For improving the operations of inter-zonal buses in the cities, we define a new trip pattern, i.e., frequent bus passenger trip patterns for bus lines (FBPT4BL patterns in short). We utilize the passenger trajectories from bus smart card data and propose a two-phase approach to mine FBPT4BL patterns and then recommend inter-zonal bus lines. We conduct extensive experiments on the real data from the Beijing Public Transport Group. By comparing the experimental results with the actual operation of inter-zonal buses at the Beijing Public Transport Group, we verify the validity of our proposed method.

Introduction

With the popularity of smart devices and wireless networks, a large number of digital trajectories in everyday life from different objects (such as persons or vehicles) can be collected. Mining these trajectories gives us the opportunities to discover new knowledge or create new value.

Trip patterns are a kind of frequent sequence pattern. They can be loosely defined as a class of frequently-occurring trajectories that appear in the same spatial positions at the same periods. In real life, trip patterns can be found almost everywhere. For example, a student's behaviors in a university often follow some pattern: he or she often moves in the morning from the dormitory to the classroom, and then gets to the canteen; in the afternoon departs for the playground from the library and then heads for the canteen. Similarly, tourists often follow one of several kinds of travelling routes. As we know, office workers often take the buses of the same line to go to their companies or go home during the weekdays. The vehicles in logistics companies often deliver the goods together. Their trajectories also contain the trip patterns. Further, discovering trip patterns is a constituent part of many applications, which include transportation planning, logistics optimization, friend recommendation, etc.

We note that while mining the trip patterns, the key step is to determine whether a trajectory contains a trip pattern. A variety of criteria can be made, depending on the definition of inclusion relation of the spatial and temporal attributes. However, the inclusion relation on these two dimensions will be completely different in various applications. It leads to the high diversity and complexity in mining trip patterns. Meanwhile, these trajectory data that have been obtained may suffer the problem of incomplete information. For example, the data from bus smart cards which are a specific kind of public transportation card, only recording the bus trajectories, belong to incomplete trajectories. Because we only know the boarding and disembarking times of these trajectories, and do not know the exact times that the passengers pass the intermediate bus stations along the trajectories.

At present, the data from bus smart cards are often used to analyze travel behaviors of individuals or crowds. As far as we know, they have not been used for inter-zonal bus planning and real-time bus scheduling. We think that the data from bus smart cards reflect the public`s travel needs and they are an important basis for bus scheduling. Because of this, this paper attempts to mine a specific trip pattern from the data of bus smart cards and then suggests some inter-zonal bus lines.

The main contribution of this paper is that we propose a solution which utilizes the data of public smart cards for planning inter-zonal buses. In the proposed solution, we first distinguish the commuters by clustering bus passengers. Then, we mine frequent bus passenger trip patterns for bus lines (FBPT4BL patterns in short) and determine some inter-zonal bus lines. We also conduct extensive experiments based on the public smart card data from the Beijing Public Transport Group. By comparing the experimental results with the actual operation of inter-zonal bus at the Beijing Public Transport Group, we verify the validity of our proposed method.

The rest of this paper is organized as follows. First, we review the related work in Section 2. Then, we define the problem formally in Section 3. Next, we describe the process of mining FBPT4BL patterns from the public smart card data in Section 4. In Section 5, we give the experimental evaluation with real data as input. Finally, we conclude our paper in Section 6.

Related Work

We first review the previous methods of mining trip patterns. Next, we investigate the existing work on public transportation card data. Finally, we discuss the ways of optimizing bus lines and public transport scheduling with different data sources.

Trip Pattern Mining

A trip pattern denotes in essence a frequent path. The kernel issue in mining trip patterns is how to organize and search the trajectory information in an effective and efficient way [START_REF] Luo | Finding time period-based most frequent path in big trajectory data[END_REF] [START_REF] Lee | Mining frequent trajectory patterns in spatial-temporal databases[END_REF]. For example, [START_REF] Luo | Finding time period-based most frequent path in big trajectory data[END_REF] adopts a sequence instead of a single scalar to describe the frequency of a path so as to avoid the influences of infrequent edges and the number of constituent edges of a path, and construct the footmark graph and the corresponding footmark indexes. Next, [START_REF] Luo | Finding time period-based most frequent path in big trajectory data[END_REF] proposes a dynamic programming algorithm for path selection and applies an improved Bellman-Ford algorithm for mining frequent paths.

On the other hand, different application requirements derive new variants of trip patterns [START_REF] Fosca | Trajectory Pattern Mining[END_REF][START_REF] Kai | On discovery of gathering patterns from trajectories[END_REF][START_REF] Li | Swarm: Mining Relaxed Temporal Moving Object Clusters[END_REF]. For example, the T pattern is proposed in [START_REF] Fosca | Trajectory Pattern Mining[END_REF] for obtaining the classification of persons. Moreover, [START_REF] Fosca | Trajectory Pattern Mining[END_REF] adopts a density-based clustering method to mine ROIs (Regions-of-Interest) from history trajectories, then mines T patterns in an incremental way from ROI sequences, and finally obtains the classification of persons on the basis of T patterns. For another example, the gathering pattern is proposed in [START_REF] Kai | On discovery of gathering patterns from trajectories[END_REF] whose goal is to identify various group events, such as celebrations, parades, protests, traffic jams and so on. In [START_REF] Kai | On discovery of gathering patterns from trajectories[END_REF], objects' trajectories are clustered into several crowds. Next, the Hausdorff distance is used for measuring the distance between crowds, and neighboring crowds comprise the group. And then, the lower bounds for the number of crowds in one group and the number of moving objects appearing in a group are given for mining gathering patterns.

Smart Card Data Analysis

The existing work on smart card data mainly includes the analyses of individual travel behaviors and collective behaviors.

As an example of mining individual behaviors, [START_REF] Dou | Predicting Passengers in Public Transportation Using Smart Card Data[END_REF] adopts the bag-of-words model to build a passenger profile by his or her trip information in the smart card data, and employs the hierarchical clustering to get groups of passengers. [START_REF] Dou | Predicting Passengers in Public Transportation Using Smart Card Data[END_REF] uses the results of clustering as input of a three-layer back-propagation neural network to generate the predictions. The results show that passengers have their inner mobility patterns and usually hold the same patterns as the ones in the same group. However, for mining the patterns implied in the collective behaviors, the starting point is in general to classify the passengers according to the smart card data. [START_REF] Cui | Perspectives on Stability and Mobility of Passenger's Travel Behavior through Smart Card Data[END_REF] divides passengers into two groups: extreme travelers and non-extreme travelers, and then employs different methods to analyze the mobility and stability of two kinds of travelers. [START_REF] Cui | Perspectives on Stability and Mobility of Passenger's Travel Behavior through Smart Card Data[END_REF] concludes that the stability of extreme traveler's travel pattern cannot last for a long time and the non-extreme shows high regularity. [START_REF] Le | Passenger Segmentation Using Smart Card Data[END_REF] classifies passengers into four types and then conducts the statistical analyses for each passenger type.

Bus Line Planning and Scheduling

Planning bus lines and scheduling buses on the basis of big data is an emerging topic in intelligent transportation systems.

[9] utilizes smart card data and GPS data of buses to calculate the passenger density of a bus service, so as to verify the validity of time arrangements and assess the selections of bus scheduling schemes. [START_REF] Zuo | Vehicle Scheduling of an Urban Bus Line via an Improved Multiobjective Genetic Algorithm[END_REF] focuses on performing the bus scheduling of urban bus lines and proposes an improved multi-objective genetic algorithm and obtains multiple Pareto solutions. In order to meet individual travel needs, [START_REF] Favyen | A greener Transportation Mode: Flexible Routes Discovery from GPS Trajectory Data[END_REF] proposes a flexible mini-shuttle like transportation system called flexi, to establish a flexible bus scheduling by exploring the taxi trajectories. The authors first adopt a hierarchical clustering algorithm to get the frequent taxi trajectory clustering, named hot line. Then, they construct a directed acyclic graph of hot lines, and mine bus lines and bus schedule strategies depending on the connectivity between hot lines.

Compared with the existing work, our work has a different goal, that is, inter-zonal bus line planning. For this goal, we propose a new variant of the trip pattern named the FBPT4BL pattern, and design a two-phase appraoch to mining this pattern from the smart card data.

Problem Definition

Generally, a trajectory of an object refers to a sequence of time-stamped locations, representing the traces collected by some mobile wireless devices. As far as a bus trip is concerned, the following information can be obtained from bus smart card data, i.e., the bus card ID, the bus ID, the bus line ID, the boarding time of a passenger, the disembarking time of a passenger, the GPS data of the boarding station, and the GPS data of the disembarking station. These data reflect the spatio-temporal characteristics of the boarding and disembarking behaviors. With the aid of bus line details, the station information which a bus passenger passes can be supplemented, but the times of reaching these passing stations are still unknown. So the trajectories from smart card data are incomplete ones.

For clearly defining the problem to be solved, the concepts below are given at first. Definition 1 (Bus Trajectory): A bus trajectory is a pair (T, A) = <(b0, t0), b1, …, (bn, t1)>. Here, T denotes a sequential sequence of bus stations, that is, T=<b0, b1, …, bn>, where b0 stands for the boarding station, bn is the disembarking station, and the rest are the stations a passenger passes through. However, A=[t0, t1], where t0 and t1 stand for the boarding and disembarking times, respectively. Definition 2 (Bus Passenger Trip pattern, BPT pattern): A trip pattern, called BPT pattern, is a pair ( , ) P  , where  denotes a sequential sequence of bus stations which a bus trajectory, in whole or part, passes through, and  is the time interval that P goes through.

For deciding whether a trajectory is included in a BPT pattern, we have to define a binary relation between a trajectory and a BPT pattern. Definition 3 (the inclusion between a bus trajectory and a BPT pattern,  ): for any bus trajectory 0 0 1 1 ( , ( , ), ,...,( , )

m T A b t b b t   )
and a BPT pattern ( , ) P  , where In the paper, we explore bus smart card data to discover the commuters and mine one kind of specific frequent BPT pattern, named FBPT4BL patterns: i.e., frequent BPT patterns for bus lines. Now, we give the definition of mining FBPT4BL patterns. Definition 5 (Frequent Bus Passenger Trip pattern for Bus Lines, FBPT4BL pattern): Given the bus trajectory set of commuters Dcommuter, the minimum busload threshold between adjacent stations psmin, the minimum trip length r, and the time interval interzonal 

, mining a FBPT4BL pattern is to find a BPT pattern ( , ) commuter P  in interzonal  whose trip length is longer than r and score is higher than psmin. That is, for any BPT pattern (

ITFQ P count T A T A D T A P      (2)
where ITFQ denotes the busload of ( , ) commuter P  .

Mining Frequent Trip Patterns for Inter-Zonal Bus Lines

In this section, we propose an approach to mining commuter-based frequent trip pattern (the MCFTP approach in short) for recommending inter-zonal bus lines. The MCFTP approach consists of two phases: commuter recognition and inter-zonal bus mining. In the first phase, the DBSCAN algorithm is applied for passenger classification. In the second phase, with the support of a forest structure, an incremental data mining algorithm is designed for mining FBPT4BL patterns from the commuter trajectories. As a result, top-k inter-zonal bus lines can be obtained.

Mining Commuters

For the perspective of bus line planning, inter-zonal bus lines should satisfy the travel needs from commuters. Thus, we employ the DBSCAN algorithm and identify commuters by clustering the trajectories on spatial and temporal features. In spatial aspect, we cluster on boarding and disembarking stations respectively to discover frequent OD (Origin-Destination) pairs and then find frequent trajectories. In temporal aspect, we also use the density clustering algorithm DBSCAN to get the habitual time feature.

Mining Frequent OD Pairs

For mining a passenger's frequent boarding stations, we adopt the DBSCAN algorithm to cluster for each bus station in geographical position. Let () Neib i  represent the collection of neighbor stations of station i, that is,

( ) { ' | ( ', ) } Neib i i dis i i   
, where  is the upper bound on distance and dis(•) is the Euclidean distance. Let MinPts be the lower bound on the number of neighbors. The following four steps describe how to cluster.

Step 1: for a station i in the collection of boarding stations, if i has not been marked (which means that i is not marked as "processed" or "noise"), then check its neighborhood

. If | ( ) | Neib i MinPts  
, then create a new cluster h, add i into h, and add all its neighbors to the candidate set N.

Step 2: for the neighborhood of station i' that has not been marked in N, if

| ( ') | Neib i MinPts  
, then add ( ') Neib i  into N, add i' into h, and mark i' as "processed", else mark i' as "noise".

Step 3: repeat Step 2, until all stations in N have been processed.

Step 4: repeat Step 1 to Step 3, until each station has been marked.

Note that the clustering steps in this paper are a bit different from the ones in the original DBSCAN algorithm. Now, these isolated points in the result of clustering are not noise. Each isolated point indicates that only one bus station is found nearby. Thus, it should form a distinct cluster. We store the clustering attributes of each boarding station in Hboarding.

For a passenger p, by matching all boarding stations of smart card records with Hboarding, we can get arrival times for each cluster. Finally, the high frequency clustering is supposed to be frequent boarding stations, and the others are general boarding stations.

While mining frequent disembarking stations, we also employ the DBSCAN algorithm. The specific mining steps are the same as the ones in mining boarding stations. We store all clustering attributes of disembarking stations in Hdisembarking. Then, by matching all disembarking stations in smart card records with Hdisembarking, we can get frequent disembarking stations.

For a passenger p, if the boarding station (O) and the disembarking station (D) of a record belong to different high frequency clustering respectively, then this record is a frequent OD record. If the proportion of the frequent OD records in p's records (denoted as ,

p OD  ) is greater than 50% (which is , 50% p OD   ),
then p is frequent in terms of OD. Fig. 1 shows the result of mining frequent OD pairs for a passenger. The yellow bubbles represent the results of clustering of frequent boarding stations. And the purple bubbles represent the results of clustering of frequent disembarking stations. The number in each bubble is the frequency of boarding or disembarking for a passenger. If the frequency in a bubble is more than 6, then the station is regarded as a frequent boarding station or disembarking station. Following this rule, clusters BC2 and DC2 Fig. 1. The result of mining frequent OD pairs. are frequent stations, while BC1 and DC1 are normal ones. So only (BC2, DC2) is a frequent OD pair. From Fig. 1, we know that the proportion of frequent trajectories is greater than 50% (10/15=67%), so this passenger is frequent in terms of OD pairs.

Mining the Habit of Travel Time

For a passenger p, if he or she takes buses within a certain time interval frequently, this time interval is referred to as the habit of travel time for p. Once again, we adopt the DBSCAN algorithm to cluster the boarding times of p in the bus smart card records for getting all the habits of travel time of p. In particular, the object i in the DBSCAN algorithm corresponds to the boarding time. The distance between objects corresponds to the time interval expressed in milliseconds. MinPts is the lower bound on i's neighbors. The resultant clusters signify frequent times, and isolated points signify noise. If the proportion of p's records with frequent times in all p's records (denoted as , p Habitual



) is greater than 50%, then we say that p has habitual time.

Recognizing Commuters

Having the above clustering analysis results, we can further make passenger classification. First, different kinds of passengers are defined as follows:

 OD passengers: the passengers are frequent in terms of OD pairs, but have no habitual time.  Habitual time passengers: the passengers have habitual times, but are infrequent in terms of OD pairs.  Commuters: the passengers are both frequent in spatial and temporal aspects.  Casual passengers: they have none in spatio-temporal features.

Next, for each passenger p, the following rules are given to distinguish commuters:

 

, p is a commuter.

Mining FBPT4BL Patterns

For reducing the overheads of trajectory retrieval, we design a forest structure which can organize trajectories with the same boarding station into a tree.

Establishing a Tree Structure

Each tree in the forest is used to store the trajectories with the same boarding station. Specifically, the same boarding station is stored in the root node, the disembarking station and these stations which passengers pass through are stored in the children nodes. Each node stores a triple, i.e., (item, count, children), where item stores the name of current station; count is the number of commuters' trips whose boarding station is the root node of this tree and the disembarking station is current node; and children contains the children of this node which are stored in a hash table.

Creating a Forest

The forest is established by these trees above and stored in a hash table. For a trajectory that has not been visited, if the tree whose root node is the boarding station of the trajectory does not exist, then we create the tree, otherwise we search the tree for the branch that matches with the trajectory. If the matched branch exists, then we increment count, where the count belongs to the node that matches with the disembarking station. Otherwise, we create a new branch and set count of the leaf node to 1.

Executing FBPT4BL patterns mining

The mining steps in the form of the pseudo code are shown in Fig. 2.

Input

Fig. 2. Mining FBPT4BL patterns

Step 1: traverse the tree in a depth-first order. Let c be the current visiting node. If c.count > 0, then mark the branch from root node to c as a BPT pattern tpc, and store tpc into a set of BPT pattern TP.

Step 2: let pc be the father node of c. If BPT pattern tppc exists in TP, then set tpc.ITFQ to tppc.ITFQ. Then, for each node o in tppc, find the tree whose root node is o, search for the branch that matches with the sub-trip in tpc from o to c, and add the count of end node in the matched branch to tpc.ITFQ, and then get to Step 5. If tppc is not in TP, then continue Step 3.

Step 3: sum all count values in tpc to tpc.ITFQ.

Step 4: delete the first node of tpc to get the new pattern tpc'. If tpc' is empty, then continue Step 5, else match tpc' against the forest. If the matched branch is found, then turn to Step 3. If not, then turn to Step 4. Here, the meaning of match is to get a branch whose root node is the first node of tpc', and each node of the branch is the same as the bus station in tpc' in order.

Step 5: select BPT patterns in TP whose lengths are larger than r, and compute the commuters' score values of these patterns by Eq. 1. Then, sort the selected patterns by score to get top-k results which are the trips of BPT4BL patterns. By matching these trips to bus lines, the inter-zonal bus lines and bus intervals can be gotten.

Time Complexity Analysis

Let w be the number of bus stations, g be the number of commuters, and u be the trajectory number. The analysis of the MCFTP approach consists of three parts: commuter mining, forest creation, and FBPT4BL pattern mining.

In the commuter mining part, since the DBSCAN algorithm has the complexity of O(w•logw), the complexity of mining frequent ODs is O(2g•u), and the complexity of mining habitual time is O(g•ulogu), the total complexity is O(w•logw+2g•u+g•ulogu).

In the second part, creating a forest needs to traverse all trajectories, which will make the complexity of this process O(u•w).

In the third part, we use an incremental method to mine FBPT4BL patterns. A new BPT pattern's ITFQ is calculated by the existing pattern's IFTQ via a traverse from the root node to its father node. From Step 2, we see that the complexity is 1+2+3+…+d=O(d 2 ), where d is the station number in a branch. Let e be the number of leaf nodes in the forest. The complexity of mining process is O(d 2 •e). Considering that each branch in a tree is a sub-trajectory of passengers and the total station number of one bus line in Beijing is no more than 50, which means that the maximum length of branches cannot be larger than 50, the complexity of mining process is O(2500•e).

Evaluation

In order to show availability of the MCFTP approach, we need to fix following questions:

 How do we set the distance upper bound  and the minimum number of neighbors MinPts in the commuter identification phase?  Does only commuter data result in better experimental results than all passengers or other types of passengers?  Does the MCFTP approach is appropriate to a real-time bus scheduling?

To answer the above questions, we first conduct experiments to analyze the sensitivities of  and MinPts. Then we evaluate effectiveness and efficiency of the MCFTP approach. In experiments, we use the real data from Beijing Public Transport Group, including 6,507,837 passengers and 48,427,884 items of bus smart card data from Aug. 3, 2015 to Aug. 9, 2015, as well as 5,622 bus stations and 707 bus lines.

Sensitivity Analysis of MinPts and ɛ

The application of the DBSCAN algorithm requires two important parameters: the distance upper bound ɛ and the minimum number of neighbors MinPts.

While the DBSCAN algorithm is applied to clustering by the spatial information, ɛ denotes the upper bound of spatial distance. A small ɛ may result in a big error since some stations which belong to the same destination may be clustered into different classes, whereas a too large ɛ also performs poorly since the stations falling into different destinations may be clustered into one class.

In Beijing, the distance between neighbor bus stations ranges from 500m to 1200m. Considering that an acceptable walking distance is 1000m or so, we increase ɛ from 500m to 1000m to evaluate clustering results. However, MinPts is used to set a regular cluster density. In the downtown, bus stations within ɛ should not be very congested. Thus, in experiments, we increase MinPts from 1 to 10.

While the DBSCAN algorithm is applied to temporal information, ɛ denotes the upper bound of the temporal distance. ɛ is set to 20 minutes, since in general commuters will arrive at stations at a relatively fixed time points, varying within a very narrow interval. MinPts is set to 3. That means a passenger is regarded as frequent in temporal aspect if the passenger takes a bus at same station at least three times one week. Fig. 3 shows percentages of commuters under different ɛ and MinPts (in spatial clusters). From Fig. 3, we can see that for the same ɛ, commuter number decreases with the increase of MinPts. It is because a large MinPts will generate a large number of clusters and those trips which should be in a same cluster will be departed into different clusters. In particular, we find when setting ɛ to 500 or 600 and MinPts to a value greater than 5, the percentages of commuters will be less than 5%, which cannot be true in Beijing. We deem that the percentages of commuters ranging from 20% to 35% is rational, so we set ɛ to 600 and MinPts to 4 for the experiments in Section 5.2.

Effective and Efficient Analysis of MCFTP Approach

We collect the real inter-zonal bus lines in Beijing as the ground truth. So far, about 3,851 inter-zonal bus lines have been operated, covering 282 bus lines. In experiments, we set r to 15, and then run our MCFTP approach using the smart card data of different days as input. We choose different percentages (denoted as γ, from 1% to 20%) of recommended inter-zonal bus lines as the results of our MCFTP approach, and calculate the matching ratio of our results to the ground truth. We also employ the methods in Section 4.2 to mine FBPT4BL patterns from all passengers, OD passengers and habitual time passengers. The corresponding methods are called the AP based method, the OD based method and the HTP based method, respectively. The results are showed in Fig. 4. From Fig. 4, we can see that the MCFTP approach performs better than other three methods. The highest matching ratio of our approach is 62%, and the lowest matching ratio is 51%. For the data on Aug. 7, our MCFTP approach is 28% higher than the OD based method, 18% higher than the HTP based method, and 18% higher than the AP based method while γ is set to 1%. On average, the HTP based method is mostly close to our method. The reason behind is that these habitual time passengers have regular boarding habits and interzonal bus lines in morning rush hours can greatly benefit these passengers.

We find that the OD based method performs worst in four methods. However, from the above experiments, we know that the sum of all passengers is 6,507,837. Among them, the number of OD passengers is 4,661,267, the number of habitual time passengers is 243,370, and the number of commuters is 1,536,927. OD passenger's number is about 3 times of commuter's number. That means that the inter-zonal bus lines planning should rely on the contributory passenger factor instead of passenger number. As regard to the time complexity, for the data of one day, we need 65s to build the forest and 5.852s to mine inter-zonal bus lines. Our method has the low time complexity, and can be used for scheduling inter-zonal buses in real-time.

Conclusion

In the paper, we focus on mining patterns in the trajectories. We propose a two-phase approach to mine FBPT4BL patterns from the bus smart card data and obtain interzonal bus lines. The resulting inter-zonal bus lines can be used for evaluating the rationality of existing inter-zonal bus lines or guiding the opening of inter-zonal bus lines.

Definition 4 (

 4 Frequent Bus Passenger Trip pattern, FBPT pattern): Given a bus trajectory set D, the minimum support threshold smin, and the time interval interval  , mining a FBPT pattern is to find a BPT pattern( , ) P  that includes at least smin trajectories and whose  is within interval  . That is, for any BPT pattern ( , ) P  , such that within interval  . Note that in Definition 4, different supportD ((P,τ)) will lead to the different definitions of the frequent trip pattern.

Fig. 3 .

 3 Fig. 3. The percentages of commuters.

Fig. 4 .

 4 Fig. 4. The experiment results of inter-zonal bus recommendation.

Acknowledgments. This work is supported by the National Natural Science Foundation of China under Grant No. 61472408.


Xiangshan Sun

Zhiping Jia

Mengying Zhao

Zhiyong Zhang

Multipath Load Balancing In SDN/OSPF Hybrid Network

Software defined network (SDN) is an emerging network architecture that has drawn the attention of academics and industry in recent years. Affected by investment protection, risk control and other factors, the full deployment of SDN will not be finished in the short term, thus it results into a coexistence state of traditional IP network and SDN which is named hybrid SDN. In this paper, we formulate the SDN controller's optimization problem for load balancing as a mathematical model. Then we propose a routing algorithm Dijkstra-Repeat in SDN nodes which can offer disjoint multipath routing. To make it computationally feasible for large scale networks, we develop a new Fast Fully Polynomial Time Approximation Schemes (FPTAS) based Lazy Routing Update (LRU).

Introduction

Load balancing is a key technique for improving the performance and scalability of the Internet. It aims to distribute traffic so as to optimize some performance criteria. Load balancing using OSPF may cause network congestion as they are non-traffic-aware. The chief problem is that very often many comparable traffic flows are misled to converge on bottleneck links since these algorithms are oblivious to traffic characteristics and link loading.

SDN is an emerging innovator to the traditional networking paradigm, which unleashes a powerful new paradigm offering flow-level traffic control and programmable interfaces to network operators. However, fully deploying the SDN in the network is by no means an easy job. We may encounter economical, organizational and technical challenges [START_REF] Vissicchio | Opportunities and research challenges of hybrid software defined networks[END_REF]. As a result, a full deployment of SDN, i.e., all the router nodes support SDN and can be centrally controlled by the controllers, in the network will not work out in the short term. Thus a hybrid SDN deployment, i.e., SDN/OSPF hybrid network is a better choice. We adopt the hybrid architecture as the research background in this work. In a hybrid SDN, only the SDN nodes can be controlled by the centralized controller, while the legacy nodes still use the traditional shortest path routing protocol OSPF to forward packets. [START_REF] Agarwal | Traffic engineering in software defined networks[END_REF] is the first paper to address network performance issues in an incrementally deployed SDN network. It formulates the load balancing as a linear programming problem and refines a FPTAS algorithm to solve it. But [START_REF] Agarwal | Traffic engineering in software defined networks[END_REF] only uses a single shortest path to optimize the traffic passing through SDN nodes and the SDN controller must recompute the routing after forwarding one flow. The network performance is thus limited. We propose disjoint multipath calculation in SDN nodes. For the flows directed to the same destination, the SDN controller can map them to disjoint paths which could ensure that the flows do not aggregate until they reach the destination node. We also formulate the SDN controller's optimization problem for load balancing and develop a Lazy Routing Update (LRU) scheme for solving these problems, which belongs to Fast Fully Polynomial Time Approximation Schemes (FPTAS). LRU can decrease the routing calculation in the SDN controller. It does this by spreading traffic load across all feasible links in the network. In simpler terms it means placing traffic where the capacity exists.

Problem Formulation

Hybrid Network Scenario

In the SDN/OSPF hybrid network, a centralized SDN controller computes the forwarding table for a set of SDN nodes. The first packet of every flow passing through SDN nodes is sent to the SDN controller, and the following operations are done by the SDN controller. The rest of the nodes in the network run traditional network protocol OSPF and forward packets along the shortest paths. In addition to forwarding packets, the SDN nodes forward some traffic measurement information to the SDN controller. The controller uses these information along with information disseminated in the network by OSPF-TE to dynamically map the routing tables to the SDN nodes in order to change traffic conditions. Note that in OSPF-TE, the nodes also exchange available bandwidth information on the links in the network. Therefore the controller knows the current OSPF costs as well as the amount of traffic flow on each link (averaged over some time period). Figure 1 shows an example of hybrid network topology from [START_REF] Agarwal | Traffic engineering in software defined networks[END_REF]. Nodes 2, 9, 14 are SDN nodes and the rest nodes are legacy nodes. SDN nodes 2, 9, 14 are controlled externally. We will use this network to illustrate some of the concepts that we outline in the rest of the paper. We assume that all the links in the network are bidirectional and all links have the same OSPF cost. Each flow enters the network at its ingress node and has to visit a set of nodes before egressing the network at its egress node. The traffic that goes from source to destination without transiting through a SDN node will be referred to as uncontrollable traffic. If the source of a packet is a SDN node, or if it passes through at least one SDN node before it reaches its destination then the traffic will be called controllable traffic. In other words, controllable traffic comprises of packets that pass through at least one SDN node if the packets are routed using standard OSPF. There is at least an opportunity at the SDN nodes to manipulate the path of controllable traffic.

Optimization Problem Definition

Given a directed graph

( , ) G N E 

, where the N and E are set of n nodes and set of m edges, respectively, with each edge capacity retrievable from a function () ce . The background traffic () be on each link e is readily retrieved or estimated by the controller through the dynamic information disseminated by OSPF-TE [START_REF] Nascimento | Virtual routers as a service: the routeflow approach leveraging softwaredefined networks[END_REF].

()

ge
max  ( ) ( ), k pP f p d k k K       (1) ( ) ( ), k pP f p g e e E      (2) ( ) 0, f p p P    (3)
(1) denotes that the sum of flows on all paths in k P is greater than the demand of ingress-egress pairs. (2) enforces the edge capacity constraints which ensure that the total flow on the edge is less than the difference between the edge capacity () ce and the background traffic () be .

(3) ensures non-negative flow on each candidate path. The goal is to maximize the throughput  while not violating capacity constraints. If the optimal    then the current flow can be routed at the SDN nodes while ensuring that all edge utilizations are less than one.

We now associate dual variables () lewith each edge capacity constraint (2) and () zk for the demand constraint (1). It is interesting to note that its dual LP problem of the above can be shown to be

min ( ) ( ) eE l e g e   ( ) ( ), , eP l e z k k K p P        (1)
( ) ( ) 1 k z k d k   (2)
( ) 0, l e e E    (3) ( ) 0, z k k K    (4)
Note that this problem is a constrained version of the maximum concurrent flow problem, we can adapt the Fully Polynomial Time Approximation Scheme (FPTAS) developed for a generic maximum concurrent flow problem [START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF] to this case at SDN controller.

Load Balancing In Hybrid SDN Network

Disjoint Multipath Calculation

The proposed disjoint multipath scheme determines paths as follows. First, a path between nodes i and j is found as the shortest path by Dijkstra algorithm. The Dijkstra algorithm is then repeated after excluding network links used in the first shortest path to calculate the second shortest path. After that, Dijkstra algorithm is further repeated after excluding those network links used in the first or second shortest path. This process is repeated until no more paths are obtained. The algorithm of disjoint multipath calculation is named Dijkstra-Repeat in the following of this paper. Obviously, the Dijkstra-Repeat algorithm for computing the routing table for the SDN nodes could ensure that routing will be along loop-free shortest paths while minimizing the congestion in the network.

Forwarding is a method which maps incoming packets to outgoing links. The SDN nodes act basically as forwarding elements. If there are multiple next hops for a given destination, then the SDN nodes can split traffic to the destination in a pre-specified manner across the multiple next hops, subject to load balancing.

LRU: A new FPTAS algorithm

We assume that the traffic matrix and the topology of the network are steady for a short period. The locations and number of the SDN nodes can be fixed and determined based on greedy algorithms [START_REF] Agarwal | Traffic engineering in software defined networks[END_REF]. The  is defined as the same value in [2], which is a function of the desired accuracy level , the number of nodes n and the number of edges m .

The algorithm then operates iteratively. At the beginning of each cycle, the controller schedules controllable traffic with awareness of background traffic () be on each link by OSPF-TE, so as to optimize the overall load balancing. The dual weight of each edge

eE  is initialized to ( ) / ( ) l e g e 
, where () geis the remaining capacity of each edge. In each iteration, it first computes the multiple admissible paths ut P between SDN nodes u and other nodes t with Dijkstra-Repeat. For the primal problem, the algorithm forwards flow along the path p , while p is selected from ut P with hashing. The amount of flow () fusent along the path p is determined by the minimum remaining link capacity () ge on p and the controllable traffic demand () du between the two terminals of the path. As a result, the primal variable The algorithm follows in the similar vein as [START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF]. The correctness of the algorithm as well as the running time analysis is identical to the results in the paper and is therefore omitted. Actually, the computational complexity of the FPTAS algorithm is at most a polynomial function of the network size and 1/  [3]. Thus, the computational complexity of our approximation algorithm is also polynomial. There are however some key differences in the implementation of the algorithm. One key difference is that we use disjoint multipath while [START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF] uses a single shortest path. In fact, multipath routing can significantly reduce congestion in hot spots by distributing traffic to unused network resources instead of routing all the traffic on a single path. That is, multipath routing offers better load balancing and makes full utilization of network resources [START_REF] Dasgupta | Design of multi-path data routing algorithm based on network reliability[END_REF].

The other key difference is that our FPTAS algorithm is based on Lazy Routing Update. In each iteration, [START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF] has to compute the lightest admissible path from all SDN nodes to a given destination using path finding algorithm with the dual weights () le

(not OSPF costs). The most time consuming step in practical cases is the shortest path computation. In [START_REF] Garg | Faster and simpler algorithms for multicommodity flow and other fractional packing problems[END_REF], the SDN controller recomputes the shortest path after routing one flow, resulting in frequent updates on routers, which is a so time consuming process in each iteration of FPTAS algorithm that it doesn't fit in such an online routing algorithm. So in our scenario, at the beginning of each cycle, the controller calculates admissible paths set using Dijkstra-Repeat algorithm with the traffic information from OSPF-TE. And in a short period, the SDN controller maps the flows aggregated at SDN nodes to multiple admissible paths with hashing. This process of augmenting flow is repeated until the problem is dual feasible. We call that Lazy Routing Update (LRU), as shown in Algorithm for Load Balancing.

Experiments And Evaluation

In this section, we conduct the simulation experiments. We ran two groups of experiments to check the effectiveness of the algorithm using the following two topologies: (i) The Geant (Europe) topology from [5]. This topology has 22 nodes and 36 links; (ii) The Abilene topology from [5]. This topology has 12 nodes and 30 links. For Geant and Abilene topology, the link weights and the link capacities are given, and we can also get the traffic matrices of the two topologies from [5]. The number of SDN nodes for the two topologies are determined as 6 and 3, respectively. The location of the SDN nodes are decided by the incremental greedy approach stated in [START_REF] Agarwal | Traffic engineering in software defined networks[END_REF]. For Geant and Abilene topology, we carry out twenty experiments with twenty traffic matrices from [5] on each topology to compare with the maximum link utilization in OSPF, HSTE[11] and our LRU. We carry out the two groups of experiments to illustrate the practicality of our algorithm, as the two topologies used in the experiments are real and the traffic is actually measured. The results are shown in Figure 4 and Figure 5. As the figures illustrate, our algorithm LRU in the figures obtains a lower maximum link utilization compared with the other two algorithms. Compared with HSTE, LRU can reduce the overall maximum link utilization by 10% and 9% for Geant and Abilene topologies, respectively. Compared with OSPF, the reductions are 20% and 17%.

Conclusion

The SDN/OSPF hybrid network load balancing is a popular problem that raises people's attention worldwide. It deviates from the traditional load balancing scenario, where the flows are always routed along the shortest paths. The emerging of SDN provides a new method to solve the load balancing problem. It can centrally control the flows that directed to the outgoing links of the SDN nodes, which is similar with the model of multi-commodity. In this paper, we propose a new FPTAS algorithm LRU to solve the load balancing problems in SDN/OSPF hybrid network. Compared with other load balancing algorithms, the proposed algorithm reduces the SDN calculation and obtains a lower maximum link utilization. In the future work, we will carry out the experiments on the testbed and consider more hybrid SDN network types.

Fig. 1 .

 1 Fig.1. A hybrid network scenario Fig.2. Shortest Path Tree to Node 13

1 L

 1 is updated by () fu, respectively. After updating the primal variables, the algorithm continues to update the dual variables () le related to path p . The algorithm stops when ←δ/g(e),eϵE R ut ←0,uϵSN,tϵN while D L <1 do for each demand d(u) having the same destination tϵN P ut : admissible paths set with Dijkstra-Repeat while D L< 1 and d(u)>0 do select path p from P ut with hashing c=min eϵp g(e) f(u)=min{d(u),c},∀u Route f(u) flow from each u to t R ut =R ut +f(u) d(u)=d(u)-f(u) l(e)=l(e)(1+ωf(u)/c(e)) Recompute D L= Ʃ eϵE g(e)/l(e

Fig. 4 .

 4 Fig.4. Comparison of Maximum Link Utilization of Geant

Acknowledgments. This research is sponsored by the State Key Program of National Natural Science Foundation of China No. 61533011, Shandong Provincial Natural Science Foundation under Grant No. ZR2015FM001, the Fundamental Research Funds of Shandong University No.2015JC030.


Daxin Zhu

Tinran Wang

Xiaodong Wang

On determination of balance ratio for some tree structures

In this paper, we studies the problem to find the maximal number of red nodes of a kind of balanced binary search tree. We have presented a dynamic programming formula for computing r(n), the maximal number of red nodes of a red-black tree with n keys. The first dynamic programming algorithm uses O(n 2 log n) time and uses O(n log n) space. The basic algorithm is then improved to a more efficient O(n) time algorithm. The time complexity of the new algorithm is finally reduced to O(n) and the space is reduced to only O(log n).

Introduction

This paper studies the worst case balance ratio of the red-black tree structure. A redblack tree is a kind of self-balancing binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions. The data structure was originally presented by Rudolf Bayer in 1972 with its name 'symmetric binary B-tree' [START_REF] Bayer | Symmetric binary B-trees, Data structure and maintenance algorithms[END_REF]. Guibas and Sedgewick named the data structure red-black tree in 1978, [START_REF] Guibas | A dichromatic framework for balanced trees[END_REF]. They introduced the red/black color convention and the properties of a red-black tree at length. A simpler-to-code variant of red-black trees was presented in [START_REF] Andersson | Balanced search treesmade simple[END_REF][START_REF] Heejin | Parallel algorithms for redCblack trees[END_REF]. This variant of red-black trees was called the variant AAtrees [START_REF] Weiss | Data Structures and Problem Solving Using C++[END_REF]. The left-leaning red-black tree [START_REF] Sedgewick | Left-leaning RedCBlack Trees[END_REF] was introduced in 2008 by Sedgewick. It is a new version of red-black tree which eliminated a previously unspecified degree of freedom. Either 2-3 trees or 2-4 trees can also be made isometric to red-black trees for any sequence of operations [START_REF] Sedgewick | Left-leaning RedCBlack Trees[END_REF].

The basic properties and algorithms

A red-black tree of n keys is denoted by T in this paper. In a red-black tree T of n keys, r(n) and s(n), are defined as the maximal and the minimal number of red internal nodes respectively. It is readily seen that in this case of n = 2 k -1, the number of red nodes of T achieves its maximum, if the node from the bottom to the top are colored alternately red and black. the number of red nodes of T achieves its minimum, if the node from the bottom to the top are all colored black.

Corresponding author

In the special case of n = 2 k -1, we can conclude,

r(n) = r(2 k -1) = (k-1)/2 ∑ i=0 2 k-2i-1 = 2 k-1 (k-1)/2 ∑ i=0 1 4 i = 2 k-1 3 4 - 1 4 (k-1)/2 = 2 k+1 -2 k-1-2 (k-1)/2 3 = 2 k+1 -2 (k-1) mod 2 3 = 2 k+1 -2 + k mod 2 3 = 2(2 k -1) + k mod 2 3 = 2n + log(n + 1) mod 2 3
The number of black nodes b(n) can then be,

b(n) = n -r(n) = n - 2n + log(n + 1) mod 2 3 = n -log(n + 1) mod 2 3
Therefore, in this case, the ratio of red nodes to black nodes is,

r(n)/b(n) = 2n + log(n + 1) mod 2 n -log(n + 1) mod 2
In the general cases, the maximal number of red nodes of a red-black tree with n keys can be denoted by γ(n, 0) if root is red, and by γ(n, 1) if root is black. We then have, r(n) = max{γ(n, 0), γ(n, 1)}.

It can be proved by induction further that γ(n, 0) ≤ 2n+1 3 and γ(n, 1) ≤ 2n 3 . Therefore,

r(n) ≤ max 2n + 1 3 , 2n 3 = 2n + 1 3
Thus, for n ≥ 7, we have

0 ≤ r(n) n -r(n) ≤ 2n+1 3 n -2n+1 3 = 2n + 1 n -1 ≤ 2.5
In the general cases, the maximal number of red nodes of a subtree of black-height j and size i can be denoted by a(i, j, 0) if root is red and by a(i, j, 1) if root is black. It follows from 1 2 log n ≤ j ≤ 2 log n that

γ(n, k) = max 1 2 log n≤ j≤2 log n a(n, j, k) (1)
Furthermore, we can denote for any 1

≤ i ≤ n, 1 2 log i ≤ j ≤ 2 log i that                  α 1 (i, j) = max 0≤t≤i/2 {a(t, j, 1) + a(i -t -1, j, 1)} α 2 (i, j) = max 0≤t≤i/2 {a(t, j, 0) + a(i -t -1, j, 0)} α 3 (i, j) = max 0≤t≤i/2 {a(t, j, 1) + a(i -t -1, j, 0)} α 4 (i, j) = max 0≤t≤i/2 {a(t, j, 0) + a(i -t -1, j, 1)} (2)
Theorem 1 a(i, j, 0) and a(i, j, 1) can be formulated for each

1 ≤ i ≤ n, 1 2 log(i + 1) ≤ j ≤ 2 log(i + 1), as follows. a(i, j, 0) = 1 + α 1 (i, j) a(i, j, 1) = max{α 1 (i, j -1), α 2 (i, j -1), α 3 (i, j -1)} (3)
Proof. Let i, j be two indices such that 1 ≤ i ≤ n, 1 2 log(i+1) ≤ j ≤ 2 log(i+1). T (i, j, 0) is defined to be a red-black tree of i keys and black-height j, and its root red. T (i, j, 1) is defined similarly if its root black. The number of red nodes in T (i, j, 0) and T (i, j, 1) can be denoted respectively by a(i, j, 0) and a(i, j, 1).

(1) We consider T (i, j, 0) first. The two children of T (i, j, 0) must be black, since its root red. The two subtrees L and R must both have a black-height of j. The subtrees T (t, j, 1) and T (it -1, j, 1) which connected to a red node must be a red-black tree of black-height j and i keys. The number of red nodes is thus 1 + a(t, j, 1) + a(it -1, j, 1). T (i, j, 0) have a maximal number of red nodes, and thus,

a(i, j, 0) ≥ max 0≤t≤i/2 {1 + a(t, j, 1) + a(i -t -1, j, 1)} (4)
On the other hand, If the number of red nodes of L and R are denoted by r(L) and r(R), and the sizes of L and R are t and it -1, then we can conclude that r(L) ≤ a(t, j, 1) and r(R) ≤ a(it -1, j, 1). Therefore we have,

a(i, j, 0) ≤ 1 + max 0≤t≤i/2 {a(t, j, 1) + a(i -t -1, j, 1)} (5)
It follows from ( 4) and (5) that,

a(i, j, 0) = 1 + max 0≤t≤i/2 {a(t, j, 1) + a(i -t -1, j, 1)} (6)
(2) We now consider T (i, j, 1). The two subtrees L and R must both have a blackheights j -1.

If both L and R have a black root, then T (t, j -1, 1) and T (it -1, j -1, 1) must have black-height j and i keys. The number of red nodes must be a(t, j -1, 1) + a(it -1, j -1, 1). It follows that

a(i, j, 1) ≥ max 0≤t≤i/2 {a(t, j -1, 1) + a(i -t -1, j -1, 1)} = α 1 (i, j -1) (7)
The other three cases, can be discussed similarly.

a(i, j, 1) ≥ max 0≤t≤i/2 {a(t, j -1, 0) + a(i -t -1, j -1, 0)} = α 2 (i, j -1) (8)
a(i, j, 1) ≥ max 0≤t≤i/2 {a(t, j -1, 1) + a(i -t -1, j -1, 0)} = α 3 (i, j -1) (9)
a(i, j, 1) ≥ max 0≤t≤i/2 {a(t, j -1, 0) + a(i -t -1, j -1, 1)} = α 4 (i, j -1) (10)
Therefore, we can conclude, a(i, j, 1) ≥ max{α 1 (i, j -1), α 2 (i, j -1), α 3 (i, j -1), α 4 (i, j -1)} (11)

On the other hand, If the number of red nodes of L and R are denoted by r(L) and r(R), and the sizes of L and R are t and it -1, then we can conclude that r(L) ≤ a(t, j -1, 1) and r(R) ≤ a(it -1, j -1, 1). Therefore we have,

a(i, j, 1) ≤ max 0≤t≤i/2 {a(t, j -1, 1) + a(i -t -1, j -1, 1)} = α 1 (i, j -1) (12)
The other three cases can be discussed similarly that

a(i, j, 1) ≤ max 0≤t≤i/2 {a(t, j -1, 0) + a(i -t -1, j -1, 0)} = α 2 (i, j -1) (13)
a(i, j, 1) ≤ max 0≤t≤i/2 {a(t, j -1, 1) + a(it -1, j -1, 0)} = α 3 (i, j -1) ( 14)

a(i, j, 1) ≤ max 0≤t≤i/2 {a(t, j -1, 0) + a(i -t -1, j -1, 1)} = α 4 (i, j -1) (15)
It follows that a(i, j, 1) ≤ max{α 1 (i, j -1), α 2 (i, j -1), α 3 (i, j -1), α 4 (i, j -1)} (16)

It follows from ( 11) and ( 16) that

a(i, j, 1) = max{α 1 (i, j -1), α 2 (i, j -1), α 3 (i, j -1), α 4 (i, j -1)} (17)
It is clear that α 4 (i, j) achieves its maximum at t 0 α 4 (i, j) = a(t 0 , j, 0) + a(it 0 -1, j, 1), 0 ≤ t 0 ≤ i/2, then α 3 (i, j) achieves its maximum at 1 2 log(i + 1) ≤ j ≤ 2 log(i + 1), and finally we have,

t 1 = i -t 0 -1, α 3 (i, j) = a(t 1 , j, 1) + a(i -t 1 -1, j, 0), 0 ≤ t 1 ≤ i/2. Thus, α 3 (i, j) = α 4 (i, j), for each 1 ≤ i ≤ n,
a(i, j, 1) = max{α 1 (i, j -1), α 2 (i, j -1), α 3 (i, j -1)} ( 18
)
The proof is complete.

Some special pictures of the maximal red-black trees are listed in Fig. 2. It can be observed from these pictures of the maximal red-black trees that some properties of r(n) are useful.

(1) The maximal red-black tree with r(n) red nodes of n keys as shown above can be realized by a complete binary search tree.

(2) In the maximal red-black tree of n keys, the nodes along the left spine are colored red, black, • • • , alternatively from the bottom to the top. In such a red-black tree, its black-height must be 1 2 log n. The dynamic programming formula in Theorem 1 we can be improved further from above observations. The second loop for j can be reduced to j = 1 2 log i to 1 + 1 2 log i, since the black-height of i keys must be 1+ 1 2 log i. The time complexity of the algorithm can thus be reduced immediately to O(n 2 ).

It can be seen from observation (1) that the subtree of a T is a complete binary tree. If T has a size n, then its left subtree must have a size of

le f t(n) = 2 log n -1 -1 + min{2 log n -1 , n -2 log n + 1}
and its right subtree must have a size of

right(n) = n -le f t(n) -1
It follows that the range 0 ≤ t ≤ i/2 can be reduced to t = le f t(i). The time complexity of the algorithm can thus be reduced further to O(n).

Another efficient algorithm for r(n) need only O(log n) space can be built as follows.

Theorem 2 In a red-black tree T of n keys, let r(n) be the maximal number of red nodes in T . The values of d(1) = r(n) can be formulated as follows.

d(m) =    h(m) h(m) ≤ 1 1 + d(4m) + d(4m + 1) + d(4m + 2) + d(4m + 3) h(m) mod 2 = 1 d(2m) + d(2m + 1) h(m) mod 2 = 0 (19)
where

h(m) = 1 + log n -log m m 2 log n -log m ≤ n log n -log m otherwise (20)
Proof. We can label the nodes of a maximal red-black tree like a heap. The root of the tree is labeled 1. The left child of a node i is labeled 2i and the right child is labeled 2i+1. Let d(i) denote the maximal number of red nodes of T and h(i), denote the height at node i. Then we have r(n) = d(1). It is easy to verify that if

i 2 log n -log i > n, then we have h(i) = log n -log i , otherwise, h(i) = 1 + log n -log i . It is obvious that if h(i) ≤ 1, then d(i) = h(i).
Therefore, if h(i) is even then the left subtree rooted at node 2i and the right subtree rooted at node 2i+1 are both black. If h(i) odd, the four nodes rooted at nodes 4i, 4i+1, 4i + 2 and 4i + 3 can be all maximal red-black trees. Therefore, if h(i) > 1, we have

d(i) = 1 + d(4i) + d(4i + 1) + d(4i + 2) + d(4i + 3) h(i) odd d(2i) + d(2i + 1) h(i) even
The proof is complete.

A new recursive algorithm for r(n) can be build as the following algorithm.

Algorithm 1 t(i, j)

Input: i, j, the row and the collum number Output: t(i, j)

1: if i < 2 then 2: return i 3: else 4: if j = 1 then 5: return 2 3 (2 i -1) 6: else 7: if 2 ≤ j ≤ 2 i-1 then 8: return t(i -1, j) + 2 3 (2 i-1 -1) 9: else 10: if j = 2 i-1 + 1 then 11:
return 2 i -1 12: else 13: return t(i -1, j -2 i-1 ) + It can be seen that the time complexity of the algorithm is O(n), since each node is visited at most once in the algorithm. The space complexity of the algorithm is the stack space used in recursive calls. The depth of recursive is at most log n, and the space complexity of the algorithm is thus O(log n).

In order to find r(n), the algorithm can be reformulated in a non-recursive form as follows.

By further improvement of the formula, we can reduce algorithm to a very simple algorithm as follows.

It is clear that the time complexities of above two algorithms are both O log n.

If the number of n can fit into a computer word, then a(n) and o(n) can be computed in O(1) time.

Algorithm 2 r(n)

Input: n, the number of keys Output: r(n), the maximal number of red nodes 1: r ← 1, j ← n 2: for i = 1 to log n do 3: if j mod 2 = 1 then 4:

r ← r + η(i) 5: else 6:

r ← r + ξ (i -1) 7:

end if 8: j ← j/2 9: end for 10: return r Algorithm 3 r(n) Input: n, the number of keys Output: r(n), the maximal number of red nodes 1: r ← 1, x ← 0, y ← 1, j ← n 2: for i = 1 to log n do 3: if j mod 2 = 1 then 4:

r ← r + y 5: else 6: r ← r + x 7: end if 8:

if i mod 2 = 1 then 9:

x ← 2x + 1, y ← 2y + 1 10: else 11:

x ← 2x, y ← 2y -1 12:

end if 13: j ← j/2 14: end for 15: return r

Acknowledgement

This work was supported by Intelligent Computing and Information Processing of Fujian University Laboratory and Data-Intensive Computing of Fujian Provincial Key Laboratory.

Concluding remarks

We have presented a dynamic programming formula for computing r(n), the maximal number of red nodes of a red-black tree with n keys. The time complexity of the new algorithm is finally reduced to O(n) and the space is reduced to only O(log n).