Akademska digitalna zbirka SLovenije - logo
E-viri
Celotno besedilo
Recenzirano Odprti dostop
  • Compact and succinct data s...
    Ishiyama, Kazuki; Sadakane, Kunihiko

    Information and computation, August 2020, 2020-08-00, Letnik: 273
    Journal Article

    We introduce compact and succinct representations of a d-dimensional point set for any constant d≥3 supporting orthogonal range searching. Our first data structure uses dnlg⁡n+o(nlg⁡n) bits, where n denotes the number of points in P, and supporting reporting queries in O((n(d−2)/d+occ)lg⁡n/lg⁡lg⁡n) time, and counting queries in O(n(d−2)/dlg⁡n/lg⁡lg⁡n) time, where occ denotes the number of point to report, which is faster than known algorithms. Our second data structure uses dnlg⁡U−nlg⁡n+o(nlg⁡n) bits, where U is the size of the universe, which asymptotically matches the information-theoretic lower bound. The query time complexity is worse than the first one, but the algorithm runs fast in practical database search.