Bloomopt Algorithm Optimizes Data Transfer in Path Expressions

path x.dongCo.nhaSanXuat.ten retrieves the name property value of the engine manufacturers of object x . We can create path expressions that contain properties as well as methods. Optimizing path expressions is a problem that has received much attention in the field of object query processing.

Path expressions provide a concise abstract notation for representing traversal of object composition graphs, allowing the shaping of predicates on values ​​deeply nested within an object structure. They provide a unified mechanism for shaping queries containing composition and inherited member functions. Path expressions can be of single-valued or set-valued type, and can appear in a query as a member of a predicate, a target of a query, or a member of a reference list. A path expression is single-valued if each member of the path expression is a single-valued. If at least one member of the path expression is a set of values, then the entire expression is a set of values. A technique for traversing forward and backward through a path expression has been discussed in [31].

The problem of path expression optimization spans the entire query optimization process. During or after parsing a query, but before algebraic optimization, the compiler must identify path expressions that are potentially optimizable. This is typically achieved through rewriting techniques, which transform path expressions into logical algebraic equivalents. Once the path expression is expressed in algebraic form, the query optimizer seeks the least-cost solution. Finally, the optimal execution method may contain algorithms that efficiently compute path expressions, including hash joins, complex object aggregations, or indexed scans of path indices.

Consider first a query rewrite and algebraic optimization. Consider the path expression x.car.manufacturer.name . Suppose that each instance of a car has a reference to an engine object, each engine has a reference to a manufacturer object, and each manufacturer has a name field. Suppose that the types DongCo and NhaSanXuat have a corresponding type family. The first two links of the path above might have to trace the engine and manufacturer objects

resides on disk. The third path consists of only a lookup of a field within a producer object. Thus only the first two paths present query optimization opportunities in computing that path. An object query compiler needs a mechanism to distinguish these paths in a path that represents optimization possibilities.

There have been some studies on path expression optimization in a centralized environment following Ozkan's heuristic approach in [45], rewriting complex path expressions into a simple form in Truong Bao Chau's doctoral thesis [2]. The algorithms proposed in [52], [34] are all dynamic programming algorithms. The limitation of the algorithm in [52] is that it only considers each path expression, not combining path expressions together. The limitation of the algorithm in [34] is that there is no filtering mechanism during data transmission and the subgraph generation algorithm is not optimal. In sections 3.3 and 3.4, the thesis will present path expression optimization algorithms in the PT-HDT database.

3.3. BloomOpt algorithm optimizes data transfer in path expressions

3.3.1. Introduction

The query cost in a distributed system includes the local processing cost at each station and the remote data transmission cost when needed, in which the normal data transmission cost is the largest cost. The problem of optimizing distributed queries is reduced to the problem of minimizing the above two costs. Reducing the local processing cost at each station is the problem of query processing in the centralized model that some studies have conducted. To reduce the data transmission cost, it is necessary to minimize the transmission of unnecessary data. There are a number of filtering algorithms to limit the transmitted data, including the filtering mechanism of the Bloom filter [16]. Using the Bloom filter to process distributed queries in relational database systems has been mentioned in articles [35], [46]. In this section, the thesis proposes an algorithm to optimize data transmission between layers when processing path expression queries in the PT-HDT database using the Bloom filter to reduce data transmission.

3.3.2. Query with path expression

Queries in object-oriented databases are expressed by the OQL language, which is an extension of and inherited from the SQL language. The design of OQL is in the form of functions, the results of queries have types, this allows the results of one query to be the input for another query, so it is possible to express complex queries.

When performing a query in the HDT database, if the classes have complex attributes, the query will be directed to nested objects according to a path expression.

Example 3.3: The database schema consists of the following classes: CanBoNghienCuu (Research Staff), ToChuc (Organization), DiaChi (Address). The CanBoNghienCuu class has the attribute coQuan which is a set of objects of the ToChuc class , the CoQuan class has the attribute diaChi which is an object of the DiaChi class , the DiaChi class has the attribute thanhPho .

Figure 3.3 : Illustration of classes with complex attributes

Suppose the query here is to list the names of researchers in Hanoi city and can be written as:

SELECT c.name

FROM CanBoNghienCuu as c

WHERE c.coQuan.diaChi.thanhPho = “Hanoi”

c.coQuan.diaChi.thanhPho is a path expression or also known as an implicit connection. Each object of the class has a unique identifier (OID) that is initialized by the system, and implicit connections are made through these identifiers. A path expression can be single-valued if each of its components is single-valued, otherwise if at least one component is a set of values, the entire expression is a set of values. Optimizing path expressions is an important goal in processing queries to the PT-HDT database.

3.3.3. Bloom filter

3.3.3.1.Bloom filter structure

Bloom filter introduced in [16], is a probabilistic data structure to check whether an element is in a set or not. The structure of a Bloom filter includes:

- An array of n bits, initialized to all values ​​0

- A set of hash functions h 1 , h 2 ,..h k . Each hash function will map the key values ​​to a value in the range from 1 to n, corresponding to the filter bit

- A set S consists of m key values

For each key value k in S:hash it according to the hash function, the i-th hash function has value h i (k), set the h i (k)-th bit of the Bloom filter to 1.

Filter function​​​

Bloom is a definition of a

quarter x has ́​

episode

S or

No. It is used as a pre - processing step of the search process . If after filtering​​​

through filter

Bloom returns “ no ” then no need to practice

porch

work

search​​

Also , if the result is “ maybe ” then the action is done .

porch

search .​

To determine a

any quarter x has​​​

episode

S or not, we are

The n-bit vector has the value h 1 ( x),..., h k (x) from x through the hash key . If the k bits in the n-bit vector at corresponding positions h 1 (x), h 2 (x),…, h k (x) all have the value 1 then x “ can ”

exists in the set S with some probability , and n if at least one bit has the value 0

then affirm h is x does not belong

episode

S. We can only assert that x “ has

drug

episode

S is because in a bit vector , 1 bit can be

the value is 1 more

swim multiple quarters in S when starting

filter. Just one

bit 0 we have

affirmative statement hx does not belong

S swims because if x belongs to

S then all corresponding k bits will

ok

is set to 1 at initialization Example 3.4:

filter

with a quarter of the x measure .

 Bloom filter consists of 9 bits, initially assigning all bits to 0.

 Using two hash functions: The first function h 1 (k) takes the values ​​at odd positions (from left to right) of k when represented in binary, and converts them to values

decimal and then divide by 9. The h 2 (k) function is similar but takes the value at even positions.

 S = {23, 147, 352}

 The process of building a Bloom filter is illustrated in Table 3.2

Table 3.2: Illustration of Bloom filter construction

Step

Binary performance k's stool	h 1 (k)	h 2 (k)	Bloom Filter
Initialization				000000000
k = 23	10111	7	1	010000010
k = 147	10010011	0 (9 mod 9)	5	110001010
k = 352	101100000	6 (24 mod 9)	4	110011110

Maybe you are interested!

• Data Structure and Algorithm - Hanoi College of Industry - 14
• Qos Assurance Methods for Multimedia Communications zt2i3t4l5ee zt2a3gs zt2a3ge zc2o3n4t5e6n7ts low. The EF PHB requires a sufficiently large number of output ports to provide low delay, low loss, and low jitter. EF PHBs can be implemented if the output port's bandwidth is sufficiently large, combined with small buffer sizes and other network resources dedicated to EF packets, to allow the router's service rate for EF packets on an output port to exceed the arrival rate λ of packets at that port. This means that packets with PHB EF are considered with a pre-allocated amount of output bandwidth and a priority that ensures minimum loss, minimum delay and minimum jitter before being put into operation. PHB EF is suitable for channel simulation, leased line simulation, and real-time services such as voice, video without compromising on high loss, delay and jitter values. Figure 2.10 Example of EF installation Figure 2.10 shows an example of an EF PHB implementation. This is a simple priority queue scheduling technique. At the edges of the DS domain, EF packet traffic is prioritized according to the values ​​agreed upon by the SLA. The EF queue in the figure needs to output packets at a rate higher than the packet arrival rate λ. To provide an EF PHB over an end-to-end DS domain, bandwidth at the output ports of the core routers needs to be allocated in advance to ensure the requirement μ > λ. This can be done by a pre-configured provisioning process. In the figure, EF packets are placed in the priority queue (the upper queue). With such a length, the queue can operate with μ > λ. Since EF was primarily used for real-time services such as voice and video, and since real-time services use UDP instead of TCP, RED is generally not suitable for EF queues because applications using UDP will not respond to random packet drop and RED will strip unnecessary packets. 2.2.4.2 Assured Forwarding (AF) PHB PHB AF is defined by RFC 2597. The purpose of PHB AF is to deliver packets reliably and therefore delay and jitter are considered less important than packet loss. PHB AF is suitable for non-real-time services such as applications using TCP. PHB AF first defines four classes: AF1, AF2, AF3, AF4. For each of these AF classes, packets are then classified into three subclasses with three distinct priority levels. Table 2.8 shows the four AF classes and 12 AF subclasses and the DSCP values ​​for the 12 AF subclasses defined by RFC 2597. RFC 2597 also allows for more than three separate priority levels to be added for internal use. However, these separate priority levels will only have internal significance. PHB Class PHB Subclass Package type DSCP AF4 AF41 Short 100010 AF42 Medium 100100 AF43 High 100110 AF3 AF31 Short 011010 AF32 Medium 011100 AF33 High 011110 AF2 AF21 Short 010010 AF22 Medium 010100 AF23 High 010110 AF1 AF11 Short 001010 AF12 Medium 001100 AF13 High 001110 Table 2.8 AF DSCPs The AF PHB ensures that packets are forwarded with a high probability of delivery to the destination within the bounds of the rate agreed upon in an SLA. If AF traffic at an ingress port exceeds the pre-priority rate, which is considered non-compliant or “out of profile”, the excess packets will not be delivered to the destination with the same probability as the packets belonging to the defined traffic or “in profile” packets. When there is network congestion, the out of profile packets are dropped before the in profile packets are dropped. When service levels are defined using AF classes, different quantity and quality between AF classes can be realized by allocating different amounts of bandwidth and buffer space to the four AF classes. Unlike EF, most AF traffic is non-real-time traffic using TCP, and the RED queue management strategy is an AQM (Adaptive Queue Management) strategy suitable for use in AF PHBs. The four AF PHB layers can be implemented as four separate queues. The output port bandwidth is divided into four AF queues. For each AF queue, packets are marked with three “colors” corresponding to three separate priority levels. In addition to the 32 DSCP 1 groups defined in Table 2.8, 21 DSCPs have been standardized as follows: one for PHB EF, 12 for PHB AF, and 8 for CSCP. There are 11 DSCP 1 groups still available for other standards. 2.2.5.Example of Differentiated Services We will look at an example of the Differentiated Service model and mechanism of operation. The architecture of Differentiated Service consists of two basic sets of functions: Edge functions: include packet classification and traffic conditioning. At the inbound edge of the network, incoming packets are marked. In particular, the DS field in the packet header is set to a certain value. For example, in Figure 2.12, packets sent from H1 to H3 are marked at R1, while packets from H2 to H4 are marked at R2. The labels on the received packets identify the service class to which they belong. Different traffic classes receive different services in the core network. The RFC definition uses the term behavior aggregate rather than the term traffic class. After being marked, a packet can be forwarded immediately into the network, delayed for a period of time before being forwarded, or dropped. We will see that there are many factors that affect how a packet is marked, and whether it is forwarded immediately, delayed, or dropped. Figure 2.12 DiffServ Example Core functionality: When a DS-marked packet arrives at a Diffservcapable router, the packet is forwarded to the next router based on Per-hop behavior is associated with packet classes. Per-hop behavior affects router buffers and the bandwidth shared between competing classes. An important principle of the Differentiated Service architecture is that a router's per-hop behavior is based only on the packet's marking or the class to which it belongs. Therefore, if packets sent from H1 to H3 as shown in the figure receive the same marking as packets from H2 to H4, then the network routers treat the packets exactly the same, regardless of whether the packet originated from H1 or H2. For example, R3 does not distinguish between packets from h1 and H2 when forwarding packets to R4. Therefore, the Differentiated Service architecture avoids the need to maintain router state about separate source-destination pairs, which is important for network scalability. Chapter Conclusion Chapter 2 has presented and clarified two main models of deploying and installing quality of service in IP networks. While the traditional best-effort model has many disadvantages, later models such as IntServ and DiffServ have partly solved the problems that best-effort could not solve. IntServ follows the direction of ensuring quality of service for each separate flow, it is built similar to the circuit switching model with the use of the RSVP resource reservation protocol. IntSer is suitable for services that require fixed bandwidth that is not shared such as VoIP services, multicast TV services. However, IntSer has disadvantages such as using a lot of network resources, low scalability and lack of flexibility. DiffServ was born with the idea of ​​solving the disadvantages of the IntServ model. DiffServ follows the direction of ensuring quality based on the principle of hop-by-hop behavior based on the priority of marked packets. The policy for different types of traffic is decided by the administrator and can be changed according to reality, so it is very flexible. DiffServ makes better use of network resources, avoiding idle bandwidth and processing capacity on routers. In addition, the DifServ model can be deployed on many independent domains, so the ability to expand the network becomes easy. Chapter 3: METHODS TO ENSURE QoS FOR MULTIMEDIA COMMUNICATIONS In packet-switched networks, different packet flows often have to share the transmission medium all the way to the destination station. To ensure the fair and efficient allocation of bandwidth to flows, appropriate serving mechanisms are required at network nodes, especially at gateways or routers, where many different data flows often pass through. The scheduler is responsible for serving packets of the selected flow and deciding which packet will be served next. Here, a flow is understood as a set of packets belonging to the same priority class, or originating from the same source, or having the same source and destination addresses, etc. In normal state when there is no congestion, packets will be sent as soon as they are delivered. In case of congestion, if QoS assurance methods are not applied, prolonged congestion can cause packet drops, affecting service quality. In some cases, congestion is prolonged and widespread in the network, which can easily lead to the network being "frozen", or many packets being dropped, seriously affecting service quality. Therefore, in this chapter, in sections 3.2 and 3.3, we introduce some typical network traffic load monitoring techniques to predict and prevent congestion before it occurs through the measure of dropping (removing) packets early when there are signs of impending congestion. 3.1. DropTail method DropTail is a simple, traditional queue management method based on FIFO mechanism. All incoming packets are placed in the queue, when the queue is full, the later packets are dropped. Due to its simplicity and ease of implementation, DropTail has been used for many years on Internet router systems. However, this algorithm has the following disadvantages: − Cannot avoid the phenomenon of “Lock out”: Occurs when 1 or several traffic streams monopolize the queue, making packets of other connections unable to pass through the router. This phenomenon greatly affects reliable transmission protocols such as TCP. According to the anti-congestion algorithm, when locked out, the TCP connection stream will reduce the window size and reduce the packet transmission speed exponentially. − Can cause Global Synchronization: This is the result of a severe “Lock out” phenomenon. Some neighboring routers have their queues monopolized by a number of connections, causing a series of other TCP connections to be unable to pass through and simultaneously reducing the transmission speed. After those monopolized connections are temporarily suspended, Once the queue is cleared, it takes a considerable amount of time for TCP connections to return to their original speed. − Full Queue phenomenon: Data transmitted on the Internet often has an explosion, packets arriving at the router are often in clusters rather than in turn. Therefore, the operating mechanism of DropTail makes the queue easily full for a long period of time, leading to the average delay time of large packets. To avoid this phenomenon, with DropTail, the only way is to increase the router's buffer, this method is very expensive and ineffective. − No QoS guarantee: With the DropTail mechanism, there is no way to prioritize important packets to be transmitted through the router earlier when all are in the queue. Meanwhile, with multimedia communication, ensuring connection and stable speed is extremely important and the DropTail algorithm cannot satisfy. The problem of choosing the buffer size of the routers in the network is to “absorb” short bursts of traffic without causing too much queuing delay. This is necessary in bursty data transmission. The queue size determines the size of the packet bursts (traffic spikes) that we want to be able to transmit without being dropped at the routers. In IP-based application networks, packet dropping is an important mechanism for indirectly reporting congestion to end stations. A solution that prevents router queues from filling up while reducing the packet drop rate is called dynamic queue management. 3.2. Random elimination method – RED 3.2.1 Overview RED (Random Early Detection of congestion; Random Early Drop) is one of the first AQM algorithms proposed in 1993 by Sally Floyd and Van Jacobson, two scientists at the Lawrence Berkeley Laboratory of the University of California, USA. Due to its outstanding advantages compared to previous queue management algorithms, RED has been widely installed and deployed on the Internet. The most fundamental point of their work is that the most effective place to detect congestion and react to it is at the gateway or router. Source entities (senders) can also do this by estimating end-to-end delay, throughput variability, or the rate of packet retransmissions due to drop. However, the sender and receiver view of a particular connection cannot tell which gateways on the network are congested, and cannot distinguish between propagation delay and queuing delay. Only the gateway has a true view of the state of the queue, the link share of the connections passing through it at any given time, and the quality of service requirements of the traffic flows. The RED gateway monitors the average queue length, which detects early signs of impending congestion (average queue length exceeding a predetermined threshold) and reacts appropriately in one of two ways: − Drop incoming packets with a certain probability, to indirectly inform the source of congestion, the source needs to reduce the transmission rate to keep the queue from filling up, maintaining the ability to absorb incoming traffic spikes. − Mark “congestion” with a certain probability in the ECN field in the header of TCP packets to notify the source (the receiving entity will copy this bit into the acknowledgement packet). Figure 3. 1 RED algorithm The main goal of RED is to avoid congestion by keeping the average queue size within a sufficiently small and stable region, which also means keeping the queuing delay sufficiently small and stable. Achieving this goal also helps: avoid global synchronization, not resist bursty traffic flows (i.e. flows with low average throughput but high volatility), and maintain an upper bound on the average queue size even in the absence of cooperation from transport layer protocols. To achieve the above goals, RED gateways must do the following: − The first is to detect congestion early and react appropriately to keep the average queue size small enough to keep the network operating in the low latency, high throughput region, while still allowing the queue size to fluctuate within a certain range to absorb short-term fluctuations. As discussed above, the gateway is the most appropriate place to detect congestion and is also the most appropriate place to decide which specific connection to report congestion to. − The second thing is to notify the source of congestion. This is done by marking and notifying the source to reduce traffic. Normally the RED gateway will randomly drop packets. However, if congestion If congestion is detected before the queue is full, it should be combined with packet marking to signal congestion. The RED gateway has two options: drop or mark; where marking is done by marking the ECN field of the packet with a certain probability, to signal the source to reduce the traffic entering the network. − An important goal that RED gateways need to achieve is to avoid global synchronization and not to resist traffic flows that have a sudden characteristic. Global synchronization occurs when all connections simultaneously reduce their transmission window size, leading to a severe drop in throughput at the same time. On the other hand, Drop Tail or Random Drop strategies are very sensitive to sudden flows; that is, the gateway queue will often overflow when packets from these flows arrive. To avoid these two phenomena, gateways can use special algorithms to detect congestion and decide which connections will be notified of congestion at the gateway. The RED gateway randomly selects incoming packets to mark; with this method, the probability of marking a packet from a particular connection is proportional to the connection's shared bandwidth at the gateway. − Another goal is to control the average queue size even without cooperation from the source entities. This can be done by dropping packets when the average size exceeds an upper threshold (instead of marking it). This approach is necessary in cases where most connections have transmission times that are less than the round-trip time, or where the source entities are not able to reduce traffic in response to marking or dropping packets (such as UDP flows). 3.2.2 Algorithm This section describes the algorithm for RED gateways. RED gateways calculate the average queue size using a low-pass filter. This average queue size is compared with two thresholds: minth and maxth. When the average queue size is less than the lower threshold, no incoming packets are marked or dropped; when the average queue size is greater than the upper threshold, all incoming packets are dropped. When the average queue size is between minth and maxth, each incoming packet is marked or dropped with a probability pa, where pa is a function of the average queue size avg; the probability of marking or dropping a packet for a particular connection is proportional to the bandwidth share of that connection at the gateway. The general algorithm for a RED gateway is described as follows: [5] For each packet arrival Caculate the average queue size avg If minth ≤ avg < maxth div.maincontent .s1 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 15pt; } div.maincontent .s2 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 15pt; } div.maincontent .p { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; margin:0pt; } div.maincontent p { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; margin:0pt; } div.maincontent .s3 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 14pt; } div.maincontent .s4 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s5 { color: black; font-family:"Times New Roman", serif; font-style: italic; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s6 { color: black; font-family:"Times New Roman", serif; font-style: italic; font-weight: bold; text-decoration: none; font-size: 14pt; } div.maincontent .s7 { color: black; font-family:Wingdings; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s8 { color: black; font-family:Arial, sans-serif; font-style: italic; font-weight: bold; text-decoration: none; font-size: 15pt; } div.maincontent .s9 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 14pt; } div.maincontent .s10 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; vertical-align: 6pt; } div.maincontent .s11 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 13pt; } div.maincontent .s12 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10pt; } div.maincontent .s13 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-d
• Pre-tax Profit of Bidv Tien Giang in the Period 2011-2015 zt2i3t4l5ee zt2a3gsnon-credit services, joint stock commercial bank zt2a3ge zc2o3n4t5e6n7ts At that time, the Branch had to set aside a provision for credit risks, which reduced the Branch's income. Chart 2.2. Pre-tax profit of BIDV Tien Giang in the period 2011-2015 Unit: Billion VND 140 120 100 80 60 40 20 0 63.3 80.34 89.29 110.08 131.99 2011 2012 2013 2014 2015 Profit before tax (Source: Report on the implementation of the annual business plan of the General Planning Department of BIDV Tien Giang [24]) However, through chart 2.2, it can be seen that BIDV Tien Giang's profit is still increasing continuously, and its operating efficiency is currently leaking. This is a contribution of non-credit services, and this service segment will be increasingly focused on growth by BIDV Tien Giang to ensure the highest profit safety because credit activities have many potential risks. At the same time, focusing on developing non-credit services is consistent with one of the contents of restructuring the financial activities of credit institutions in the project "Restructuring the system of credit institutions in the period 2011-2015" approved by the Prime Minister in Decision No. 254/QD-TTg dated March 1, 2012 [14]: "Gradually shifting the business model of commercial banks towards reducing dependence on credit activities and increasing income from non-credit services". 2.2. Current status of non-credit service development at BIDV Tien Giang. 2.2.1. BIDV Tien Giang has deployed the development of non-credit services in recent times. Along with the development of the Head Office, BIDV Tien Giang's products and services are constantly improved and deployed in a diverse manner to ensure provision for many different customer groups in the area: individual customers, corporate customers, and financial institutions. Typical services are as follows: Payment services, treasury services, guarantee services, card services, trade finance, other services: Western Union, insurance commissions, consulting services, foreign exchange derivatives trading, e-banking services,... 2.2.1.1. Payment services: In accordance with the Prime Minister's Project to promote non-cash payments in Vietnam [15], banks in Tien Giang province have continuously developed payment services to reduce customers' cash usage habits through card services and electronic banking services such as: salary payment through accounts, focusing on developing card acceptance points, developing multi-purpose cards, paying social insurance by transfer, paying bills through banks, etc. Chart 2.3. Net income from payment services in the period 2011-2015 Unit: Million VND 6000 5000 4000 3000 2000 1000 0 3922 4065 4720 5084 5324 2011 2012 2013 2014 2015 Net income from payment services (Source: Report on the implementation of the annual business plan of the General Planning Department of BIDV Tien Giang [24]) Along with the technological development of the entire system, BIDV Tien Giang has a payment system with a fairly stable transaction processing speed, bringing many conveniences to customers. The results of observing chart 2.3 show that the income from payment services that the Branch has achieved has grown over the years but the speed is not high and the products are not outstanding compared to other banks. Domestic payment products such as: Online bill payment, electricity bills, water bills, insurance premiums, cable TV bills, telecommunications fees, airline tickets, etc. bring many conveniences to customers. Regarding international payment, this is an indispensable activity for foreign economic activities, BIDV Tien Giang is providing international payment methods for small enterprises producing agriculture, aquatic food and seafood that have credit relationships with banks in industrial parks in Tien Giang province such as: money transfer, collection, L/C payment. 2.2.1.2. Treasury services: BIDV Tien Giang always focuses on ensuring treasury safety and currency security, always complies with legal regulations, and minimizes risks in operations such as: counting and collecting money from customers, receiving and delivering internal transactions, collecting from the State Bank (SBV) or other credit institutions, receiving ATM funds, bundling money, etc. BIDV Tien Giang's treasury service management department is always fully equipped with modern machinery and equipment such as: money transport vehicles, fire prevention tools, money counters, money detectors, magnifying glasses, etc. to ensure absolute safety in treasury operations, immediately identifying real and fake money and other risks that may affect people and assets of the bank and customers. In addition, implementing regulation 2480/QC dated October 28, 2008 between the State Bank of Tien Giang province and the Provincial Police on coordination in the fight against counterfeit money, in the 3-year review of implementation, BIDV Tien Giang discovered, seized and submitted to the State Bank of Tien Giang province 475 banknotes of various denominations and was commended by the Provincial Police and the State Bank of Tien Giang province [17]. Chart 2.4. Net income from treasury services in the period 2011-2015 Unit: Million VND 350 300 250 200 150 100 50 0 105 122 309 289 279 2011 2012 2013 2014 2015 Net income from treasury services (Source: Report on the implementation of the annual business plan of the General Planning Department of BIDV Tien Giang [24]) However, as shown in Figure 2.4, income from treasury operations is not high and fluctuates. Specifically, in the period 2011-2013, net income increased and increased most sharply in 2013, then in the period 2013-2015, there was a downward trend. This fluctuation is due to the fact that fees collected from treasury services are often very low and can even be waived to attract customers to use other services. 2.2.1.3. Guarantee and trade finance services: BIDV Tien Giang, thanks to the advantages of the province and the favorable location of the Branch, has continuously focused on developing income from guarantee services and trade finance. Chart 2.5. Net income from guarantee and trade finance services in the period 2011-2015 Unit: Million VND 14000 12000 10000 8000 6000 4000 2000 0 5193 5695 2742 3420 8889 3992 11604 12206 5143 5312 2011 2012 2013 2014 2015 Net income from guarantee services Net income from Trade Finance (Source: Report on the implementation of the annual business plan of the General Planning Department of BIDV Tien Giang [24]) Through chart 2.5, we can see that BIDV Tien Giang's income from guarantee services and trade finance has grown over the years. The reason is: Among BIDV Tien Giang's corporate customers, the construction industry is the industry with the highest proportion of customers after the trading industry, this is a group of customers with potential to develop guarantee services. The second group of customers is corporate customers in the fields of agricultural production, livestock and seafood processing with high import and export turnover in the area. are the target of trade finance development. In addition, BIDV Tien Giang also focuses on continuously developing these customer groups to increase revenue for many other products and services in the future. 2.2.1.4. Card and POS services: As a service that BIDV Tien Giang has recently developed strongly, it can be said that this is a very potential market and has the ability to develop even more strongly in the future. Card services with outstanding advantages such as fast payment time, wide payment range, quite safe, effective and suitable for the integration trend and the Project to promote non-cash payments in Vietnam. Cards have become a modern and popular payment tool. BIDV Tien Giang early identified that developing card services is to expand the market to people in society, create capital mobilized from card-opened accounts, contribute to diversifying banking activities, enhance the image of the bank, bring the BIDV Tien Giang brand to people as quickly and easily as possible. BIDV Tien Giang is currently providing card types such as: credit cards (BIDV MasterCard Platinum, BIDV Visa Gold Precious, BIDV Visa Manchester United, BIDV Visa Classic), international debit cards (BIDV Ready Card, BIDV Manu Debit Card), domestic debit cards (BIDV Harmony Card, BIDV eTrans Card, BIDV Moving Card, BIDV-Lingo Co-branded Card, BIDV-Co.opmart Co-branded Card). These cards can be paid via POS/EDC or on the ATM system. In addition, with debit cards, customers can not only withdraw money via ATMs but also perform utilities such as mobile top-up, online payment, money transfer,... through electronic banking services. In order to attract customers with card services, BIDV Tien Giang has continuously increased the installation of ATMs. As of December 31, 2015, BIDV Tien Giang has 23 ATMs combined with 7 ATMs in the same system of BIDV My Tho, so the number of ATMs is quite large, especially in the center of My Tho City, but is not yet fully present in the districts. Basic services on ATMs such as withdrawing money, checking balances, printing short statements,... BIDV ATMs accept cards from banks in the system. Banknetvn and Smartlink, cards branded by international card organizations Union Pay (CUP), VISA, MasterCard and cards of banks in the Asian Payment Network. From here, cardholders can make bill payments for themselves or others at ATMs, by simply entering the subscriber number or customer code, booking code that service providers notify and make bill payments. Chart 2.6. Net income from card services in the period 2011-2015 Unit: Million VND 3500 3000 2500 2000 1500 1000 500 0 687 1023 1547 2267 3104 2011 2012 2013 2014 2015 Net income from card services (Source: Report on the implementation of the annual business plan of the General Planning Department of BIDV Tien Giang [24]) Through chart 2.6, it can be seen that BIDV Tien Giang's card service income is constantly growing because the Branch focuses on developing businesses operating in industrial parks, which are the source of customers for salary payment products, ATMs, BSMS. Specifically, there are companies such as Freeview, Quang Viet, Dai Thanh, which are businesses with a large number of card openings at the Branch, contributing to the increase in card service fees [25]. Table 2.6. Number of ATMs and POS machines in 2015 of some banks in Tien Giang area. Unit: Machine STT Bank name Number of ATMs Cumulative number of ATM cards POS machine 1 BIDV Tien Giang 23 97,095 22 2 BIDV My Tho 7 21,325 0 3 Agribank Tien Giang 29 115,743 77 4 Vietinbank Tien Giang 16 100,052 54 5 Dong A Tien Giang 26 97,536 11 6 Sacombank Tien Giang 24 88,513 27 7 Vietcombank Tien Giang 15 61,607 96 8 Vietinbank - Tay Tien Giang Branch 6 46,042 38 (Source: 2015 Banking Activity Data Report of the General and Internal Control Department of the Provincial State Bank [21]) Through table 2.6, the author finds that the number of ATMs of BIDV Tien Giang is not much, ranking fourth after Agribank Tien Giang, Dong A Tien Giang, Sacombank Tien Giang. The number of POS machines of BIDV Tien Giang is very small, only higher than Dong A Tien Giang and BIDV My Tho in the initial stages of merging the BIDV system. Besides, BIDV Tien Giang has a high number of cards increasing over the years (table 2.7) but the cumulative number of cards issued up to December 31, 2015 is still relatively low compared to Agribank, Vietcombank, Dong A (table 2.6). div.maincontent .content_head3 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 14pt; } div.maincontent .p { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; margin:0pt; } div.maincontent p { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; margin:0pt; } div.maincontent .s1 { color: black; font-family:"Courier New", monospace; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s2 { color: black; font-family:"Times New Roman", serif; font-style: italic; font-weight: normal; text-decoration: none; font-size: 13pt; } div.maincontent .s3 { color: black; font-family:"Times New Roman", serif; font-style: italic; font-weight: bold; text-decoration: none; font-size: 14pt; } div.maincontent .s4 { color: black; font-family:"Times New Roman", serif; font-style: italic; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s5 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s6 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 14pt; } div.maincontent .s7 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 13.5pt; } div.maincontent .s8 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; } div.maincontent .s9 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; vertical-align: -2pt; } div.maincontent .s10 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; vertical-align: 5pt; } div.maincontent .s11 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; vertical-align: -5pt; } div.maincontent .s12 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; vertical-align: -3pt; } div.maincontent .s13 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9pt; vertical-align: -4pt; } div.maincontent .s14 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 7.5pt; } div.maincontent .s15 { color: black; font-family:"Times New Roman", serif; font-style: italic; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s16 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; } div.maincontent .s17 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 9.5pt; } div.maincontent .s18 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; vertical-align: -1pt; } div.maincontent .s19 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; vertical-align: -5pt; } div.maincontent .s20 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; vertical-align: -2pt; } div.maincontent .s21 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10pt; } div.maincontent .s22 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; } div.maincontent .s23 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; vertical-align: -3pt; } div.maincontent .s24 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; vertical-align: -5pt; } div.maincontent .s25 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; } div.maincontent .s26 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; vertical-align: -4pt; } div.maincontent .s27 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; vertical-align: -6pt; } div.maincontent .s28 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; vertical-align: -1pt; } div.maincontent .s29 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 11.5pt; } div.maincontent .s30 { color: black; font-family:Calibri, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 11pt; } div.maincontent .s31 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 11pt; } div.maincontent .s32 { color: black; font-family:.VnTime, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 14pt; } div.maincontent .s33 { color: black; font-family:Cambria, serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; } div.maincontent .s34 { color: black; font-family:Cambria, serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 10.5pt; vertical-align: -4pt; } div.maincontent .s35 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 11.5pt; } div.maincontent .s36 { color: black; font-family:Arial, sans-serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 14pt; } div.maincontent .s37 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: bold; text-decoration: none; font-size: 13pt; } div.maincontent .s38 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 13pt; } div.maincontent .s39 { color: black; font-family:"Times New Roman", serif; font-style: normal; font-weight: normal; text-decoration: none; font-size: 15pt; } div.maincontent .s40 { color: black; font-family:"Times New Roman", serif; font-style: normal; fo
• Table of Data Converted to Logarithm Base E
• Summary Table of Data Illustrating the Contents of the Thesis

 If x = 15, the binary representation of x is 1111, h 1 (x) = h 2 (x) =3. At bit number 3 of the Bloom filter, the value is 0, so x is definitely not in S.

3.3.3.2. Error analysis

With a filter two errors can occur:

 False positive : Filter check is there but actual search is not there

 False negative : Filter check is not available but actual search is available

With Bloom filter, there is no possibility of false negative error , but only a very small probability of false positive error . The probability of encountering false positive error depends on the density of bits with value 1 and the number of hash functions.

The probability that a random bit of an n-bit array is assigned the value 1 by the function

hash rate is 1/n, the probability that that bit is not assigned the value 1 is (1 −

1 ) . Probability for bit

that is not assigned the value 1 by any hash function is (1 −

n

1 ) 𝑘 where k is a number

𝑛

hash functions. Given m key values, the probability that that bit remains 0 is

(1 −

1 ) mk ,

n

and the probability that that bit is set to 1 is (1 − (1 − 1 ) mk ) .

n

Consider the process of checking whether an element is in a set or not. The algorithm checks k positions in the array to see if they are equal to 1 or not, with probability

] mk k −km/nk

all of them are equal to 1 is (1 − [1 −1) ≈ (1 − e ) for very large n. Verify

n

This probability does not depend on the element being tested and is therefore called the false positive probability. The false positive probability can be reduced by choosing appropriate values ​​of n, k, and m. The value of n needs to be quite large compared to m, and this probability can be further reduced by increasing the number of

hash function. In the best case, the optimal value of k is k = n ln2 , then the probability

m

The false positive is minimized with respect to k and will be p = 2 −k = 2 −nln2/m => n =

− mlnp . That is, to keep the probability of false positive constant, the size of

(ln2) 2

The array is linear in the number of elements in the set.

3.3.4. Using Bloom filters to reduce communication costs

We will describe an algorithm that uses a Bloom filter to process a query with a path expression between two classes. Suppose class C i has an attribute a k which is an object of class C j , class C i is located at station S, class C j is located at station R. It is easy to see that the size of an object of class C j is smaller than the size of an object of class C i . Suppose there is a query containing a path expression from class C i to class C j . Let the cost of transmitting a unit of data from station S to station R be transCost(S, R), assuming this transmission cost is symmetric, that is, transCost (S, R) = transCost (R, S).

The main idea here is that instead of transmitting all the objects of C j from R to S for association with C i (or vice versa), we will filter some objects of C j that are necessary for association with C i . This will reduce the amount of data transmitted and, consequently, the cost of data transmission. The filtering mechanism will be implemented by a Bloom filter. There are three cases: (1) The query occurs at station S (which contains C i ). (2) The query occurs at station R (which contains C j ). (3) The query occurs at a station other than S and R. We will consider each case in turn.

Case 1 : Query at station S

- Build a Bloom filter for all objects of class C i according to attribute value a k , called BF(C i ).

- Send BF(C i ) to R (the station containing C j ), BF(C i ) is used to filter the objects of C j .

- Send the objects of C j that satisfy the above filter condition to S

- Execute queries from objects of C i and C j at S

Algorithm 3.1 - Case1(C i , C j , R, S)

Input:

- Class C i at station R and class C j at station S

- Attribute a k of class C i is an object of class C j

Output:

- result is the result of the join operation C i and layer C j at station S

Steps to follow:

BF(C i ) = createBloomFilter(C i ,a k ); send(BF(C i ),S, R);

tempClass = filter(C j , BF(C i )); send(tempClass, R, S);

result = join(C i , tempClass); end; {Algorithm 3.1}

Case 2: Query at station R

 Build a Bloom filter for all objects of class C j according to the value of the identifying attribute, called BF(C j ).

 Send BF(C j ) to S (the station containing C i ), BF(C j ) is used to filter the objects of C i .

 Send objects of C i that satisfy the above filter conditions to R

 Execute queries from objects of C i and C j at R

Algorithm 3.2 – Case2(C i , C j , R, S)

Input:

- Class C i at station R and class C j at station S

Output:

- result is the result of the join operation C i and layer C j at station R

Steps to follow:

BF(C j )= createBloomFilter(C i , oid(C j )); send(BF(C j ), R, S);

tempClass = filter(C i , BF(C i )); send(tempClass, S, R);

result = join(tempClass, C j ); end; {Algorithm 3.2}

Case 3 : The query at the station does not contain both C i and C j , let's say station P ( P ≠ S , P ≠ R )

 Compare the cost of transmitting a unit of data in 3 cases:

o (a) transCost (S, R) + transCost (R, P)

o (b) transCost (R, S) + transCost (S, P)

o (c) transCost (S, P) + transCost (R, P)

 If the minimum cost is case (a), perform the steps as in case 1, then transmit the result from S to P.

 If the minimum cost is case (b), perform the steps as in case 2, then transmit the result from R to P

 If the minimum cost is case (c)

o If transCost (S, P) <= transCost (R, P)

 Build a Bloom filter for all objects in class C i

according to the attribute value a k , called BF(C i ).

 Send BF(C i ) to P, then from P send BF(C i ) to R. BF(C i ) is used to filter the objects of C j .