論文

In this paper, we propose two methods of interactive visualization of the MoSaIC catalogue. We proposed a conceptual modeling for manifold relationships among digital content files as polymorphic catalogues and its visualization system (MoSaIC-II) before. In the modeling, two structures are provided to express the relationships. One is “grouping objects”. The other is “associating between two objects”. The relationship is constructed by using the combination of two structures, and it is described by using directed graph called a MoSaIC catalogue. Multiple catalogues can be connected by shared objects polymorphically. To visualize the catalogue, we propose two methods which are polymorphic topology view and layer view in MoSaIC system using 3D computer graphics. In the previous method, some objects might be overlapped depending on object connections. Then a lot of objects and complex connection of edges can users feel complicated. Using the new methods, object overlap and the complexity of catalogue and object connections can be improved. In the polymorphic topology view, users can see topology of connected objects avoiding object overlaps. Furthermore, we propose the layer view to show objects aligned by a catalogue creator. In the layer view, users can see connected objects which are aligned and exhibited on each catalogue layer. In this method, a complex connection of edges is improved and comparatively a lot of objects can be handled.

This paper argues that a layered approach is more suitable for Information CentricNetworking (ICN) than a narrow-waist approach and proposes an ICN mechanism called ZINK. In ZINK, a location-independent content name is resolved to a list of node IDs of content servers in the application layer and a node ID is mapped to a node locator in the network layer, which results in scalable locator-based routing. An ID/Locator split approach in the network layer can efficiently support client/serever mobility. Efficient content transfer is achieved by using sophisticated functions in the transport layer such as multipath transfer for bandwidth aggregation or fault tolerance. Existing well-tuned congestion control in the transport layer achieves fairness not only among ICN flows but also among ICN flows and other flows. A proof-of concept prototype of ZINK is implemented on an IPv6 stack. Evaluation results show that the time for content finding is practical, efficient content transfer is possible by using multipath transfer, and the mobility support mechanism is scalable as shown in a nationwide experiment environment in Japan.

Limiting data usage is an important issue for data sharing. Big data, in particular, has numerous potential values; thus, an arbitrary value can be extracted as an output by processing data with an arbitrary program. If a data provider simply shares his data with users, the users may get information that the data provider does not want to disclose. However, currently, there is no mechanism to limit the usage of such data. In our approach, a data provider and a program provider specify a combination of data and program files bidirectionally to limit their usages. The Activation Server binds the specified data and program, and then the Activation Server processes the data with the program and sends the output to the user specified by the data provider. We assume that a third-party organization has certified the security for the Activation Server. We implemented and evaluated the Activation Server to demonstrate that it enables data sharing by limiting the usage of digital objects.

Recently, application demands placed on the network have become more multifaceted. Highly functional application-to-application communication services such as bandwidth aggregation, fault tolerant communication, and delay/disruption tolerant networking (DTN) were developed independently in the network layer, the transport layer, and the application layer. As a result, protocol layering has become complicated. This paper proposes to insert Layer-5 (L5) between the application layer and the transport layer to separate communication policies and communication mechanisms to make protocol layering clearer. The transport layer (L4) provides end-to-end communication mechanisms such as reliable byte stream while L5 realizes communication policies such as bandwidth aggregation by combining the communication mechanisms in L4. This paper proposes five types of L5-paths as communication policies: (1) the L5 bundled path for bandwidth aggregation or fault tolerant communication, (2) the L5 spatially-spliced path for communication with middleboxes, (3) the L5 temporally-spliced path for DTN, (4) the L5 spliced-bundled path, and (5) the L5 bundled over spatially-spliced path. An application can select and use an appropriate L5-path depending on the network circumstances through a common API. A prototype of L5 is implemented in the Linux user space as a library to make deployment and maintenance easier. An evaluation shows that establishment time of L5-paths is short enough and performance of L5-paths is comparable or superior to existing technologies.

各ミュージアムが所有するでーたを自律分散的に接続し高い規模拡張性を有するオープンなデジタルミュージアムを提示した。

Personalized PageRank (PPR) measures the importance of vertices with respect to a source vertex. Since real-world graphs are evolving rapidly, PPR computation methods need to be index-free and fast. Unfortunately, existing index-free methods suffer from cache misses. They follow the state-of-the-art algorithm that first performs the Forward Push (FP) phase and subsequently runs the random walk Monte-Carlo simulation (MC) phase. Although existing methods succeed in reducing cache misses in the FP phase, an inefficient data layout limits their performance improvement. Besides, existing methods have overlooked the importance of reducing cache misses in the MC phase. In this paper, we propose a cache-efficient approach that accelerates both FP and MC phases. In the FP phase, we first reorder the data layout with low overheads. Specifically, we utilize the Breadth First Search result so that vertices near the source vertex are co-located on the reordered data layout. We subsequently perform optimized FP, namely Distance-Extension Forward Push (DEFP). By preferentially proceeding FP around the source vertex, DEFP improves memory access locality. In the MC phase, we perform optimized MC, namely Vertex-Centric Random Walk (VCRW). VCRW aggregates random walks at each vertex to eliminate redundant memory access for repeatedly obtaining neighbor vertices. We prove that most of the random walks can be aggregated while maintaining accuracy guarantees. Experimental results show that the proposed method is up to 4.7x faster than existing index-free methods and outperforms the state-of-the-art index-oriented method under rigorous accuracy guarantees.

Personalized PageRank (PPR) is a popular graph computation in various real-world applications. Since massive real-world graphs are evolving rapidly, PPR computation methods require index-free and fast. In general, index-free methods go through Forward Push phase and random walk Monte-Carlo simulation phase respectively. While existing methods have succeeded in accelerating the Forward Push phase, there is a space for running-time improvements in the second phase that performs a large number of sequential random walks. Through this sequential process, each random walk needs to obtain neighbor nodes for every single step, which causes redundant operation at each node as a result. Our proposal is a node-centric random walk that aggregates random walks at each node and minimizes the total number of obtaining neighbor nodes in the second phase. Most of the random walks can be aggregated while maintaining theoretical guarantees because they do not need to memorize the starting node. In addition, we review the expected running time of random walk Monte-Carlo simulation focusing on the total number of obtaining neighbor nodes. We conducted extensive experiments using four real-world graphs. Experimental results showed that our proposed method is up to 3.3x faster than the existing methods.

PPR is an essential computation for customized graph analysis, and its fast computation methods have been proposed. FORA +, one of the fastest methods, introduces an index to speed up PPR computation by referencing the end nodes of pre-generated random walks with a specific termination probability αindex. Although for customized graph analysis, it is essential to query with different termination probabilities α for controlling the analysis range, FORA + does not contribute to the speedup for such different α other than the αindex. This paper proposes a method to quickly determine the end nodes of random walks for arbitrary termination probabilities α(≤ αindex) by focusing on the fact that the random walks become probabilistically longer as the termination probability decreases. In particular, we repeatedly reference the index based on the probability p defined by αindex and α to make the longer random walks. By defining p according to mathematical considerations, the results of our method are guaranteed. In addition, our method can be used in FORA + without modifying its index structure. We incorporate our method into FORA + and evaluate the processing time using six real-world graph datasets. As a result, our method achieves up to 19.8 times speedup over the existing index-free method.

Minimum Steiner tree is frequently used as a means for information retrieval, particularly for search with keyword. While it tends to include high-centrality nodes, the information obtained from such tree may already be accessible to the user, which is not very useful. In this paper, we propose a Steiner tree that avoids high-centrality nodes, in order to increase the likelihood of information being unknown to the user, and thus more useful, while maintaining a high degree of relevance to the keywords. We examine various schemes to select high-centrality nodes to avoid, and compare them in terms of the degree of relevance with the keyword, probability of being unknown to the user, and the pre-computation time. We employ degree centrality and betweenness centrality as our metric for centrality. We find that, our best-performing scheme, despite its simplicity, is able to reduce more than 5% in terms of the number of betweenness centrality nodes compared to the minimum Steiner tree, along with its pre-computation time being about 20% times faster, regardless of our choice of centrality metric.

Top-k Personalized PageRank (PPR) is a graph analysis method used to determine the k most important nodes with respect to a source node. To realize fast Top-k PPR computation, indexing for each node is effective. When we apply the index-based Top-k PPR methods to dynamic graphs, the index becomes stale with edge updates, and index correction is required. Although the existing methods perform index correction for every update to guarantee Top-k PPR accuracy, they involve heavy re-indexing computation or significant memory overhead. This paper proposes a method that achieves comparable accuracy to guaranteed methods while significantly reducing re-indexing by focusing on the fact that index references are concentrated on the nodes whose index is unlikely to change due to edge updates. In particular, our method omits re-indexing as long as we achieve comparable accuracy. Furthermore, our method involves the minimum memory overhead among the existing index-based methods. The space complexity of the index is Θ (n + m), where n and m are the number of nodes and edges of the graph, respectively. The evaluation results using real-world datasets show that our method achieves more than 0.999 Normalized Discounted Cumulative Gain until 20% of edges are updated from index generation.

We propose a framework for converting relational databases (RDB) into hypergraphs to adjust and output various PageRank (PR) correlations by weighting hyperedges and nodes. While analyzing PR of converted graphs can reveal multifaceted information about relationships in the data, conventional methods struggled to balance the correlations between node PR and degree (NPR correlation) and edge PR and shared field records (EPR correlation). Our approach introduces two exponential weighting parameters: α for edge size, influencing EPR correlation, and β for node degree, influencing NPR correlation. By adjusting these parameters, various PR correlations can be obtained. Evaluation using real-world data demonstrate that our model can convert RDBs into hypergraphs with flexibility.

For personalized recommendation in graphs, random walks starting from the user’s interest node are known as a general-purpose and fast analysis method. Specifically, Personalized PageRank (PPR), which quantifies the importance of each node by the distribution of visited nodes in random walks, determines nodes with high global importance and source proximity. However, it is difficult to balance both influences monotonically. This paper clarifies that the random walks length is effective to monotonically control the balance of both influences on PPR vectors. In particular, we exploit the fact that correlation between PPR and PageRank values monotonically changes depending on PPR parameter that controls the average random walk length. Here, PageRank is a metric that quantifies the global importance by the probability of random walks from all nodes visiting each node. A case study using the movie rating dataset showed that nodes that are considered to be directly related to the source node get high PPR value by shortening the average random walk length. Moreover, statistical evaluation on nine real-world datasets revealed that changing the average random walk length from 1.01 to 100 resulted in a monotonic increase of the cosine similarity between PPR and PageRank vectors from 0.002 to 0.76 at the maximum.

モバイルIPv6におけるHAの配置の影響を3万のASレベルトポロジにおいて評価した。