License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.59
URN: urn:nbn:de:0030-drops-169971
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16997/
Go to the corresponding LIPIcs Volume Portal

Gao, Younan ; He, Meng

Faster Path Queries in Colored Trees via Sparse Matrix Multiplication and Min-Plus Product

pdf-format:
LIPIcs-ESA-2022-59.pdf (0.7 MB)

Abstract

Let T be an ordinal tree on n nodes in which each node is assigned a color. We consider the batched colored path counting problem and the batched path mode/least frequent element query problem, in which given n query paths, each identified by a pair of nodes in T, one is asked to answer queries of the following forms: How many distinct colors are there on each query path (i.e. the colored path counting problem); what is the color on each query path that occurs at least/most as frequently as any other colors (i.e. the path mode/least frequent element query problem). By reducing the batched colored path counting problem to sparse matrix multiplication, we design a solution that answers n colored path counting queries in Õ(n^{2ω/(ω+1)}) = O(n^1.40704) time in total, while we reduce batched path mode/least frequent element query to the min-plus-query-witness problem so that we can answer a batch of n queries in Õ(n^{{24+2ω}/{17+ω}}) = O(n^1.483814) time. Previously, both problems could only be solved in Õ(n^1.5) time.
Based on similar techniques, we design a dynamic colored path counting structure supporting both queries and updates in Õ(n^{{ω+1}/{ω+3}}) = O(n^0.627759) time, while our dynamic path mode/least frequent element query structures support each operation in Õ(n^{{16+ω(1,2,1)}/{26+ω(1,2,1)}}) = O(n^0.658139) time, where ω(1, 2, 1) denotes the minimum value such that the product of an n × n² matrix and an n² × n matrix can be computed in O(n^{ω(1, 2, 1)+ε}) time for any constant ε > 0. We also solve batched range mode/least frequent element query problems over arrays in Õ(n^{{18+2ω}/{13+ω}}) = O(n^1.479603) time. Both problems can be viewed as special cases of these batched path queries, and previously, the fastest algorithm for batched range mode queries and batched range least frequent element queries use O(n^1.4805) and Õ(n^1.5) time, respectively.

BibTeX - Entry

@InProceedings{gao_et_al:LIPIcs.ESA.2022.59,
  author =	{Gao, Younan and He, Meng},
  title =	{{Faster Path Queries in Colored Trees via Sparse Matrix Multiplication and Min-Plus Product}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16997},
  URN =		{urn:nbn:de:0030-drops-169971},
  doi =		{10.4230/LIPIcs.ESA.2022.59},
  annote =	{Keywords: min-plus product, range mode queries, range least frequent queries, path queries, colored path counting, path mode queries, path least frequent queries}
}

Keywords: min-plus product, range mode queries, range least frequent queries, path queries, colored path counting, path mode queries, path least frequent queries
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI