检索结果-内蒙古大学图书馆

A General Technique for Top-k geometric Intersection Query Problems

IEEE TRANSACTIONS ON KNOWLEDGE AND data ENGINEERING 2014年第12期26卷 2859-2871页

作者： Rahul, Saladi Janardan, Ravi Univ Minnesota Twin Cities Dept Comp Sci & Engn Minneapolis MN 55455 USA

In a top-k geometric Intersection Query (top-k GIQ) problem, a set of n weighted, geometric objects in R-d is to be preprocessed into a compact data structure so that for any query geometric object, q, and integer k > 0, the k largest-weight objects intersected by q can be reported efficiently. While the top-k problem has been studied extensively for non-geometric problems (e. g., recommender systems), the geometric version has received little attention. This paper gives a general technique to solve any top-k GIQ problem efficiently. The technique relies only on the availability of an efficient solution for the underlying (non-top-k) GIQ problem, which is often the case. Using this, asymptotically efficient solutions are derived for several top-k GIQ problems, including top-k orthogonal and circular range search, point enclosure search, halfspace range search, etc. Implementations of some of these solutions, using practical data structures, show that they are quite efficient in practice. This paper also does a formal investigation of the hardness of the top-k GIQ problem, which reveals interesting connections between the top-k GIQ problem and the underlying (non-top-k) GIQ problem.

关键词： Range search aggregation Top-k query processing and optimization geometric algorithms and data structures

来源：评论

学校读者我要写书评

暂无评论

New Directions in Approximate Nearest-Neighbor Searching 1

引用

5th International Conference on 5th International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Mount, David M. Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA

ISBN: (数字)9783030115098

ISBN: (纸本)9783030115098;9783030115081

Approximate nearest-neighbor searching is an important retrieval problem with numerous applications in science and engineering. This problem has been the subject of many research papers spanning decades of work. Recently, a number of dramatic improvements and extensions have been discovered. In this paper, we will survey some of recent techniques that underlie these developments. In particular, we discuss local convexification, Macbeath regions, Delone sets, and how to apply these concepts to develop new data structures for approximate polytope membership queries and approximate vertical rayshooting queries.

关键词： Approximate nearest-neighbor searching Convexification Macbeath regions geometric algorithms and data structures

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：