We consider the orthogonal range search problem: given a point set P in d-dimensional space and an orthogonal query region Q, return some information on P∩Q. We focus on the counting query to count the number of points of P contained in Q, and the reporting query to enumerate all points of P in Q. For 2-dimensional case, Bose et al. proposed a space-efficient data structure supporting the counting query in O(lgn/lglg_n) time and the reporting query in O(k lg n/ lg lg n) time, where n = |P| and k-|P∩Q|. For high-dimensional cases, the KDW-tree [Okajima, Maruyama, ALENEX 2015] and the data structure of [Ishiyama, Sadakane, DCC 2017] have been proposed. These are however not efficient for very large d. This paper proposes practical space-efficient data structures for the problem. They run fast when the number of dimensions d' used in queries is smaller than the data dimension d. This kind of queries are typical in database queries.
展开▼
机译：我们考虑正交范围搜索问题：给定D维空间中的点设置p和正交查询区域q，返回关于p∩q的一些信息。我们专注于计算Q中包含的P点数的计数查询，以及报告查询，以枚举Q中的所有P点。对于二维案例，Bose等人。提出了一种空节空节空节数据结构，支持O（LGN / LGLG_N）时间中的计数查询以及O（klg n / lg lg n）时间的报告查询，其中n = | p |和k- |p∩q|。对于高维病例，已经提出了KDW树[okajima，Maruyama，Alenex 2015]以及[Ishiyama，Sadakane，DCC 2017]的数据结构。然而，这些对非常大的d不高。本文提出了实用的空间高效数据结构的问题。当查询中使用的维度D'的数量小于数据维度D时，它们快速运行。这种查询在数据库查询中是典型的。
展开▼
