The common prefix problem on trees

DOI10.1016/J.IPL.2007.08.032MaRDI QIDQ2380083zbMATH OpenOpenAlexFDO

Authors Sreyash Kenkre, Sundar Vishwanathan

Publication date 24 March 2010

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

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

zbMATH Keywords

approximation algorithmscommon prefixdatabase query optimizationmaximum edge biclique

Mathematics Subject Classification ID

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

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.

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

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)