Betty Salzberg, Linan Jiang, David Lomet, Manuel Barrena, Jing Shan, Evangelos Kanoulas, "A Framework for Access Methods for Versioned Data". Appeared in EDBT '03. Acceptance rate about 14%.
Evangelos Kanoulas, Yang Du, Tian Xia, Donghui Zhang, "Finding Fastest Paths on A Road Network with Speed Patterns". Submitted to SSTD '05. Acceptance rate about 31%.
Tian Xia, Donghui Zhang, Evangelos Kanoulas, Yang Du, "On Computing Top-t Most Influential Spatial Sites". To appear in VLDB '05. Acceptance rate about 16.5%.
o A Framework for Access Methods for Versioned Data
This paper presents a framework for understanding and constructing access methods for versioned data. Records are associated with version ranges in a version tree. A minimal representation for the end set of a version range is given.We show how, within a page, a compact representation of a record can be made using start version of the version range only. Current-version splits, version-and-key splits and consolidations are explained. These operations preserve an invariant which allows visiting only one page at each level of the access method when doing exact-match search (no backtracking). Splits and consolidations also enable efficient stabbing queries by clustering data alive at a given version into a small number of data pages. Last, we survey the methods in the literature to show in what ways they conform or do not conform to our framework. These methods include temporal access methods, branched versioning access methods and spatio-temporal access methods. Our contribution is not to create a new access method but to bring to light fundamental properties of version-splitting access methods and to provide a blueprint for future versioned access methods. In addition, we have not made the unrealistic assumption that transactions creating a new version make only one update, and have shown how to treat multiple updates.
o Finding Fastest Paths on A Road Network with Speed Patterns
Existing path computation systems, like MapPoint, produce driving directions ignoring the speed changes on the road network and the user preferred leaving (or arrival) time. In this paper we propose the CapeCod speed patterns to capture the speed changes and based on it we define a generalized fastest path query, named time interval all fastest paths query, to produce all fastest paths for a user-defined leaving (or arrival) time interval. A system that supports this query is of great practical value and an efficient solution to this query may bring huge savings to the society. For instance, during rush hour in the morning, the system may avoid using in-bound highways to a big city. To answer this query, we propose novel extensions to the A* algorithm. A new path expansion algorithm is discussed. Novel lower-bound estimators are proposed. We also propose to use upper-bound estimators to shrink the size of the processing queue. Several practical extensions and concerns are discussed. The algorithm is experimentally evaluated on real road network data.>
o On Computing Top-t Most Influential Spatial Sites
Given a set O of weighted objects, a set S of sites, and a query site s, the influence set of s is the set of objects in O that consider s as the nearest site among all sites in S. The influence of a site s can be defined as the total weight of its influence set. This paper addresses the new and interesting problem of finding the top-t most influential sites from S, inside a given spatial region Q. This paper proposes an algorithm called TopInfluentialSites, which finds the answer by browsing R*-trees of objects and sites once systematically. Novel pruning techniques are provided, based on a new metric called minExistDNN. There is no need to compute the influence for all sites in Q, or even to visit all sites in Q. Experimental results verify that our proposed method outperforms the straightforward approach.
o A Framework for Access Methods for Versioned Data
- Evangelos helped in re-writting the paper by doing some critical reading and giving comments regarding
both the written style and the actual content of the paper.
- Research papers on versioned data do not consider the case of massive updates within a single transaction.
Evangelos considered this fact and defined the problem of ghost pages.
o Finding Fastest Paths on A Road Network with Speed Patterns (to be considered for fulfilling the paper requirement)
- Evangelos is the one that mostly contributed in this paper. He worked on the related work,
and came up with the algorithm to solve the proposed problem. He did most of the writting
(except the introduction and section 6). He helped in re-writting these two sections.
- He did most of the coding (the underline storage model coding was done by Tian Xia while the coding
related to section 6 was done by Yang Du) and worked on the experiments.
- After the paper being rejected by SIGMOD he got fully in charge with re-writting the paper and running
more experiments and resubmitting it to SSTD.
o On Computing Top-t Most Influential Spatial Sites
- Evangelos helped in writting and re-writting the paper and participated in figuring out the algorithm
for solving the proposed problem.
- He came up with the computation of the new proposed metric in cooperation with Yang Du (the metric
itself was proposed by Donghui Zhang)