Open Access Open Access  Restricted Access Subscription or Fee Access

Efficient Query Result Navigation Using Top down Navigation Model

R. Saranya, B. Arunkumar


Search queries on databases, and often it return a large number of results, only a small subset of result are relevant to the user. Ranking and categorization, which can also be combined, have been proposed to alleviate this information overload problem. Results categorization for databases is the focus of this work. In this paper, we present the system is a novel search interface that enables the user to navigate large number of query results by organizing them using the concept hierarchy. First, the query results are organized navigation tree. Inside the navigation tree edge cut operation is performed. The query results returns the two set of results that is relevant to the user and ignore results. At each node expansion step, this system of results reveals only a small subset of the concept nodes, selected such that the expected user navigation cost is minimized. In contrast, previous works expand the hierarchy in a predefined static manner, without navigation cost modelling. We show that the problem of selecting the best concepts to reveal at each node expansion and propose an efficient heuristic as well as a feasible optimal algorithm for relatively small trees.


Information Retrieval, Navigation, Search Process.

Full Text:



S. Agrawal, S. Chaudhuri and G. Das. DBXplorer: A System for Keyword Based Search over Relational Databases. ICDE 2002.

J.S. Agrawal, S. Chaudhuri, G. Das, and A. Gionis, ―Automated Ranking of Database Query Results,‖ Proc. First Biennial Conf. Innovative Data Systems Research, 2003.

N. Bruno, S. Chaudhuri and L. Gravano. STHoles: A Multidimensional Workload-Aware Histogram. Proc. Of SIGMOD, 2001.

K. Chakrabarti, S. Chaudhuri, and S.W. Hwang, ―Automatic Categorization of Query Results,‖ Proc. ACM SIGMOD, pp. 755-766, 2004.

Z. Chen and T. Li, ―Addressing Diverse User Preferences in SQLQuery- Result Navigation,‖ Proc. ACM SIGMOD, pp. 641-652,2007.

D. Demner-Fushman and J. Lin, ―Answer Extraction, Semantic Clustering, and Extractive Summarization for Clinical Question Answering,‖ Proc. Int‘l Conf. Computational Linguistics and Ann. Meeting of the Assoc. for Computational Linguistics, pp. 841-848, 2006.

V. Hristidis and Y. Papakonstantinou, ―DISCOVER: Keyword Search in Relational Databases,‖ Proc. Int‘l Conf. Very Large Data Bases (VLDB), 2002.

M. Kaki, ―Findex: Search Results Categories Help When Document Ranking Fails,‖ Proc. ACM SIGCHI Conf. Human Factors in Computing Systems, pp. 131-140, 2005.

W. Lee, L. Raschid, H. Sayyadi, and P. Srinivasan, ―Exploiting Ontology Structure and Patterns of Annotation to Mine Significant Associations between Pairs of Controlled Vocabulary Terms,‖ Proc. Fifth Int‘l Workshop Data Integration in the Life Sciences (DILS), pp. 44-60, 2008.

J. Lin and W.J. Wilbur, ―Pubmed Related Articles: A Probabilistic Topic Based Model for Content Similarity,‖ BMC Bioinformatics, vol. 8, article no. 423, 2007.

H. Shatkay and R. Feldman, ―Mining the Biomedical Literature in the Genomic Era: An Overview,‖ J. Computational Biology, vol. 10, no. 6, pp. 821-855, 2003.

Timos K. Sellis. Multiple-query optimization. TODS, 13(1):23–52, 1988.

E. P. Xing, A. Y. Ng, M. I. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In Advances in Neural Information Processing Systems 15, pages 505–512, 2003.

T. Zhang, R. Ramakrishnan, and M. Livny, ―BIRCH: An Efficient Data Clustering Method for Very Large Databases,‖ Proc. ACM SIGMOD, pp. 103-114, 1996.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.