Encoding Two-Dimensional Range Top-k Queries
dc.contributor.author | Jo, Seungbum | |
dc.contributor.author | Lingala, Rahul | |
dc.contributor.author | Satti, Srinivasa Rao | |
dc.date.accessioned | 2022-09-27T12:06:16Z | |
dc.date.available | 2022-09-27T12:06:16Z | |
dc.date.created | 2021-10-28T14:44:32Z | |
dc.date.issued | 2021 | |
dc.identifier.citation | Algorithmica. 2021, 83 3379-3402. | en_US |
dc.identifier.issn | 0178-4617 | |
dc.identifier.uri | https://hdl.handle.net/11250/3021787 | |
dc.description.abstract | We consider the problem of encoding two-dimensional arrays, whose elements come from a total order, for answering Top-k queries. The aim is to obtain encodings that use space close to the information-theoretic lower bound, which can be constructed efficiently. For an m×n array, with m≤n, we first propose an encoding for answering 1-sided Top-k queries, whose query range is restricted to [1…m][1…a], for 1≤a≤n. Next, we propose an encoding for answering for the general (4-sided) Top-k queries that takes (mlg((k+1)nn)+2nm(m−1)+o(n)) bits, which generalizes the joint Cartesian tree of Golin et al. [TCS 2016]. Compared with trivial O(nmlgn)-bit encoding, our encoding takes less space when m=o(lgn). In addition to the upper bound results for the encodings, we also give lower bounds on encodings for answering 1 and 4-sided Top-k queries, which show that our upper bound results are almost optimal. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Springer | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Encoding Two-Dimensional Range Top-k Queries | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.source.pagenumber | 3379-3402 | en_US |
dc.source.volume | 83 | en_US |
dc.source.journal | Algorithmica | en_US |
dc.identifier.doi | 10.1007/s00453-021-00856-1 | |
dc.identifier.cristin | 1949333 | |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 2 |