Ke Yi

Ke Yi

Auto-generated profile, based on publicly available information

Ke Yi

Hong Kong University of Science and Technology, Hong Kong, Hong Kong

Research Focus & Metrics

Academic Career Length

20Years (2007-Present)

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

Representative Publications

View All Publications
1 April 2008
Verified
Conference Paper
Closed access
KYKe Yi
Ke Yi
FLFeifei Li
Feifei Li
GKGeorge Kollios
George Kollios
DSDivesh Srivastava
Divesh Srivastava
This work introduces novel polynomial-time algorithms for processing top-k queries in uncertain databases, under the generally adopted model of x-relations. An x-relation consists of a number of x-tuples, and each x-tuple randomly instantiates into one tuple from one or more alternatives. Our results significantly improve the best known algorithms for top-k query processing in uncertain databases, in terms of both running time and memory usage. Focusing on the single-alternative case, the new algorithms are orders of magnitude faster.

9 May 2017
Verified
Conference Paper
Open access
YCYu Chen
Yu Chen
KYKe Yi
Ke Yi
Join size estimation is a critical step in query optimization, and has been extensively studied in the literature. Among the many techniques, sampling based approaches are particularly appealing, due to their ability to handle arbitrary selection predicates. In this paper, we propose a new sampling algorithm for join size estimation, called two-level sampling, which combines the advantages of three previous sampling methods while making further improvements. Both analytical and empirical comparisons show that the new algorithm outperforms all the previous algorithms on a variety of joins, including primary key-foreign key joins, many-to-many joins, and multi-table joins. The new sampling algorithm is also very easy to implement, requiring just one pass over the data. It only relies on some basic statistical information about the data, such as the ℓk-norms and the heavy hitters.

8 February 2016 in The VLDB Journal
Verified
Journal Article
Closed access
PDF file
GLGe Luo
Ge Luo
LWLu Wang
Lu Wang
KYKe Yi
Ke Yi
GCGraham Cormode
Graham Cormode

21 October 2011 in Algorithmica
Verified
Journal Article
Closed access
PDF file
KYKe Yi
Ke Yi
QZQin Zhang
Qin Zhang

20 April 2016 in IEEE Transactions on Knowledge and Data Engineering
Verified
Journal Article
Closed access
BWBin Wu
Bin Wu
KYKe Yi
Ke Yi
ZLZhenguo Li
Zhenguo Li
The problem of counting triangles in graphs has been well studied in the literature. However, all existing algorithms, exact or approximate, spend at least linear time in the size of the graph (except a recent theoretical result), which can be prohibitive on today's large graphs. Nevertheless, we observe that the ideas in many existing triangle counting algorithms can be coupled with random sampling to yield potentially sublinear-time algorithms that return an approximation of the triangle count without looking at the whole graph. This paper makes these random sampling algorithms more explicit, and presents an experimental and analytical comparison of different approaches, identifying the best performers among a number of candidates.

11 November 2009 in The VLDB Journal
Verified
Journal Article
Closed access
PDF file
CJCheqing Jin
Cheqing Jin
KYKe Yi
Ke Yi
LCLei Chen
Lei Chen
JYJeffrey Xu Yu
Jeffrey Xu Yu
XLXuemin Lin
Xuemin Lin