Yiping Ke

Yiping Ke

Auto-generated profile, based on publicly available information

Yiping Ke

College of Computing and Data Science, Nanyang Technological University, Singapore

Research Focus & Metrics

Academic Career Length

23Years (2004-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
20 May 2012
Verified
Conference Paper
Open access
ZXZhiqiang Xu
Zhiqiang Xu
YKYiping Ke
Yiping Ke
YWYi Wang
Yi Wang
HCHong Cheng
Hong Cheng
JCJames Cheng
James Cheng

1 May 2014 in Proceedings of the VLDB Endowment
Verified
Journal Article
Open access
HWHuanhuan Wu
Huanhuan Wu
JCJames Cheng
James Cheng
SHSilu Huang
Silu Huang
YKYiping Ke
Yiping Ke
YLYi Lu
Yi Lu
YXYanyan Xu
Yanyan Xu
Shortest path is a fundamental graph problem with numerous applications. However, the concept of classic shortest path is insufficient or even flawed in a temporal graph, as the temporal information determines the order of activities along any path. In this paper, we show the shortcomings of classic shortest path in a temporal graph, and study various concepts of "shortest" path for temporal graphs. Computing these temporal paths is challenging as subpaths of a "shortest" path may not be "shortest" in a temporal graph. We investigate properties of the temporal paths and propose efficient algorithms to compute them. We tested our algorithms on real world temporal graphs to verify their efficiency, and also show that temporal paths are essential for studying temporal graphs by comparing shortest paths in normal static graphs.

1 April 2011
Verified
Conference Paper
Closed access
JCJames Cheng
James Cheng
YKYiping Ke
Yiping Ke
SCShumo Chu
Shumo Chu
MOM. Tamer Ozsu
M. Tamer Ozsu
The k-core of a graph is the largest subgraph in which every vertex is connected to at least k other vertices within the subgraph. Core decomposition finds the k-core of the graph for every possible k. Past studies have shown important applications of core decomposition such as in the study of the properties of large networks (e.g., sustainability, connectivity, centrality, etc.), for solving NP-hard problems efficiently in real networks (e.g., maximum clique finding, densest subgraph approximation, etc.), and for large-scale network fingerprinting and visualization. The k-core is a well accepted concept partly because there exists a simple and efficient algorithm for core decomposition, by recursively removing the lowest degree vertices and their incident edges. However, this algorithm requires random access to the graph and hence assumes the entire graph can be kept in main memory. Nevertheless, real-world networks such as online social networks have become exceedingly large in recent years and still keep growing at a steady rate. In this paper, we propose the first external-memory algorithm for core decomposition in massive graphs. When the memory is large enough to hold the graph, our algorithm achieves comparable performance as the in-memory algorithm. When the graph is too large to be kept in the memory, our algorithm requires only O(k max ) scans of the graph, where k max is the largest core number of the graph. We demonstrate the efficiency of our algorithm on real networks with up to 52.9 million vertices and 1.65 billion edges.

11 June 2007
Verified
Conference Paper
Open access
PDF file
JCJames Cheng
James Cheng
YKYiping Ke
Yiping Ke
WNWilfred Ng
Wilfred Ng
ALAn Lu
An Lu
Graphs are prevalently used to model the relationships between objects in various domains. With the increasing usage of graph databases, it has become more and more demanding to efficiently process graph queries. Querying graph databases is costly since it involves subgraph isomorphism testing, which is an NP-complete problem. In recent years, some effective graph indexes have been proposed to first obtain a candidate answer set by filtering part of the false results and then perform verification on each candidate by checking subgraph isomorphism. Query performance is improved since the number of subgraph isomorphism tests is reduced. However, candidate verification is still inevitable, which can be expensive when the size of the candidate answer set is large. In this paper, we propose a novel indexing technique that constructs a nested inverted-index, called FG-index, based on the set of Frequent subGraphs (FGs). Given a graph query that is an FG in the database, FG-index returns the exact set of query answers without performing candidate verification. When the query is an infrequent graph, FG-index produces a candidate answer set which is close to the exact answer set. Since an infrequent graph means the graph occurs in only a small number of graphs in the database, the number of subgraph isomorphism tests is small. To ensure that the index fits into the main memory, we propose a new notion of -Tolerance Closed Frequent Graphs (-TCFGs), which allows us to flexibly tune the size of the index in a parameterized way. Our extensive experiments verify that query processing using FG-index is orders of magnitude more efficient than using the state-of-the-art graph index. Copyright 2007 ACM

26 July 2016 in IEEE Transactions on Knowledge and Data Engineering
Verified
Journal Article
Closed access
HWHuanhuan Wu
Huanhuan Wu
JCJames Cheng
James Cheng
YKYiping Ke
Yiping Ke
SHSilu Huang
Silu Huang
YHYuzhen Huang
Yuzhen Huang
HWHejun Wu
Hejun Wu
Shortest path is a fundamental graph problem with numerous applications. However, the concept of classic shortest path is insufficient. In this paper, we study various concepts of “shortest” path in temporal graphs, called minimum temporal paths. Computing these minimum temporal paths is challenging as subpaths of a “shortest” path may not be “shortest” in a temporal graph. We propose efficient algorithms to compute minimum temporal paths and verified their efficiency using large real-world temporal graphs.

19 December 2011 in ACM Transactions on Database Systems
Verified
Journal Article
Open access
JCJames Cheng
James Cheng
YKYiping Ke
Yiping Ke
AFAda Wai-Chee Fu
Ada Wai-Chee Fu
JYJeffrey Xu Yu
Jeffrey Xu Yu
LZLinhong Zhu
Linhong Zhu
Maximal clique enumeration is a fundamental problem in graph theory and has important applications in many areas such as social network analysis and bioinformatics. The problem is extensively studied; however, the best existing algorithms require memory space linear in the size of the input graph. This has become a serious concern in view of the massive volume of today's fast-growing networks. We propose a general framework for designing external-memory algorithms for maximal clique enumeration in large graphs. The general framework enables maximal clique enumeration to be processed recursively in small subgraphs of the input graph, thus allowing in-memory computation of maximal cliques without the costly random disk access. We prove that the set of cliques obtained by the recursive local computation is both correct (i.e., globally maximal) and complete. The subgraph to be processed each time is defined based on a set of base vertices that can be flexibly chosen to achieve different purposes. We discuss the selection of the base vertices to fully utilize the available memory in order to minimize I/O cost in static graphs, and for update maintenance in dynamic graphs. We also apply our framework to design an external-memory algorithm for maximum clique computation in a large graph.