The common prefix problem on trees

DOI10.1016/J.IPL.2007.08.032zbMATH Open1184.68216arXivcs/0612060OpenAlexW1965347398MaRDI QIDQ2380083FDOQ2380083

Authors: Sreyash Kenkre, Sundar Vishwanathan 

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: We present a theoretical study of a problem arising in database query optimization, which we call as The Common Prefix Problem. We present a $(1-o(1))$ factor approximation algorithm for this problem, when the underlying graph is a binary tree. We then use a result of Feige and Kogan to show that even on stars, the problem is hard to approximate.

Full work available at URL: https://arxiv.org/abs/cs/0612060

Recommendations

• Longest common extensions in trees
• Automata, Languages and Programming
• Longest common extensions in trees
• Top Tree Compression of Tries.
• On the weak prefix-search problem

zbMATH Keywords

approximation algorithmscommon prefixdatabase query optimizationmaximum edge biclique

Mathematics Subject Classification ID

Approximation algorithms (68W25) Database theory (68P15)

This page was built for publication: The common prefix problem on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380083)