骆吉洲科研成果

个人简历 科研信息 发表论文 出版物 新建主栏目 教育经历 标题 本科 起讫时间 1995.09-1999.07 所学专业 信息科学与计算数学 学习机构 哈尔滨工业大学 学历 本科 简单介绍 教育经历 标题 硕士 起讫时间 1999.09-2001.07 所学专业 基础数学 学习机构 哈尔滨工业大学 学历 硕士研究生 简单介绍 教育经历 标题 博士 起讫时间 2001.09-2006.05 所学专业 软件与理论 学习机构 哈尔滨工业大学 学历 博士 简单介绍 工作经历 标题 工作经历 起讫时间 2006.07-2008.09 职位/职称 讲师 工作单位 哈尔滨工业大学计算机科学与技术学院 简单介绍 工作经历 标题 工作经历 起讫时间 2008.09-2022.12 职位/职称 副教授 工作单位 哈尔滨工业大学计算学部海量数据计算研究中心 简单介绍 主要从事《算法设计与分析》《高级算法》《程序设计语言》《编译原理》等课程的教学工作，和大数据管理、算法设计与分析、工业软件设计与实现、数据压缩等方面的研究工作。 工作经历 标题 工作经历 工作单位 哈尔滨工业大学计算学部 职位/职称 教授 起讫时间 2022.12-至今 简单介绍 主要从事《高级算法设计与分析》《高级算法》《程序设计语言》等课程的教学工作，和大数据管理、工业软件设计与实现、算法设计与分析方面的研究工作。 研究方向 名称 目前主要从事两方面的工作：(1)海量数据管理技术，大数据高效处理算法的设计与分析；（2）工业软件高效数值计算方法研究； 科研项目 项目名称 XXX项目并行计算与性能优化子课题 项目来源 国家重点项目 开始时间 2020 结束时间 2022 项目经费 150万/6552 担任角色 负责 项目类别 纵向项目 项目状态 完成 简单介绍 通过算法设计、分析和优化、并行计算等技术大幅度提升工业软件运行效率。 项目名称 XXX项目高效数值计算方法研究 项目来源 国家重点项目 开始时间 2020 结束时间 2022 项目经费 150万/1242万 担任角色 负责 项目类别 纵向项目 项目状态 完成 简单介绍 通过算法设计、分析和优化，并行计算等技术大幅度提升工业软件效率，使得问题求解规模提升数百倍。 奖项成果 奖项名称 机群并行数据库系统 获奖时间 2004 完成人 李建中 骆吉洲 所获奖项 国家科学技术进步二等奖(2004) 简单介绍 讲授课程 名称 研究生高级算法设计与分析 本科生高级算法 本科生算法设计与分析 本科生程序设计与数据结构 论文期刊 论文标题 FreshJoin: An Efficient and Adaptive Algorithm for Set Containment Join 作者 Jizhou Luo, Wei Zhang, Shengfei Shi, Hong Gao, Jianzhong Li, Wei Wu, Shouxu Jiang 发表时间 2019 期刊名称 Data Science and Engineering 期卷 4-4 简单介绍 This paper revisits set containment join (SCJ) problem, which uses the subset relationship (i.e., (subseteq) ) as condition to join set-valued attributes of two relations and has many fundamental applications in commercial and scientific fields. Existing in-memory algorithms for SCJ are either signature-based or prefix-tree-based. The former incurs high CPU cost because of the enumeration of signatures, while the latter incurs high space cost because of the storage of prefix trees. This paper proposes a new adaptive parameter-free in-memory algorithm, named as fre quency-ha sh join or ({mathsf {FreshJoin}}) in short, to evaluate SCJ efficiently. ({mathsf {FreshJoin}}) builds a flat index on-the-fly to record three kinds of signatures (i.e., two least frequent elements and a hash signature whose length is determined adaptively by the frequencies of elements in the universe set). The index consists of two sparse inverted indices and two arrays which record hash signatures of all sets in each relation. The index is well organized such that ({mathsf {FreshJoin}}) can avoid enumerating hash signatures. The rationality of this design is explained. And, the time and space cost of the proposed algorithm, which provide a rule to choose ({mathsf {FreshJoin}}) from existing algorithms, are analyzed. Experiments on 16 real-life datasets show that ({mathsf {FreshJoin}}) usually reduces more than 50% of space cost while remains as competitive as the state-of-the-art algorithms in running time. 论文标题 O2iJoin: An Efficient Index-Based Algorithm for Overlap Interval Join 作者 Jizhou Luo, Shengfei Shi, Guang Yang, Hongzhi Wang, Jian-Zhong Li 发表时间 2018 期刊名称 Journal of computer Science and Technology 期卷 33-5 简单介绍 Time intervals are often associated with tuples to represent their valid time in temporal relations, where overlap join is crucial for various kinds of queries. Many existing overlap join algorithms use indices based on tree structures such as quad-tree, B%2B-tree and interval tree. These algorithms usually have high CPU cost since deep path traversals are unavoidable, which makes them not so competitive as data-partition or plane-sweep based algorithms. This paper proposes an efficient overlap join algorithm based on a new two-layer flat index named as Overlap Interval Inverted Index (i.e., O2i Index). It uses an array to record the end points of intervals and approximates the nesting structures of intervals via two functions in the first layer, and the second layer uses inverted lists to trace all intervals satisfying the approximated nesting structures. With the help of the new index, the join algorithm only visits the must-be-scanned lists and skips all others. Analyses and experiments on both real and synthetic datasets show that the proposed algorithm is as competitive as the state-of-the-art algorithms. 论文标题 FrepJoin: an efficient partition-based algorithm for edit similarity join 作者 Jizhou Luo, Shengfei Shi, Hongzhi Wang, Jianzhong Li 发表时间 2017 期刊名称 Frontier of information Technology and Electronic Engineering 期卷 18-10 简单介绍 String similarity join (SSJ) is essential for many applications where near-duplicate objects need to be found. This paper targets SSJ with edit distance constraints. The existing algorithms usually adopt the filter-andrefine framework. They cannot catch the dissimilarity between string subsets, and do not fully exploit the statistics such as the frequencies of characters. We investigate to develop a partition-based algorithm by using such statistics. The frequency vectors are used to partition datasets into data chunks with dissimilarity between them being caught easily. A novel algorithm is designed to accelerate SSJ via the partitioned data. A new filter is proposed to leverage the statistics to avoid computing edit distances for a noticeable proportion of candidate pairs which survive the existing filters. Our algorithm outperforms alternative methods notably on real datasets. 论文标题 On the Complexity of View Update Analysis and Its Application to Annotation Propagation 作者 Gao Cong, Wenfei Fan, Floris Geerts, Jianzhong Li, Jizhou Luo 发表时间 2012 期刊名称 Transaction on Knowledge and Data Engineering 期卷 24-3 简单介绍 This paper investigates three problems identified in [1] for annotation propagation, namely, the view side-effect, source side-effect, and annotation placement problems. Given annotations entered for a tuple or an attribute in a view, these problems ask what tuples or attributes in the source have to be annotated to produce the view annotations. As observed in [1], these problems are fundamental not only for data provenance but also for the management of view updates. For an annotation attached to a single existing tuple in a view, it has been shown that these problems are often intractable even for views defined in terms of simple SPJU queries [1]. We revisit these problems by considering several dichotomies: (1) views defined in various subclasses of SPJU, versus SPJU views under a practical key preserving condition; (2) annotations attached to existing tuples in a view versus annotations on tuples to be inserted into the view; and (3) a single-tuple annotation versus a group of annotations. We provide a complete picture of intractability and tractability for the three problems in all th 论文标题 Incremental graph pattern matching 作者 Wenfei Fan, Jianzhong Li, Jizhou Luo, Zijing Tan, Xin Wang, Yinghui Wu 发表时间 2011 期刊名称 SIGMOD 期卷 简单介绍 Graph pattern matching is commonly used in a variety of emerging applications such as social network analysis. These applications highlight the need for studying the following two issues. First, graph pattern matching is traditionally defined in terms of subgraph isomorphism or graph simulation. These notions, however, often impose too strong a topological constraint on graphs to identify meaningful matches. Second, in practice a graph is typically large, and is frequently updated with small changes. It is often prohibitively expensive to recompute matches starting from scratch via batch algorithms when the graph is updated. This article studies these two issues. (1) We propose to define graph pattern matching based on a notion of bounded simulation, which extends graph simulation by specifying the connectivity of nodes in a graph within a predefined number of hops. We show that bounded simulation is able to find sensible matches that the traditional matching notions fail to catch. We also show that matching via bounded simulation is in cubic time, by giving such an algorithm. (2) We provide an account of results on incremental graph pattern matching, for matching defined with graph simulation, bounded simulation, and subgraph isomorphism. We show that the incremental matching problem is unbounded, that is, its cost is not determined alone by the size of the changes in the input and output, for all these matching notions. Nonetheless, when matching is defined in terms of simulation or bounded simulation, incremental matching is semibounded, that is, its worst-time complexity is bounded by a polynomial in the size of the changes in the input, output, and auxiliary information that is necessarily maintained to reuse previous computation, and the size of graph patterns. We also develop incremental matching algorithms for graph simulation and bounded simulation, by minimizing unnecessary recomputation. In contrast, matching based on subgraph isomorphism is neither bounded nor semibounded. (3) We experimentally verify the effectiveness and efficiency of these algorithms, and show that: (a) the revised notion of graph pattern matching allows us to identify communities commonly found in real-life networks, and (b) the incremental algorithms substantially outperform their batch counterparts in response to small changes. These suggest a promising framework for real-life graph pattern matching. 论文标题 Probing Queries in Wireless Sensor Networks 作者 Liqiang Pan, Jizhou Luo, Jianzhong Li: 发表时间 2008 期刊名称 ICDCS 期卷 简单介绍 For queries in wireless sensor networks, empty sets may be returned as query results which could confuse users a lot and users obtain no useful information about the monitored objects from the empty sets. To solve the problem, this paper proposes methods to provide users with approximate answer sets in the case where no sensing data satisfies the query conditions. The approximate answer sets can be used not only to answer the query approximately but also to guide users to modify their queries for further probing the monitored objects. The distance between sensing data and a query and the dominating relationship between sensing data are first defined. Then, three algorithms for processing probing queries are proposed, which compute the best approximate answer sets that consist of the sensing data with the smallest distance from given queries. All the algorithms utilize the dominating relationship to reduce the amount of data transmitted in sensor networks by filtering out the unnecessary data. Experimental results on real and synthetic data sets show that the proposed algorithms have high performance and energy efficiency. 出版物 出版物名称 编著 作者 骆吉洲 出版时间 2014 出版社 机械工业出版社 简单介绍 算法设计与分析讲义 出版物 出版物名称 出版物 译著 作者 骆吉洲 出版时间 2014-2015 出版社 机械工业出版社 电子工业出版社 简单介绍 1.复杂性理论：现代方法 机械工业出版社2.图论导引 电子工业出版社