OAZE: a Network-Friendly Distributed Zapping System for Peer-to-Peer IPTV

IPTV systems attracting millions of users are now commonly deployed on peer-to-peer (P2P) infrastructures and provide an appealing alternative to multicast-based systems. Typically, a P2P overlay network is associated with each channel, composed of users who receive, watch and redistribute this channel. Yet, channel surﬁng (aka as zapping) involves switching overlays and may introduce delays, potentially hurting the user experi-ence when compared to multicast-based IPTV. In this paper, we present a distributed sys-tem called OAZE (Overlay Augmentation for Zapping Experience) which speeds up the switching process and reduces the overall cross-domain trafﬁc generated by the IPTV sys-tem. In OAZE, each peer maintains connections to other peers, not only in a given channel, but also in a subset of all channels to which the associated user is likely to zap. More spe-ciﬁcally, we focus on the channel assignment problem, i.e. determining, in a given P2P overlay, the optimal distribution of the responsibility to maintain contact peers to other channels. We propose an approximate algorithm providing guaranteed performances, and a simpler and more practical one. Our experimental results show that OAZE leads to substantial improvements on the connections between peers, resulting in less switching delay and lower network cost; it then represents an appealing add-on for existing P2P IPTV systems.

Context and motivations
P2P systems have recently been considered as appealing alternatives to disseminate TV content over the Internet (aka IPTV). Such approaches have led not only to theoretical proposals (see [1] for an overview of the main theoretical challenges) but also practical applications used by millions of users (e.g., PPlive, sopcast, PPStream). Such system usually rely on creating a P2P overlay network per channel, connecting all users of the channel. However, these P2P IPTV systems usually do not implement an efficient channel zapping feature; the interval between the time a new channel is selected and the time the actual playback starts on the screen, commonly called start-up delay, can be prohibitively long. Should measurements highlighting the high frequency of zapping be confirmed [2,3], this could be a serious burden for the success of P2P IPTV systems.
The start-up delay can be broken down in two components: the bootstrap delay is the delay between the time a user decides to switch channel and the reception of a first video packet from another peer, and the player buffering delay is the delay between the reception of the first video packet and the actual video playback. Measurement studies [4][5][6] consistently report that the total start-up delays ranges from 10 to 20 s for a popular channel and up to 2 min for less popular ones. In our previous paper [7] (see Supplementary data), we analyzed the bootstrap delay in PPlive, and we identified the major cause of the poor bootstrap performances in current P2P systems: this is due to the absence of reactivity from the first set of peers that a new peer contacts when it joins a channel overlay (less than one fifth of contacted peers actually respond). This set of peers, usually referred as the peerlist in the literature, is provided by a tracker. In addition to the poor ratio of responses of peers in the peerlist, our measurement also showed that two thirds of the peers that provide content in the first 2 min appear in the peerlist. Therefore, the responsiveness of the initial list of contacts (peerlist) when joining a channel is of the untmost importance for an efficient bootstrap. Precisely, channel surfing is about switching channels frequently.
Recent P2P live streaming systems rely on a gossipbased topology management system to connect peers (e.g. [8]) of a given channel. The overlay construction is driven by some guidelines, including a preference system, which allows to determine which neighbors a peer should preferentially connect with. The ''best'' peers that a peer can find in its overlay are called its matching peers. Periodically, some potential new neighbors are introduced to every peer by its neighbors. An operation allows to determine if some of these potential neighbors match better than current overlay neighbors. If so, the neighborhood can be improved by simply replacing the less matching overlay neighbors by these new matching ones, then a handshake should be completed (including typically an exchange of the map of downloaded packets). A cycle corresponds to the reception of a new list of potential neighbors, and the associated handshakes. The T-Man gossip system has shown the benefits one can expect from such a topology management system [8]. From the initial peerlist, a peer iteratively discovers better peers until it is connected to its matching peers. Ideally, the initial peerlist contains only matching peers. With a randomly chosen initial peerlist (a list of supposedly active peers provided by a central server for a given channel), a joining peer has low chance to be connected directly to matching peers. Despite some works in this direction (e.g. [9,10]), a central server can hardly provide peers with matching peers quickly, in a scalable fashion. This calls for a new strategy.
In this paper, we present OAZE for Overlay Augmentation for Zapping Experience, which has been introduced in [7]. We focus on the case where the preference system of the mesh-based P2P IPTV system is a function of the network distance between peers for that enable to improve startup delays. The design of network-friendly P2P systems, where peers tend to connect preferentially to peers that are located in the same Autonomous System (AS), has recently appeared to be a major topic of research [11,12]. We show that OAZE improves the channel switching process by connecting with high probability a peer joining a new channel to peers that are actually active in the overlay of this channel. Furthermore, since the initial peerlist contains matching peers with higher probability than peerlists provided by central servers, connections between distant peers are avoided and the number of handshakes are reduced.

Rationale
In IPTV systems, some channels are clearly more popular than others [2,13]. Moreover, channels exhibit content similarities such that a participant is more likely to switch to a channel displaying similar content than the one it is currently enjoying. For example, it has been shown [2] that 76% of switches are done in the same channel genre (e.g. sport, music or news). Let us state that a channel c 2 is adjacent to a channel c 1 if, when a user watches c 1 , the probability to switch to c 2 is among the largest probabilities over all channels. Several works (e.g. [14]) have leveraged this property of users behavior to reduce the switching delay in multicast-based IPTV (networks controlled by telco operators). The idea is to send data of some adjacent channels along with the current channel data, anticipating a potential channel switching. This technique has been extended in order to maximize the probability that the target channels are within the set of adjacent channels [15,16].In addition, sophisticated recommendation systems [17,18] based on user profile have recently been designed in order to accurately predict the adjacent channels.
Yet, in P2P IPTV systems, receiving simultaneously several multimedia flows, even degraded, remains expensive (important overhead of applicative multicast over IP, compared to lower layer multicast). However, we believe that this ability to predict accurately the most probable switching channels can be leveraged in P2P IPTV systems as well. This is precisely the idea of OAZE, where every peer maintains connections to peers in adjacent channels to account for a potential channel switching operation. More precisely, peers maintain accurate peerlists for the overlays of adjacent channels. In related works related to multichannel systems [9,19], concurrent to our work, each peer is also connected to one or more channels that are independent of the channel the peer is viewing. In order to limit the bandwidth overhead, each peer is allowed to determine the fraction of upload capacity dedicated to every other stream. This work is complementary to ours. We choose to not impose peers to download unnecessary stream data. Instead, we focus on the connections between peers and their contact peers in adjacent channels. We aim at showing the benefits one can expect from a relevant mechanism to link peers from distinct channels. Yet, it is possible to implement, on top of OAZE, some prefetching mechanisms like the one presented in [9,19].

Contributions
We have introduced the main concept of OAZE in a previous paper [7]. In this paper, we give a comprehensive description of the OAZE algorithms augmented with two additional contributions: (1) the distribution of the switching task and (2) and extensive evaluation of the system. In OAZE, peers maintain a set of overlay neighbors, with whom they exchange video content related to their channel and contact peers, peers acting as contact points to other channel overlays. When a peer x has a contact peer in the channel c, we say that x is a switcher to c. Instead of being a switcher to all adjacent channels, which would yield important maintenance costs, peers in OAZE leverage their overlay neighbors to switch to other channels. When a peer x wants to switch to a channel c, it requests contact peers in c from an overlay neighbor that is a switcher to c. Although OAZE has been designed for channel switching, its applicability goes beyond. More generally, the problem addressed in this paper consists of switching from a highly connected cluster of peers to another highly connected cluster within a giant overlay network. Typically, switching from one chapter to another chapter in a P2P VoD streaming system can be formulated in the same way, and solutions are unsurprisingly related to prefetching of most probable seeking positions [20,21].
In this paper, we first address the problem of distributing the switching task to the peers. The performances of OAZE highly depend on the ability of peers to discover a switcher to a given channel in their neighborhood (contact peers). When a peer joins an overlay, it should decide which adjacent channels it wants to become a switcher to, with regard to its overlay neighbors. We call the problem of distributing the switching responsibility to peers in a given overlay the channel assignment problem.W e show that determining the optimal solution of a channel assignment problem is a NP-hard problem. From a theoretical side, no exact solution can be computed in a reasonable time, and therefore we provide two heuristics to assign adjacent channels to peers: an approximate algorithm and a practical distributed solution. In the first approach, the assignment computation can be distributed.
When the number of adjacent channels is a and only one channel is assigned to every peer, the solution is guaranteed to be no more than 3 2 a À 5 2 times the optimal one. However, since all peers in the overlay should simultaneously execute the algorithm, this algorithm can only be used in certain cases, for example when the channel assignment is computed from scratch, or when the set of adjacent channels is re-defined. In the second approach, every peer joining a new channel explores its neighborhood in order to determine which channels it should be a switcher to. We show that this algorithm outperforms a basic random algorithm where every peer picks at random the channels it wants to become a switcher to.
Second, we provide a comprehensive set of simulations for OAZE in the case where the P2P IPTV system implements a gossip-based network-friendly topology management system. We show that OAZE significantly improves the quality of the initial peerlists. In practice, these improved peerlists allow to reduce the time to get the first video packets (bootstrap delay reduction) and to decrease the overall impact of the P2P IPTV system on the network. We focus on this latter point in our simulations. Our experiments are conducted over a realistic simulation environment where the network contains multiple ASes. We measure the reduction of the cross-domain traffic that can be expected from the integration of OAZE in an IPTV system. More specifically, we highlight the fact that the overall network cost (measured here as the number of traversed ASes) can be reduced by 10%.
The rest of this paper is organized as follows. Section 2 presents OAZE. Section 3 formulates and analyzes the channel assignment problem, and further presents our algorithms to create switchers. Section 4 reports on the set of simulations, evaluating OAZE using specific network settings. Section 5 concludes the paper.

Distributed switching systems and our approach OAZE
We assume an IPTV system consisting of a channels, each channel being a P2P overlay, which is modeled as a graph where the nodes are the peers and the edges represent the mutual knowledge of both peers. The set of all P2P overlays is also a graph noted G. A peer x is involved in exactly one channel among the a channels simultaneously offered by the IPTV service. In this P2P overlay, x cooperates with some peers, called overlay neighbors, with the exclusive goal of exchanging content related to its channel.
This small set of neighbors is noted C over ðxÞ. Furthermore, let d over ðx; yÞ denote an overlay distance that presents the hop-distance of the shortest path between a peer x and another peer y in the global graph G (with d over ðx; yÞ¼1if the channel of x is different from the channel of y). For any integer k > 0, let the k-neighborhood of x be C over ðxÞ k ¼fyj0 < d over ðx; yÞ 6 kg, where y is called k-neighbor of x.
OAZE is agnostic of the algorithms that are implemented for the P2P overlay, and it can be implemented over any P2P IPTV. However, OAZE is especially designed to fit with the characteristics of mesh-based P2P systems where a gossip algorithm makes that peers are eventually connected to their matching peers. Our assumption is that, in a given P2P overlay, the overlay neighborhood reflects the matching, in other words, for two integers k 1 and k 2 with k 1 < k 2 , if y 1 is a k 1 -neighbor of x and y 2 is a k 2 -neighbor of x, then it means that y 1 matches better with x than y 2 .
We also care on the impact of the P2P IPTV system on the underlying network. We call underlying distance between x and y the distance in the physical network between these two peers. The underlying distance can refer to the latency between x and y, the number of routing hops on the path or the number of AS hops. In this paper, we consider the underlying distance as the number of ASes traversed in the shortest path between x and y in the Internet. It is denoted as d AS ðx; yÞ. That is, d AS ðx; yÞ corresponds to the cross-domain traffic generated by any data transfer between x and y. We choose this definition of underlying distance because the cross-domain traffic represents an increasing concern for network operators.

Our proposal
A peer y is a contact peer of another peer x when y is not in the same overlay, but x ! y relation exists. We note C inter ðxÞ c the set of contact peers of x that are in the channel c. A peer x is requested to maintain fresh lists of contacts (dead nodes or nodes that switched are removed from contact lists), and to try to match with those contacts.
We associate with a peer x a set CðxÞ of channels such that a channel c belongs to CðxÞ if and only if there exists a peer y such that both y is in c and y 2 C inter ðxÞ c . We say that x is a switcher to c. Because the number of channels a is expected to be large, a peer cannot be a switcher to all other channels. For scalability issues, we bound by d the number of channels every peer can be a switcher. We depict the overall P2P overlay switching system in Fig. 1.
An overlay switch for a node x is the process leading to a complete change of its neighborhood C over ðxÞ, and to another one reflecting its move to a new chosen channel. Say that a peer x in c i wants to switch to a channel c j ;w e describe now the two ways to switch overlays. First, the k-neighborhood of peer x contains a peer y, which is a switcher to c j , thus c 2CðyÞ and y 2 C over ðxÞ k .
Search could be implemented through basic expanding ring search technique, at k hops, from the requesting peer.
A peer only has to ask y for its contact list from c j , update its neighborhood with these peers, and join the targeted channel. Note that, if both P2P overlays c i and c j implement the same matching preference system (say peers choose preferentially their neighbors in their own AS), the contact peers of y are close to y, and y is close to x, so there is good chance that the contact peers of y are close to x too. This will speed up the convergence process. The second scenario is simply a failure in searching distributively a contact peer for the targeted overlay. It can occur either because no switcher is accessible at k hops, or because the chosen channel is not an adjacent one. In such a case, the traditional centralized approach is used to get the initial peerlist. Note that in IPTV, servers are mandatory, as they are also in charge of pushing the content into overlays, and to serve as initial bootstraps for the IPTV service.

Main algorithms
Mesh-based P2P overlays use gossip algorithms to ensure that the topology conforms a preference system.I n the literature related with such gossip-based topology management systems, it has been shown that it is important to exchange a list of peers not only with the overlay neighbors, but also with peers that have been randomly chosen in the P2P overlay. Typically, in the T-man system, only a few cycles are needed to reach a near optimal peer matching, even in presence of churn [8]. The random peers needed by the algorithm are provided by a peer sampling protocol. It has also been shown that the gossip paradigm can implement efficient peer sampling protocols, see e.g. Cyclon [22] or the Peer Sampling Service [23].
We distinguish two classes of preference systems. In a global preference system, each peer can be associated with a unique value reflecting a quality metric, and therefore two neighbors can be compared by a simple distance computation. In a local preference system, each peer ranks other peers from its own point of view (e.g. network latency). In OAZE, peers use the same preference system for the management of both their overlay neighbors C over , and their contact neighbors C inter , except that this procedure is not bidirectional (the switcher tries to match with peers in target overlay, but the reverse case may not be true). With this matching process, once a peer wants to switch, and is able to find a switcher in its k-neighborhood, the contact peers provided by the switcher have a high chance to be close from its future position in the new channel.

Algorithm 1. The OAZE algorithm
Initially: upon IPTV join of a node x in channel c i 1: arbitrarily fixed input: k (depth of switcher search) 2: request server c i that returns a peerlist C over ðxÞ Matching for x in current channel: 3: stabilization and convergence toward matched C inter ðyÞ c j becomes C over ðxÞ 11: else 12: request server c j that returns a peerlist C over ðxÞ 13: goto line 3 We present in Algorithm 1 a global description of OAZE. This algorithm contains two key algorithms: the channel assignment algorithm and the switcher lookup algorithm. This latter returns a switcher to a channel if there exists one in the k-neighborhood. Various classic algorithms can be implemented (e.g. flooding with increasing depth). We now focus on the channel assignment algorithm, because it is a critical component of OAZE.

Channel assignment
In this Section, we analyze the problem of assigning a set of channels to peers so that every channel is easy to be accessed from every peer. Note that, this problem applies when a small set of resources should be distributed Fig. 1. An example of a resulting system G. Node x has 4 neighbors in its current overlay ci (dashed lines) and 2 contacts in other overlays, d ¼ 2 (plain lines). Node x is a switcher to channels c h and cx. If one of its direct neighbors in overlay c i wants to switch to either c h or cx, it can leverage x to discover matching and active peers in this overlay. among a large set of peers. Hence, this analysis presents a scientific interest that goes beyond the performances of OAZE.
We illustrate the problem in Fig. 2, where six nodes (1, 3, 4, 7, 8 and 11) form an overlay network for the channel a, two nodes (2 and 9) in channel b, two nodes (5 and 10) in channel c and node 6 in channel d. We represent the linkage in underlay network on the bottom, and the channel assignment for the channel a on the top.
This channel assignment has a drawback: the two direct overlay neighbors of node 11 are switchers to the same channel b. Therefore, for k equal to one, the node 11 is unable to discover a switcher to c. We derive from this failed assignment the main objective of a channel assignment algorithm, which is to maximize the number of distinct channels for which there exists a switcher in the k-neighborhood of every peer. This is objective 1.
Let us now observe the case of node 1, when k is equal to two. If this node wants to switch to channel b, two switchers can be used: nodes 4 and 8. The node 4 is the ideal switcher to channel b because node 4 is close to node 1 in the underlying network. If switchers are connected to their matching contact peers in channel b, node 4 would be able to introduce node 1 to node 2, which is its matching peer in channel b. We derive another definition of the assignment objective, which is to minimize the underlying distance to a switcher to every channel. This is objective 2.

Maximizing the number of channels in k-neighborhood is NP-hard
We first show that the problem defined with objective 1 is NP-hard. In domination theory [24], a set D # V of vertices in a graph ðV; EÞ is called a dominating set if, for every vertex x in V; x is either an element of D or is adjacent to an element of D. More generally, a k-dominating set extends this adjacency notion at k hops, at most, from a given peer x. Consider that at most d resources (here channels to be switcher to) can be allocated to a node. A d-configuration is an allocation of a set of resources such that, for every resource, the vertices associated with this resource form a dominating set. The same extension as in previous definitions can state for a d-configuration. That is, a ðd; kÞ-configuration is to allocate resources to vertices, such that no more than d different resources are allocated to any vertex, and each vertex can access a resource associated with another vertex in less than k hops. Applied to the switcher creation context, the resources are channels, nodes associated with a given resource are switchers for this channel.
Unfortunately the decision problem associated with the ðd; kÞ-configuration is NP-complete. All optimization problems that are directly related to this decision problem are NP-hard. The ðd; kÞ-configuration problem is the problem of assigning channels to peers so that every peer has a switcher for all channels in its k-neighborhood. This NPhardness result makes that maximizing the number of channels a that can be allocated, with a given d and a given k is NP-hard, as well as minimizing the number of switcher peers d for a given k and a given a. Therefore, an optimal solution cannot reasonably be computed in a large-scale system.

Our formulation of the channel assignment problem
We propose a slightly different formulation of the problem, which combines both objectives 1 and 2, but neglects the parameter k. We focus on assigning channels so that we minimize a distance from every peer to its closest switchers. Here, the distance, noted d, is a generic notion, which can be associated with the overlay distance d over (if the objective is actually to reduce the overlay distance between a peer and its switchers) or with the underlying network distance d AS (if the objective is to build a network-friendly P2P IPTV system), or with any mix of both distances.
The rainbow distance for a peer x is the sum of the distances from x to the closest peers hosting collectively the a adjacent channels. We denote by dðxÞ the rainbow distance of a peer x. The goal is to reduce the sum of all rainbow distances. In other words, we want to minimize the average distance for each peer x to access a switcher for every adjacent channel. Let V be the set of peers in a given channel. Let note by G adj the a adjacent channels of this channel. The goal is to determine an allocation C from adjacent channels to peers such that: X x2V X c2G adj min dðx; yÞ : x 2 V; c 2CðyÞ fg : This problem is closely related with a variant of Facility Location Problems, namely the a-Product Uncapacitated Facility Location Problem (a-PUFLP). In this problem, we have a set of facilities and a set of clients. Each client has an access cost to retrieve the service deployed at any facility. In this variant, the service consists of a distinct products. The objective is to open a subset of the facilities and to satisfy all demands of clients so that the total cost is minimized. Few papers have dealt with this NP-complete problem [25][26][27]. An approximate solution has been proposed, where the solution is at most 3 2 a À 1 times the optimal one [28]. To some extent, our problem can be seen as a sub-problem of a-PUFLP as it is possible to transform any instance of our channel assignment problem into an instance of a-PUFLP. Indeed, every peer can be seen as both a facility and a client with a null access cost between them.
Please note that this problem is for one channel, and the algorithm should be applied to every channel in the P2P IPTV system. Please finally note that, when d > 1, we regard one peer as d peers located at the same place. Therefore, in the following subsections, we only consider the case where d ¼ 1.

Distributed approximate algorithm
We first present a distributed algorithm that computes a channel assignment with guaranteed performances. This algorithm computes from scratch a full assignment, and it should be executed by all peers. Therefore, in practice, this algorithm does not cope with dynamic systems. In a controlled environment, this algorithm can be executed on a periodic basis in order to refresh the assignment.
We introduce some additional notations. From now on, the nodes that serve a peer x (i.e. the switchers to every channel that are the closest to x) are noted FðxÞ. Besides, the a À 1 nearest neighbors of a peer x are noted NðxÞ, while N½x¼NðxÞ[fxg. Moreover, we denote by NðxÞ 2 the union of the a À 1 nearest neighbors of x and their respective a À 1 nearest neighbors. Note that, in an ideal scenario, FðxÞ¼N½x but this solution is sometimes impossible.
We compute a fractional optimal solution, an impossible solution, which gives a lower bound of the optimal solution. We cut each channel into a fractional pieces. Then, we form the fractional optimal solution S by assigning to each x in V a fraction 1 a of all the channels. Therefore, each peer can have an access to any channel c by retrieving a fraction of c to itself, and the remaining cÀ1 c fractions from its a À 1 nearest nodes in the overlay. The solution S is a fractional optimal solution because the sum of fractions assigned to each node is equal to 1 and all channels can be accessed from itself and some neighbors in the overlay, that is, FðxÞ¼N½x. We denote the rainbow distance of a node x in the solution S as d x . Our distributed algorithm is inspired by Li and Li [28]. Details are given in Algorithm 2. The main idea is that every peer tries to optimally assign channels to their nearest peers and themselves. In order to avoid that two peers assign a channel to the same peer simultaneously, each peer x initially exchanges information with all peers in NðxÞ 2 (lines 1-2). Then, these 2-hop neighbors are sorted in increasing optimal rainbow distance d order (line 3). Once x has received messages from all peers in NðxÞ 2 , it enters in waiting mode.

Algorithm 2. Approximate Algorithm for Channel Assignment (node x)
Initially: 1: determine NðxÞ 2 , compute the optimal rainbow distance d x 2: broadcast d x to every peer in NðxÞ 2 3: create a list LðxÞ containing all peers in NðxÞ 2 sorted in increasing rainbow distance order 4: enter waiting mode In waiting mode: 5: upon reception of a release message from a node y 6: discard y from LðxÞ 7: if x is the first peer in LðxÞ then 8: let C toAssign ¼ G a 9: let N toAssign be all peers in N½x without any assigned channel 10: for all nodes y in N½xnN toAssign do 11: remove CðyÞ from C toAssign 12: if cardðN toAssign Þ¼card C toAssign ÀÁ then 13: assign channels in C toAssign to peers in N toAssign such that no pair of peers are assigned the same channel 14: broadcast release message to every peer in NðxÞ 2 15: enter in final mode. In final mode: 16: upon reception of a release message from a node y 17: discard y from LðxÞ 18: if LðxÞ is empty and no channel is assigned then 19: assign to x the channel whose closest switcher is the farthest among all channels The peers with minimal optimal rainbow distance among their 2-hops nearest neighbors execute the algorithm first (lines 5-7). When a peer cannot produce a local optimal assignment, it leaves itself unassigned. Such a configuration occurs when at least two peers among the a À 1 nearest neighbors have already been assigned the same channel. Otherwise a peer assigns channels to all its unassigned nearest neighbors and itself (lines 8-13). Finally, a peer sends a release message and enters in final mode.
In the final mode, some peers may be still unassigned. It means that neither they, nor their nearest neighbors were able to optimally assign channels. In this case, a peer assigns itself the channel that is the farthest (lines 18-19). Theorem 1. For any a P 3, Algorithm 2 gives an integer solution no more than 3 2 a À 5 2 times of the fractional optimal solution for the Channel Assignment Problem.
Proof. For every optimized peer x, we know that d x ¼ d x . When x cannot be optimized after the waiting mode,w e distinguish two cases.
In the first case, the channel on x has been assigned by an optimized peer x 0 2 NðxÞ, but this channel conflicts with the channel hold by another peer in NðxÞ. Since x 0 was in waiting mode before x, we know that d x 0 < d x .Asx 0 has been optimized, all channels are assigned among its nearest neighbors. Assume that the channel on x is c 1 . For the node x, a way to reach every other channel c 2 ; ...; c a is to use the neighbors of x 0 . Let note y i the node in N½x that has been assigned channel c i , for 2 6 i 6 a. We have: Since the distance dðx 0 ; xÞ is one of the ða À 1Þ distances that are part of the rainbow distance of x 0 , we have dðx; x 0 Þ 6 d x 0 . We also know that d x 0 < d x , therefore, we obtain: In the second case, two nodes in NðxÞ, say y and y 0 , have been assigned the same channel. Since these nodes hold a channel, there exists an optimized node x 0 at 2 hops from x, with d x 0 < d x . Assume without loss of generality that y and y 0 have the channel c 1 and that dðx; yÞ 6 dðx; y 0 Þ. After the final mode, the peer x picks a channel, say c a , that is different from c 1 because c 1 is not the farthest channel to access for x. Let y be in NðxÞ\Nðx 0 Þ.
When all peers are assigned a channel, since x and y are assigned a different channel, node y is included in FðxÞ.We use the same idea as in the previous case to express the rainbow distance of the node x as the sum of the distance from x to x 0 plus the rainbow distance of x 0 X y2FðxÞ dðx; yÞ 6 dðx; yÞþða À 2Þ dðx; yÞþdðy; x 0 Þ ðÞ þ X aÀ1 Since dðy; x 0 Þ is part of the rainbow distance of x 0 ,w e have dðy; x 0 Þ 6 d x 0 , and therefore ða À 3Þdðy; x 0 Þþ d x 0 is lesser than or equal to ða À 2Þ d x 0 . Moreover, since dðx; yÞ < dðx; y 0 Þ and both distances are parts of the optimal rainbow distance d As a À 1 6 3 2 a À 5 2 ÀÁ for any a greater than 3, then Algorithm 2 gives an integer solution no more than 3 2 a À 5 2 times the fractional optimal solution. h

Practical algorithms
The advantages of Algorithm 2 include its guaranteed performances. However, all peers in the overlay should execute the algorithm simultaneously. We propose two simpler algorithms, which can be executed by any peer at any time. However, their performances are not guaranteed.
In the first algorithm, every peer selects the channel whose switcher is the farthest from itself, and it assigns this channel to itself. We call this algorithm delta-k because a peer explores its nearest neighbors by increasing flooding.
In the second algorithm, which is the simplest one, every peer assigns to itself a channel that is randomly picked among the adjacent channels.

Comparative simulations
This first set of simulations aims to evaluate the distinct algorithms and to determine the best choice for the remaining of the paper. These simulations are in three parts, which correspond to three distinct scenarios. We had 1000 peers, which were randomly located in 200 different ASes. We used a real Internet map, and the inter-AS distance was measured by a technique that is detailed in Section 4. The number of adjacent channels was fixed at 15. All results are given in Fig. 3.
In the first scenario, we did not take into account the overlay. The distance d only depended on the AS distance between peers. This simulation corresponds to the scenarios where the number of peers in every channel is not large, or when the number of overlay neighbors is larger than the number of channels. The results for this scenario are figured as x-Algo where Algo can be Rand for the random algorithm, delta for the delta-k algorithm, and approx for the approximate algorithm.
We compared the average distance to the closest switcher to every channel for the three algorithms. Both approximate and delta-k algorithms outperform the random algorithm (more than 15% of gains). Moreover, we show that delta-k performs approximately as well as the approximate algorithm, despite it can be executed asynchronously.
In the second and the third scenarios, we took into account an overlay. The average overlay degree was fixed at 5. For both scenarios, the approximate algorithm was built as follows: every peer selected its a À 1 nearest neighbors in terms of AS distance among the peers in its 3-neighborhood. For the delta-k algorithm, the peer explored its neighborhood until it found switchers to all channels, then it assigned the channel that was the farthest in term of AS distance.
In the second scenario, the overlay was built at random. It is the worst case where the P2P IPTV system does not incorporate any network-friendly mechanism. The results are indicated with R (for random overlay) as a prefix. First, the average distance to switchers is more than three times larger than when no overlay constrains peer mutual knowledge. Then we can observe the differences among the algorithms. The approximate algorithm outperforms by more than 10% both random and delta-k algorithms, which have almost the same performances. The main indication of this set of simulations is that no channel assignment algorithm provides any significant gain in term of network-friendliness when the P2P IPTV system does not incorporate any network-friendly process.
In the third scenario, the overlay was built by a perfect network-friendly process so that the overlay was a 5-nearest neighbor graph in the AS distance. Despite the low average degree, this scenario corresponds to a configuration where we can expect good results from the OAZE system. Here, the results indicate that the approximate algorithm is approximately 10% better than the delta-k algorithm, which is also approximately 10% better than a random choice.

Discussion
The results we obtained from these simulations (based on representative ''toy-networks'') do not convince us to implement the approximate algorithm in our main simulations. Approximately 15% of expected gains do not appear to be important enough to justify the implementation of an algorithm that requires a global synchronisation from all peers. Therefore, in the following, we will use this delta-k algorithm in our OAZE proposal.

Simulations using an AS Map
We evaluated our OAZE proposal using the PeerSim simulator [29]. The multi-channel system we implemented as an input conformed recent application measurements conducted in [2]. The aim of this section is to put light on the benefits, considering the cross-domain traffic, that could be awaited from OAZE if implemented in a meshbased P2P streaming system having a gossip-based topology management.

Local preference system based on AS distance
We first explain our implementation of the local preference system based on the AS distance between peers. This preference system was a pre-calculated N Â N matrix. Each line of this matrix defines the preference rank of all other peers with respect to one peer. A small value at point ðx; yÞ stands for a high attractivity for peer x to be matched with y.
We adopted the AS level hop count as the rank value. These hop counts were calculated using the CAIDA dataset [30], a widely adopted trace representing a realistic view of Internet at the AS level. This dataset contains 28; 421 ASes and their type of relationship (peering or transit). Two ASes AS1 and AS2 have a transit relationship if AS1 transits the traffic from AS2 and charges AS2. The transit, which is a provider-customer relationship, is commonly observed between big and small ASes, as small ASes need big ones to be connected to the Internet. In the second type of relationship, peering, a settlement is negotiated between AS1 and AS2 so that they can exchange traffic for free. This generally happens between two ASes of same size and importance.
We followed the algorithm given in [31] to compute the relationship-based routing distance on top of this dataset. When an AS receives a routing request, it takes a local decision for next hop (often called a greedy decision) based on its relationship with the neighboring ASes. The request is forwarded in decreasing preference order to: (i) customer AS, (ii) peering AS, (iii) provider AS. Note that a route is not necessarily used both ways, so the matrix is asymetric. Fig. 4 shows the hop-distribution between ASes in the distance matrix. We observe that the distribution of distances between ASes is not uniform. Most of the ASes are located from 6 to 11 hops from each other, while the distance is significantly higher for some other fractions of ASes.
This knowledge on AS relationship allows us to obtain a finer grained estimation of the impact of our approach on the network cost. Peers now construct and update their sets of overlay neighbors C over and contact peers C inter by preferring neighbors with the smallest AS distances available. The goal is to reduce the whole cross-domain traffic, and more specifically the transit traffic because it implies financial transactions.

Simulation configuration
We considered a 150 channel system. According to the measurements of [2], channels belonged to one of 13 genres (e.g. cine, sports, kids, docu). Channel popularity in each genre followed a Zipf distribution, that decays fast for non-popular channels. The probability of a peer to remain in the same genre during a switch was set to 76% [2,3]. Otherwise, a peer picked uniformly at random first the genre it switched to (probabilities are exposed in [2]), and then the channel in that genre. Fig. 5 shows the number of channel switching for each pair (initial channel, destination channel). We observe different peaks on the figure. Since the channels are grouped in genre by their identifier (from 0 to 149), switching to a channel of the same genre means also switching to a channel with an adjacent identifier. Therefore, most peaks are located close to the diagonal of xy-plane.
Each simulation ran for 5000 cycles. A PeerSim cycle execution corresponded approximately to a dozen of seconds in a real system. According to the time peers watched channels, peers get assigned a role: surfer (stays at the same channel from 5 to 20 cycles), viewer , leaver (200-500). Joining and departing peers created the dynamism (or churn) in the system. After each channel switch, a peer picked a role with probability 0:6 for surfer, 0:35 for viewer and 0:05 for leaver.
Other simulation parameters were set as follows: 20,000 peers in the system were distributed in 1000 distinct ASes (so, an average of 20 peers per AS). These 1000 ASes were randomly selected among all 28,421 ASes in the dataset. Every peer x had a channel-neighborhood C over ðxÞ of size b. A peer was a switcher for simply one channel (d ¼ 1), and was connected to 6 peers in this channel for C inter . We added a parameter, l, that controlled the percentage of peers (1=l) that were performing the gossip protocols (matching and sampling) at each cycle.
We explored parameter space of l and b to generate two scenarios: an overlay that quickly converged toward a stable state, where neighboring peers matched (here, l ¼ 4; b ¼ 60), and a slow-converging overlay (with . This is typically of interest for network operators willing to keep some control on the traffic cost, implied by more or less ''aggressive'' P2P applications.

Uses of the distributed zapping
At first, we counted the number of times the zapping used our distributed system in comparison to the number of times the central server were used. In Fig. 6, the x-axis represents various search depths k allowed to find a switcher. In this simulation, the number of overlay neighbors b, was equal to 20. The ratio of distributed zapping cannot be above 76% for the reason that the 10 adjacent channels represented only 76% of the switch in our simulation, so some zaps must be treated by the central server.   When k ¼ 0, the search was limited to the peer itself: distributed zapping was possible only if the peer wanted to switch to the channel corresponding to its own C inter .
In this specific case, the number of zaps that require a request to the server is much higher than the number of zaps using OAZE. With the increase of search depth, distributed zapping becomes dominant. The deeper is the switcher lookup, the more channel switches use OAZE.
We also observe that the number of distributed zapping remains almost unchanged between k = 2 and k = 4. This result highlights that it is possible to find a switcher for most channels at less than three hops. At k ¼ 4, OAZE obtains this best achievable result in this specific configuration. However, using a smaller value of k (especially k ¼ 2 here) is enough to satisfy a large majority of zaps. Therefore, it is possible to use less costly 2-hops search, or to increase the number of adjacent channels if one can support a 4-hops search.

Impact of switcher distance on the quality of contact peers
We now evaluate the quality of the peerset that is provided by a switcher depending on the distance between the peer and the switcher. We note Q i ðxÞ the set of peers that are located at a AS distance exactly i from a peer x, that is, Q i ðxÞ¼fy; d AS ðx; yÞ¼ig. We computed the average distance between x and the peers that are the contact peers of all peers y in Q i ðxÞ. This measurement aims at determining the average distance of the contact peers that are provided by a switcher located at i AS-hops from x. Results are shown in Fig. 7. The x-axis is the AS distance to the switcher, while the y-axis is the average number of AS hops on the route from x to the closest contact peers of switcher at this distance.
As expected, the farther is the switcher, the farther is the contact peer. But some other observations give insights on the characteristics of the inter-AS routing. The transit distance increases surprisingly only until the distance to the switcher is eight, then the transit distance decreases. In other words, the financial gain on the overall traffic is only interesting if the switcher is close to the switching peer.
We also remark that the overall cost quickly increases. For example, a switcher at a distance five gives a contact peers with which the traffic is two times more costly than if the switcher was the peer itself. This result also suggests that the contact node should be selected preferentially in nearby ASes (typically in a AS at less than five hops of the peer).
We have not implemented any mechanism aiming at limiting the contact search process when the distance from the peer is more than a given threshold, but this result highlights that such a limitation may be an interesting future work to explore.

Distributed zapping efficiency
We now compare the efficiency of distributed and centralized zapping by observing peers' neighborhood C over right after each channel switching. We aim at measuring optimality in terms of network distance, this value is the ratio of the sum of distances between a peer and its current neighbors at time t, noted C over t , over the optimal neighborhood C over opt , which is the set of nearest peers in the overlay. This neighborhood distance ratio (NDR) of a node x is thus computed by: NDRðxÞ¼ P y2C over t ðxÞ d AS ðx; yÞ P y2C over opt ðxÞ d AS ðx; yÞ : Fig. 8 plots the NDR as a function of time after switch, for two types of settings. We averaged all switches that occur during the whole simulation: t ¼ 1 represents the first cycle after switch. We remark that NDR has a high initial value, because of the imperfect neighborhood initially obtained. For centralized zapping, since the cache overlay C over is randomly constructed after the zapping (given by the server), The NDR is high. On the contrary, using distributed zapping, the initial C over is built using the C over of the switcher in C inter . These initial contact peers are closer to the switching peer.  We now want to measure the gain provided by the distributed zapping in comparison to a classic centralized one. For the Fig. 9, we computed the ratio of the average distance to contact peers obtained from a distributed zap to the average distance to contact peers in a centralized zap: P y2C over Distributed ðxÞ d AS ðx; yÞ P y2C over Centralized ðxÞ d AS ðx; yÞ Moreover, we used different values of the switcher lookup depth k, from k =0 to k = 2. Thus, we are able to estimate the expected cost saving by using distributed zapping. This figure shows that this ratio is strictly less than one; distributed zapping reduces the peering traffic by 40-90%, and transit traffic by 20-40%, at the time right after the zapping. Then both distributed and centralized methods converge to stable settings because the preference system allows to refresh the neighborhood, so the improvement becomes less significant. Note however that recent measurements have highlighted the high number of peers who switch very frequently between channels. Thus, a watcher is likely to zap before the convergence process ends.
4.6. Global cost of the P2P-TV system Finally, we evaluated both distributed and centralized zapping costs from a global point of view. First, we measured the number of handshakes for all peers during the entire simulation. A handshake is a change in neighborhood C over , so that the peer should establish a connection to a new neighbor. As we pointed out earlier in the paper, handshakes are costly in terms of time, so they may affect the playback delay of the channel content. We observe in Table 1 that distributed zapping leads to a reduction of the number of handshakes. Since contact peers provided by OAZE are more likely to be matching peers (or peers that are close to matching peers), a switching peers need less handshakes to reach a stable neighborhood.
Secondly, we computed the overall network cost of the system, which is the total network traffic during the whole simulation (still in Table 1). The overall cost is defined as X 8x2V X t2½0;T X y2C over t ðxÞ d AS ðx; yÞ: We can remark that distributed channel switching achieves less peering and transit costs. The system using distributed zapping has reduced the total cost by more than 10% in a slow-converging case.

Summary
Here are our conclusions from these simulations results: Distributed channel switching provides better initial peerset for a switching peer. The average distance to the contact peers is at worst less than two times the optimal although it is more than three for centralized switching. Distributed switching significantly reduces both peering and transit costs. This has a practical interest for a network operator managing a P2P IPTV system to reduce the network costs. This reduction on network traffic depends on the convergence time of the matching between peers at the overlay scale; higher cost saving can be achieved when a less aggressive peer matching (a longer one) is achieved by the application.  We have demonstrated here the advantage of using a distributed channel switching system like OAZE: a better initial peer set provides less network traffic and decreases the overall cost. Better results can be obtained. For example peers can select several channels (d > 1), so that the probability to find a nearby switcher becomes higher. Choosing switchers only if they are close to the switching peer appears to be another promising way to improve overall performances.

Conclusion
In this paper, we addressed the problem of efficiently switching from one channel to another in P2P IPTV systems, in a distributed fashion. It has been show in literature that initial steps executed by a switching mechanism are crucial for the watcher's experience (reduced delays). To the best of our knowledge, no previous studies have dealt with scalable channel switching, which is a crucial issue for the next generation of multimedia delivery mechanisms over Internet. This approach shows the interest of leveraging peers' belonging to an overlay, in order to improve forthcoming switches. The algorithm proposed in this paper represents a first step toward the design of distributed and efficient switching mechanisms.


OntoPop: An Ontology Population System for the Semantic Web

SUMMARY The development of ontology at the instance level requires the extraction of the terms deﬁning the instances from various data sources. These instances then are linked to the concepts of the ontology, and re- lationships are created between these instances for the next step. However, before establishing links among data, ontology engineers must clas- sify terms or instances from a web document into an ontology concept. The tool for help ontology engineer in this task is called ontology popu- lation. The present research is not suitable for ontology development applications, such as long time processing or analyzing large or noisy data sets. OntoPop system introduces a methodology to solve these problems, which comprises two parts. First, we select meaningful features from syn- tactic relations, which can produce more signiﬁcant features than any other method. Second, we di ﬀ erentiate feature meaning and reduce noise based on latent semantic analysis. Experimental evaluation demonstrates that the OntoPop works well, signiﬁcantly out-performing the accuracy of 49.64%, a learning accuracy of 76.93%, and executes time of 5.46 second / instance.

Introduction
The Semantic Web employs a knowledge base description known as ontology. The creation and development of ontology is a sub topic in knowledge engineering, called ontology engineering. Ontology engineering divides ontology into three levels [1]. The first level, the knowledge representation level, is to prescribe representations for ontological elements such as class, relation, property and so on. To create ontology at this level, an accepted standard must be used so that all the processing is compatible. At present, the development of ontology at this level has produced some standard languages such as RDF or OWL. At the second level, the ontology concept level, generic or universal concepts are defined and classified in the form of a hierarchy, such as "island is a subclass of location", relations between concepts, such as "island located in country". The third level, the ontology instance level, specifies the instances of each concept; for instance, the concept "island" has the instances "Phuket" and "Maldives", and the concept "country" has the instance "Thailand". To link instances together, relations must be defined, such as "Phuket located in Thailand". The development of ontology at the instance level requires the extraction of the terms defining the instances from various data sources, including unstructured documents, semi- structured documents, and structured documents. These instances then are mapped to the concepts of the ontology, and relationships are created between these instances for the next step. However, the first step is very important to the development of ontology because it allows the use of derived knowledge for ontology development applications. If there are many data sources, the result is a large ontology, which can cause difficulties and require more time for developers [2]. By employing appropriate tools and architecture, the developer can reduce the complexity and time. Current research toward solving this problem is called ontology population. Ontology population is a new field in the application of knowledge acquisition [3], with the goal of creating a tool to help humans with the development of ontology. In general, the field of ontology population comprises two working parts: instance detection and instance classification. Instance detection consists of extracting likely instances from unstructured documents, while instance classification is gathering all instances to be classified into an ontology concept. Ontology population is similar to named entity recognition and classification (NERC). The difference between the two is that ontology population emphasizes concepts at a more specific level. NERC does not categorize many classes (such as person, location, organization, GPE, and miscellaneous). Current research on ontology population could solve problems with a larger number of concepts and further expand NERC research. Current ontology population research can be divided into three groups. The first group is based on lexicosyntactic pattern [4]- [6] that counts the number of generated patterns in documents and classifies an instance into the most frequently occurring ontology concept. For instance, "the Niger river" is found more often in documents than "the Niger country", so "Niger" would be classified under the river concept. However, this method can be misleading if an instance is new or is not often mentioned. This approach leads to an incorrect classification concept. The second group is similarity-based classification [7], [8]. This method compares the context of an instance (such as "Everest") and the context of a concept (such as mountain). If they have similar context, the instance will be classified into the ontology concept. However, this technique cannot solve the problem that the context of a concept may be different from the context of the instance [3]. For example, the "mountain" concept may feature in the phrase "mountain sports" or "mountain shoes" but the instance is unlikely to occur in "Everest sports" or "Everest shoes". The last group is the supervised approach [3]. The weaknesses of this technique include lack of support for fine-grained classification and a classification model that is too large for ontology development applications.
We proposed methodology to improve the weaknesses of these three techniques with a new system called OntoPop. The proposed system consists of a bootstrapping process that automatically creates the classification model by extracting the features in syntactic relations to obtain context that is most relevant to the ontology concept. This approach places more importance on context meaning than the lexicosyntactic pattern technique. Furthermore, we also apply latent semantic analysis (LSA) to distinguish feature meanings, reduce noise, and truncate the classification model size while retaining classification effectiveness. The proposed methodology supports fine-grained classification, semantic annotation, and dimension reduction, so it is more easily applied in ontology development applications. The next section summarizes the related work in this area. Section 3 summarizes OntoPop system architecture, while Sects. 4 and 5 describe the details of the system components. Section 6 presents the experiment and evaluation of our proposed system. Section 7 describe the detail of the implementation. Finally, Sect. 8 concludes the paper and offers suggestions for future research.

Related Work
The previous works at the current period can be divided into three groups. The first group of research is based on lexico-syntactic pattern technique. The basis of this work is to find the frequency of an emerging pattern in the collection of documents. The research of this group is often based on the Hearst pattern [9] such as PANKOW [4] and C-PANKOW [5]. The Hearst pattern is formatted as "[concept] such as [instance]", or "the [instance] [concept]". An example of applying PANKOW is to make a pattern for instance of "Niger" from the country concept such as "Niger such as country", and "the Niger country", and a river concept such as "Niger such as river", or "the Niger river". Next, the pattern is queried by a search engine, and the frequency of the pattern is counted from the number of hits returned from searched documents. The pattern of concept with highest number of hits is regarded as concept of that instance. C-PANKOW is an extended system from PANKOW. This system makes a pattern which has only an instance name "such as Hilton", and is sent for query at search engine. The result snippet is then considered with the regular expression rule such as "[concept] such as ([instance],?)+ ((and|or) [instance])?" When the snippet corresponds with the rule, it will show which word in what position is the name of the concept, such as "hotels such as the Ritz, the Hilton and the Holiday Inn." Ritz, Hilton, and Holiday Inn in the sentence that can match is regarded as the hotel concept. The weakness of this research group is the processing time. If there are a lot of concepts in the ontology, it would require a lot of patterns to be sent for query. It makes the processing time very slow. On the other hand to our methodology, bootstrapping processes are proposed to be used to accumulate the information of each concept in ontology and the model must be completely formed before instance classifications. This method effectively helps reduce the processing time.
The second research group is a similarity-based classification technique. This technique is to create context vector of every ontology concept. When need to classified an unknown instance, a context vector of that unknown instance is created to compare with the context vector of every concept. The comparison is to take the dot product of two vectors, whose derived similarity value to be used in classification. Each research in this group varies in methodology in extracting context to create context vector such as Alfonseca et al. [8] creating a context vector from four signatures: topic signature is word that occurs in the same sentence, subject signature is verb, object signature is verb and preposition, and modifier signature is adjective and determiner. It is based on the principle: "if two words are semantically related, their signatures will also be similar." Collecting words from these signatures is done by sending concept or instance to a search engine, access the content, count word frequency, and transformed it into weight by Xi 2 [10]. An example of person concept with the highest weight in topic signature is "chromosome", "department", and "human". For subject signatures are "work", "kill", and "write". Cimiano et al. [7] is another work in this group that extracts different contexts using pseudo-syntactic dependencies. Context extraction is done by creating rule in regular expression. These are examples of context that matches the city concept rule: "a nice city" whose context is "nice", "the city's center" whose context is "has center", or "a city near the river" whose context is "near river". Context vector is created by counting context frequency and then transformed into weight before being compared with an unknown instance to be classified into an ontology concept.
The research in the third group employs a supervised approach which considers classification from training data. This technique employs ontology engineer to specify a training instance of each ontology concept before creating a classification model. An example of such technique is found in the work of Tanev et al. [3] which propose a method called Class-Example by manually specifying each instance of the ontology concept in order to find related context and create the context vector for classification. Creating a context vector is done by counting frequency of each context, weighed, and compared with context vector of every training instance using dot product as in similarity-based classification for assigning an unknown instance into the ontology concept.
It was found that the there were inaccurate classifications in methods of the second group and the third group in feature occurring of synonym or polysemy. That is, the context of instances of synonyms is classified in different concepts, while they should be in the same concept. In addition, the context of some instances of polysemy is classified under the same concept, while they should be in different concepts. As seen, we have applied LSA to solve this prob-lem. It can effectively help solve the problem in information retrieval [11]. We will be further explained in the Sect. 4.2.
Some parts of our work are similar to those of Liu et al. [12]; however, they are considerably different. In regards to fields, Liu et al.'s methodology was in the field of text classification which focuses mainly on general words, but our approach is in the field of knowledge acquisition, which is more specific than the method of Liu et al. Our approach concentrates on the construction of facts or instances for ontology and the creation of the Semantic Web. Moreover, feature extraction is also different. Our method analyzes the context of instances by looking at grammatical relationships, while the methodology of Liu et al. analyzes the context of instances by using information entropy.

OntoPop System Architecture
OntoPop system architecture as shown in Fig. 1. The architecture has been divided into two main processes: bootstrapping and knowledge acquisition. The input of the bootstrapping process is an input ontology contained instances in each concepts that we call training instances, while the output is the LSA space. The components of this process are syntactic feature extraction, and LSA processing. The syntactic feature extraction starts by retrieving the sentences that contain training instances from Wikipedia database † , e.g., "Fiji is an island in the pacific ocean." After that, the sentence will parse and extract the syntactic features that are the output of this component. For example, the syntactic features of "Fiji" are "island" and "ocean". The next component is the LSA processing, which is the semantic processing using the syntactic features from all training instances. The output of this component is the LSA space, which is the model for classifying unknown instances in the next process.
The input of the knowledge acquisition process is a web document that is used to populate instances into the input ontology. The output are the populated ontology and the Semantic Web. The components of this process are instance detection, instance classification, and semantic annotation. The first step is instance detection, detecting possible in- stances from the web document. The output of this component is the unknown instance, e.g., "Phuket", "Ionion". The second component is the instance classification, using the LSA space from the bootstrapping process to assign an unknown instance to an ontology concept. The output of this component is a concept name for each unknown instance, e.g., "Phuket" is an island, or "Ionion" is a sea. Afterwards, the system will assign concepts to instances and update the input ontology. The input ontology that is updated in the instance level is called the populated ontology. This is the first output of the knowledge acquisition process. The last component is the semantic annotation that inserts metadata to web documents, identifying all instances of the ontology concepts. The result of this component is the Semantic Web that is the second output of the knowledge acquisition process.
The bootstrapping process has one initial stage, until the input ontology is updated, while the knowledge acquisition is an iterative process.

Syntactic Feature Extraction
The goal of this stage is the extraction of terms related to the training instance. Training instance is an instance that obtained from input ontology. The syntactic feature extraction component extracts terms by considering their syntactic relation in a sentence. We apply the Stanford Parser [13] to parse sentences into syntactic relation form. An example of such a relation is Fig. 2. It shows the dependency relationship in an asymmetric binary relationship, which is a relation between two words called the head (or governor) and the modifier (or dependent) [14], where the modifier of one word can be the head of another word. Extracting the instance context from other techniques produces unrelated terms. Therefore, we mitigate this problem by selecting only two features from the chain, i.e., first order features and second order features. A first order feature is a head that has as modifier a training instance. For example in Fig. 2, "island" is in a head relation with "Fiji". Therefore, "island" is a first order feature. A second order feature is a modifier of a first order feature. For example, "an", "is", and "ocean" are modifier of "island". However "an" and "is" are not noun. Therefore, "ocean" is the only one second order feature. Table 1 is a syntactic feature extraction algorithm that will parse a sentence s into a triple form, such as   (island, ocean). † Once the list of all triple forms is obtained, the first order features are extracted by working in a loop to find triples with modifiers as training instance i. Then the head is extracted and identified as a feature. Once the first order features are compiled, we extract the second order features by working in a loop to extract all modifiers that match the first order features. The result is a list of first and second order features from a sentence s in training instance i, which will be further processed in the next stage to create the LSA space.

LSA Processing
The second component of the bootstrapping process is to create the LSA space for populating instances in the knowledge acquisition process. LSA is a procedure based on the vector space model, which manages large sets of documents in information retrieval [15]. LSA creates a term vector representing the terms in a document and a document vector representing the document. Given a query for related documents, a query vector is created, which is represented as a pseudo-document vector formed by a weighted combination of terms and documents, and mapped to the LSA space to search for the nearest document vector; the result represents a related document. LSA can also reduce the dimension of the vector space using singular value decomposition (SVD) [16]. This is a method from linear algebra to reduce the rank of a matrix without losing important content and to eliminate noise. SVD can differentiate noise from words with several meanings (polysemy) or words with similar meanings (synonym) [17]. When the SVD process is finished, the resulting vector space is called the LSA space. From the principle of LSA in information retrieval, we borrow the idea as shown in Fig. 3. The document (such as "d 3 ") is the training instances (such as "Teipei"), and the query is the unknown instance (such as "Phuket"). The system use a training instance representations of the ontology concepts in the LSA space that are compared to unknown instances to find similar instances. If we know that an un-  Taipei is a city of major industrial area. island Fiji Fiji is an island in the pacific ocean. Solomon The Solomon is an archipelago area in the Pacific Ocean. sea Caribbean The Caribbean is a sea of the Atlantic Ocean in the Western hemisphere.

Mediterranean
The Mediterranean is a sea inflow from the Atlantic known instance is near a certain training instance, we can predict the ontology concept for the unknown instance. Using SVD to reduce the dimension of the vector space enables the training instance vectors in the LSA space with similar features to be grouped near each other. It helps in assigning the unknown instances to the ontology concepts at the instance classification stage. LSA processing is divided into three steps: creating, decomposing feature-by-training instance matrix, and truncating the factorized matrix.

Creating the Feature-by-Training Instance Matrix
A small example of a training instance and its features can found in Table 2. The features are the underlined words.
To create a vector space model for the LSA, a feature-bytraining instance matrix A must first be constructed. Figure 4 is an example of the matrix A. The rows of the matrix A are comprised of features, which are the individual components that mark up a training instance. The columns of the matrix A are comprised of training instances, which are a predetermined set of features. An instance collection composed of n training instances and m features can be represented as an m by n feature-by-training instance matrix A. Initially, each column of the matrix A contains zero and nonzero elements a i j . Each nonzero element a i j of the matrix A is the frequency of the ith feature in the jth training instance.

Decomposition of the Feature-by-Training Instance Matrix
The goal of the decomposition matrix A is to represent the features together with the training instances in one space. That makes it possible to calculate similarities between training instances and unknown instances. To calculate the new basis for the space and the vectors, the SVD is needed. SVD factors the m×n matrix A into three matrices in Eq. (1).
U is a rectangular matrix of size m × r whose rows are the feature vectors scaled to the new basis. The other important rectangular matrix is V T , which is of size r × n and contains the new vectors for the training instance. The square matrix Σ is a diagonal matrix. It contains the singular values σ 1 , σ 2 , . . . , σ r where σ 1 ≥ σ 2 ≥ . . . ≥ σ r ≥ 0 [18].

Truncating Factorized Matrix
The dimension of the LSA space has to be reduced by truncating the three matrices, as shown in Fig. 5. They are truncated to a two-dimensional LSA space by reducing the rank to k = 2 (Section 6.6 will show an experiment on reducing each dimension). The system uses only the training instance matrix to create the LSA space as the output of the bootstrapping process. The values in the training instance matrix V T k are used to encode the representations of the training instance in the two-dimensional LSA space. Figure 6 shows a plot of the training instances in the LSA space. The pair (x,y) is defined by x = first row of matrix V T k and y = second row of matrix V T k . Looking at the training instance vectors, the training instances most similar to each other are determined by the angles between vectors. If two vectors are similar, then they will have a small angle between them. In Fig. 6, the training instance "Solomon" is the closest training instance to "Fiji" because they share the "ocean" feature. In contrast, "Taipei" shares the "area" feature with "Solomon" but is not close to "Solomon" because "Taipei" also shares the "city" feature with "London". It is clear that the LSA process clarifies the discrimination among training instances in line with their occurring features, which affects the efficiency of the classification model. This is explained further in the next section.

Instance Detection
The first component of this process is the instance detection. The input of this component is a web document that is required to acquire knowledge. We apply the Stanford NER [19] to detect the possible instances from the web document. The output of this component is the set of unknown instances, which will be further processed in the next stage.

Instance Classification
The unknown instances detected from the web document will be classified in this component. This component employs the LSA space from the bootstrapping process. It comprises two steps: creating the unknown instance vector in the LSA space and assigning unknown instances to ontology concepts.

Creating the Unknown Instance Vector
To represent an unknown instance in the LSA space, we need an external data source that has enough information about the context of the unknown instance. At this stage, data from the search engine web service, such as Yahoo! † or Bing † † , are used to obtain context. The system collects context terms by sending the query as the unknown instance to the search engine. However, searching with the unknown instance results in many irrelevant data, so we append "is" to form a query in the form of "[unknown instance] is". For example, if the unknown instance is "Phuket", the query is "Phuket is". The search results from the search engine consist of a list of records. Each record comprises its title, abstract or snippet, and the document's URL. We only use the snippets for our approach and merge all the snippets as the context of the unknown instance, called the total snippet. The resulting total snippet is used to create a vector in the LSA space, called the unknown instance vector or I. Figure 7 is an example of the construction of I from two snippets. The ith row of I represents the frequency of the ith feature in the total snippets. There are two terms that match the feature in the LSA space: "city" and "island". Therefore, I has values of 1 at the positions of "city" and "island," while at other positions, its value is 0 as there is no word in the total snippets that matches the feature in the LSA space. The resulting I is a 9-dimensional vector, and to project it to the LSA space to find the nearest training vector, its dimension must be reduced to agree with the reduction in the LSA space, which can be done via the following equation [20]: In the above example of constructing an LSA space (see bottom in Fig. 5), we reduce the LSA space to be twodimensional (k = 2). Therefore, we must reduce the dimension of I to two as well. Figure 7 shows how to obtain J from Eq. (2). The resulting J has two dimensions and can be projected onto LSA space. To make the view clearer, we plot the projection of "Phuket" onto LSA space in Fig. 6.

Assigning Unknown Instance to Ontology Concept
We apply the k-nearest neighbor algorithm (k-NN) classification method at this stage to assign the unknown instance to an ontology concept. The k-NN procedure comprises two parts: finding the nearest neighbor and majority voting. Finding the nearest neighbor means to find the training instance vector (V i ) that is nearest (or most similar) to the unknown instance vector (J) at top-K, which is defined in terms of the angle between two vectors from the following equation: The values of cos(α) are in the range from −1, corresponding to 180 • or 0% similarity, to 1, corresponding to 0 • or 100% similarity [21]. Looking back at Fig. 6, it can be seen that "Phuket" and "Taipei" form the least angle. Calculating the value of cos(α) using Eq. (3), we find it to have value 0.9962 or similarity 99.62%. Furthermore, "Phuket" forms a close angle with "Solomon," and computing the value of cos(α) yields 0.8840 or similarity 88.40%. We compute cos(α) values for the angles of "Phuket" with all the training instance vectors in the LSA space and select only the K training instance vectors with the highest similarity. When K = 1, we assign the unknown instance to the single concept with the highest similarity. For example, "Phuket" and "Taipei" have the highest similarity value. We therefore assign "Phuket" to the concept of "Taipei", which is the "city" concept. When K ≥ 2, we will apply majority voting that consists of counting the number of training instances of the concept in the top-K. The assignment can occur in two cases: assigning as a single concept and as multiple concepts. For the single concept assignment, we assign the concept with the highest majority voting value to the unknown instance. We show examples of the training instance and the unknown instance in the LSA space in Fig. 6. In the oval defined at K = 4, the values of the majority vote of the "island" concept and the "city" concept are both two. Therefore, "Phuket" will be assigned to both the "island" concept and the "city" concept.

Semantic Annotation
Semantic annotation formally identifies concepts and relations between concepts in documents, and is intended primarily for use by machines [22]. At this stage, the system links all the instances on web documents with populated ontology. And displaying concept name of each instance that the system has assigned via OntoPop plug-in in the ontology editor. It help ontology engineer to easily create relation between the instances from other function in the ontology editor. The output of this component will create the Semantic Web document in the RDFa [23] format. This is a W3C recommendation that adds a set of attribute level extensions to XHTML for embedding rich metadata within Web documents. An example of RDFa is shown in Table 3. In line 7 specify "Phuket" is an instance of island concept by typeof Table 3 The Semantic Web in RDFa format from our system.
OntoPop is similar to PowerMagpie [24]. PowerMagpie is the existing tool for semantic annotation proposed by d'Aquin et al. This system supporting create only the Semantic Web, while OntoPop can be used to create both the Semantic Web and ontological knowledge base. Besides, PowerMagpie is embedded in web browsers, while OntoPop is embedded in an ontology development application. Therefore, it is convenient for ontology engineers who can use the extracted instances in constructing relations and restrictions after the process completion.

Experiment and Evaluation
To compare the effectiveness of our approach with the techniques of lexico-syntactic patterns [5] and similarity-based classification [7], input ontology and validation set of both were adopted in our experiment. The input ontology is a tourism ontology developed by the GETESS project [25], which contains 682 concepts but no instances. The experiment process is shown in Fig. 8. According to Fig. 8, there are four sections. The first section is a preparation for a training set based on learning methods from external ontology. The second one is a bootstrapping process, which is a preparation for a classification model. The third part is an instance classification. The result from the third part is a result set, which is used to evaluate the effectiveness of the system at the final stage of the experiment. In the experiment process, it can be seen that knowledge acquisition processes of the OntoPop are selected only the instance classification since instance detection and semantic annotation are beyond our work.

Training Set
To prepare a training set for GETESS ontology, information from external ontology which contains instances is used. In this work, YAGO ontology [26] which has the characteristics needed for our work. Similar to GETESS, YAGO covers a large amount of information in which tourism is also included. However, since GETESS contains a lot of concepts, to select training instances manually is difficult; as a result, an automatic learning system is instead developed by  adopting working principles of ontology mapping [27]. Figure 9 shows the results from learning by ontology mapping. As seen in the figure, the system matched concepts of GET-ESS and YAGO, whose names are similar (shown by thick lines), such as "island" with "wordnet island". After that, the learning system collects instances from YAGO's concepts to be training instances in GETESS's concepts. For example, "Fiji" and "Solomon" are set as training instances of island concept in GETESS ontology. The accumulation of the training instances in this experiment is set at a maximum of 20 instances.

Model
When the learning system accumulates all concepts of training instances on the GETESS ontology, the classification model is prepared through feature extraction of each training instance and sent to LSA processing (as previously stated in Sect. 4). Based on this process, LSA space with 4,063 features is obtained. Since in this experiment, the aim is to know the effectiveness of the approach when reducing dimensions of the LSA space. So, the LSA space with 25 to 300 dimensions is prepared and tested on the OntoPop system, one by one.

Validation Set and Test Set
A validation set is a gold standard to performance test of the ontology population. The validation set is created by selecting 30 corpora from the Lonely Planet website (http://www.lonelyplanet.com) and utilizing a human expert to classify the instances manually into GETESS ontology concepts [5]. There are 277 instances in the validation set which are stored in pairs (instance, concept). The examples are listed in Table 4. The validation set contains instances that are not identical to the training set. The validation set is prepared and used as a test set. Only the names of the instances from the validation set are used. The number of the instances in test set is also 277. The examples of test sets are shown in Table 4.

Parameters
The parameters used in the experiment are divided into two parts. The first part of the parameters is based on learning, which refers to the dimensions number of the LSA space. The second part is a parameters set by classification which is comprised of the size of snippets (between 5 and 100), which are used during the construction of unknown vectors, and K values derived from the k-NN technique ranging from 1 to 10.

Evaluation Measures
We follow the evaluation of the ontology population from McDowell et al. [28] The evaluation comprises 2 measures: accuracy and Learning Accuracy (LA). The accuracy measures the correspondence between the exact concept name from the validation set and the system result set. For example, in Table 4, if "Phuket" in the validation set is a "city" and "Phuket" in the system result set is a "city", then our system has the correct result. However, if "Ionion" in the validation set is a "sea" and "Ionion" in the system result is a "beach", then our system has an incorrect result. The accuracy of the system can be computed by Eq. (4). For the example dataset from Table 4, we can compute the accuracy value as 1/3, that is, 0.33 or 33%.

accuracy = Number of correct classifications Total number of unknown instances
Some results of the ontology population are related in the ontology concept [29], e.g., if "Ionion" in the validation set is a "sea" and "Ionion" in the system result set is a "beach". Figure 9 showed the concept level in the GETESS ontology, where "sea" and "beach" have the same parent node, "nature". We can measure this relation using the taxonomic similarity T sim . The computation of T sim is shown in Eq. (5).

Evaluation Results
The experiments were all run on a 2.90 GHZ AMD Athlon II with 4 GB main memory. The first parameter is on reducing the dimension of the LSA space to between 25 and 300 dimensions. The experiment result is shown in Fig. 10. In addition, the contribution of the SVD features are analyzed using accumulative contribution rate (ACR) [30], as listed in Table 5. We find that the LSA space of dimension 75 has the highest LA value, at 76.93% (ACR is 62.86%), and dimension 100 has the highest accuracy values, at 49.64% (ACR is 69.67%). The averages execute time at this point is 5.4572 second/instance. The second parameter tests the use of different sizes of total snippets N, as shown in Fig. 11. We find that N = 45 has the highest LA and accuracy values, at 76.03% and 48.31%, respectively. The averages execute time at this point is 5.5346 second/instance. The last parameter test is shown in Fig. 12. This shows the average LA values and average accuracy values from the experiment with different K values, where the K value denotes the number of the nearest training instances. The experiment finds that K = 7 has the highest LA and accuracy value, at 76.56%, and 49.03%, respectively. The averages execute time at this point is 5.4633 second/instance. Finally, we compare the efficiency of our approach with the lexico-syntactic patterns [5], and similarity-based classification [7]. Table 6 shows the efficiency comparison results.
We find that our approach yields higher accuracy values than the lexico-syntactic patterns (23.79%), and similaritybased classification (20.40%). For the LA value, our method yields higher accuracy values than the lexico-syntactic patterns (5.43%), and similarity-based classification (7.06%). Furthermore, we find that our approach yields lower execute time values than the lexico-syntactic patterns (74.97 second/instance), and similarity-based classification (5.73 second/instance).
The experiment aims to demonstrate the accuracy of our methodology. Looking at the first parameter, the experiment reduces the dimension of the LSA space to different dimensions. Figure 10 shows that at the starting dimension (25 dimensions), it has low accuracy and LA value. These values gradually rise and stabilize at 75 to 125 dimensions. Even though reducing dimension helps to speed up the instance classification, the experiment shows that too small a dimension adversely affects the accuracy. For this reason, we advocate reducing the dimension to the point that yields the highest accuracy and stability, 75 to 125 dimensions for our approach. The second parameter tests different sizes of the total snippets. Figure 11 shows that at the starting point;   it has the lowest accuracy and LA value. Then the graph gradually rises until N = 45 before stabilizing. We conclude that the number of snippets affects the system's efficiency. If the size of total snippets is too small, it is hard for the system to differentiate what training instance has the same meaning and direction to as a given unknown instance.
For the third parameter, the different K values, note that the graph in Fig. 12 does not show much difference in the value of accuracy and LA. However, the real trend of the accuracy and LA values from K = 1 upward is that the accuracy value gradually rises and begins to stabilize when K = 4, and then it begins to decrease.

Implementation
We have implemented the OntoPop system as the plug-in for the Protégé. Protégé is currently the most well-known ontology editor, is freely available, open source, and based on Java [31]. OntoPop plug-in provides easy graphic user interface of ontology populations to end user. On its first tab (Fig. 13), the plug-in displays the configuration form and processing console for create LSA space, and shows the ontology mapping result (right side in Fig. 13.) The second tab (Fig. 14) browses the input web document for acquiring knowledge. When the instance detection starts, the unknown instances are highlighted and showed list of instances that allow user to remove unwanted instance. After starts classification, the unknown instance will be shown the assigning in the ontology concept (right side in Fig. 14) and show concept name when mouse over the instances on the input web document (left side in Fig. 14.) Ontology engineer can save web document in RDFa format, update classified instances into ontology, switch to object properties tab in Protégé for create relation between the instances, and switch to data properties tab in Protégé for adding attribute data after OntoPop system finish processed. Fig. 13 OntoPop plug-in for bootstrapping process.

Conclusion and Future Work
An approach to ontology population for the Semantic Web has been described. This work proposed two main processes. The first process is a syntactic feature extraction to select the features with contexts most related to the instance. The second process is to construct the classification model, or LSA space, which can effectively reduce the noise and the dimension of the classification model. The contribution of this research is a new system to be used to transfer technology from the current web into the Semantic Web. It supports ontology development applications that need to extend knowledge to ontology at the instance level. In our future work, we propose to automatically build relationships between the instances, which is the step after the populating step done.