research-article

The list Viterbi training algorithm and its application to keyword search over databases

Authors:

Sonia Bergamaschi,

Francesco GuerraAuthors Info & Claims

CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge management

Pages 1601 - 1606

https://doi.org/10.1145/2063576.2063808

Published: 24 October 2011 Publication History

Abstract

Hidden Markov Models (HMMs) are today employed in a variety of applications, ranging from speech recognition to bioinformatics. In this paper, we present the List Viterbi training algorithm, a version of the Expectation-Maximization (EM) algorithm based on the List Viterbi algorithm instead of the commonly used forward-backward algorithm. We developed the batch and online versions of the algorithm, and we also describe an interesting application in the context of keyword search over databases, where we exploit a HMM for matching keywords into database terms. In our experiments we tested the online version of the training algorithm in a semi-supervised setting that allows us to take into account the feedbacks provided by the users.

References

[1]

S. Bergamaschi, P. Bouquet, D. Giacomuzzi, F. Guerra, L. Po, and M. Vincini. An incremental method for the lexical annotation of domain ontologies. Int. J. Semantic Web Inf. Syst., 3(3):57--80, 2007.

[2]

S. Bergamaschi, E. Domnori, F. Guerra, R. T. Lado, and Y. Velegrakis. Keyword search over relational databases: a metadata approach. In Proceedings of the ACM SIGMOD 2011, Athens, Greece, June 12-16, 2011. ACM, 2011.

Digital Library

[3]

S. Bergamaschi, E. Domnori, F. Guerra, M. Orsini, R. T. Lado, and Y. Velegrakis. Keymantic: Semantic keyword-based searching in data integration systems. PVLDB, 3(2):1637--1640, 2010.

Digital Library

[4]

S. Bergamaschi, F. Guerra, S. Rota, and Y. Velegrakis. A hidden markov model approach to keyword-based search over relational databases. In to appear in ER. Springer, 2011.

Digital Library

[5]

S. Chakrabarti, S. Sarawagi, and S. Sudarshan. Enhancing search with structure. IEEE Data Eng. Bull., 33(1):3--24, 2010.

[6]

J. Coffman and A. C. Weaver. A framework for evaluating database keyword search strategies. In CIKM 2010, Toronto, Canada, Oct. 26-30, 2010, pages 729--738. ACM, 2010.

Digital Library

[7]

V. Digalakis. Online adaptation of hidden markov models using incremental estimation algorithms. Speech and Audio Processing, IEEE Transactions on, 7(3):253--261, may 1999.

[8]

R. Neal and G. E. Hinton. A view of the em algorithm that justifies incremental, sparse, and other variants. In Learning in Graphical Models, pages 355--368. Kluwer Pub., 1998.

[9]

J. Pound, S. Paparizos, and P. Tsaparas. Facet discovery for structured web search: a query-log mining approach. In SIGMOD Conference, pages 169--180. ACM, 2011.

Digital Library

[10]

K. Q. Pu. Keyword query cleaning using hidden markov models. In M. T. Özsu, Y. Chen, and L. C. 0002, editors, KEYS, pages 27--32. ACM, 2009.

Digital Library

[11]

L. R. Rabiner. A tutorial on Hidden Markov Models and selected applications in speech recognition. In Proceedings of the IEEE, volume 77, pages 257--286, 1989.

[12]

N. Seshadri and C.-E. Sundberg. List Viterbi decoding algorithms with applications. Communications, IEEE Transactions on, 42(234):313--323, feb/mar/apr 1994.

[13]

N. Seshadri and C.-W. Sundberg. Generalized viterbi algorithms for error detection with convolutional codes. In GLOBECOM '89., IEEE, pages 1534--1538, nov 1989.

[14]

R. Trillo, J. Gracia, M. Espinoza, and E. Mena. Discovering the semantics of user keywords. J. UCS, 13(12), 2007.

[15]

W. Webber. Evaluating the effectiveness of keyword search. IEEE Data Eng. Bull., 33(1):54--59, 2010.

[16]

J. X. Yu, L. Qin, and L. Chang. Keyword Search in Databases. Morgan & Claypool Publishers, 2010.

Digital Library

Cited By

(2018)Combining user and database perspective for solving keyword queries over relational databasesInformation Systems10.1016/j.is.2015.07.00555:C(1-19)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.is.2015.07.005
Beneventano DGuerra FVelegrakis Y(2017)Data Exploration on Large Amount of Relational Data through Keyword Queries2017 International Conference on High Performance Computing & Simulation (HPCS)10.1109/HPCS.2017.21(70-73)Online publication date: Jul-2017
https://doi.org/10.1109/HPCS.2017.21

Index Terms

The list Viterbi training algorithm and its application to keyword search over databases
1. Information systems
  1. Information retrieval
    1. Information retrieval query processing
    2. Retrieval models and ranking

Recommendations

A Hidden Semi-Markov Model-Based Speech Synthesis System

A statistical speech synthesis system based on the hidden Markov model (HMM) was recently proposed. In this system, spectrum, excitation, and duration of speech are modeled simultaneously by context-dependent HMMs, and speech parameter vector sequences ...
Scalable top-k keyword search in relational databases
DASFAA'12: Proceedings of the 17th international conference on Database Systems for Advanced Applications - Volume Part II

Keyword search in relational databases has been widely studied in recent years because it does not require users neither to master a certain structured query language nor to know the complex underlying database schemas. There would be a huge number of ...
Effective Keyword Search over Relational Databases Considering Keywords Proximity and Keywords N-grams
DEXA '11: Proceedings of the 2011 22nd International Workshop on Database and Expert Systems Applications

The current amount of text data in relational databases is massive and is growing fast. This increases the importance and need for non-technical users to be able to search for such information using a simple keyword search. Researchers have studied and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge management

October 2011

2712 pages

ISBN:9781450307178

DOI:10.1145/2063576

Editors:
Bettina Berendt,
Arjen de Vries,
Wenfei Fan,
Craig Macdonald
University of Glasgow, UK
,
Iadh Ounis
University of Glasgow, UK
,
Ian Ruthven
University of Strathclyde, UK

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM '11

Sponsor:

CIKM '11: International Conference on Information and Knowledge Management

October 24 - 28, 2011

Glasgow, Scotland, UK

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
251
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

(2018)Combining user and database perspective for solving keyword queries over relational databasesInformation Systems10.1016/j.is.2015.07.00555:C(1-19)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.is.2015.07.005
Beneventano DGuerra FVelegrakis Y(2017)Data Exploration on Large Amount of Relational Data through Keyword Queries2017 International Conference on High Performance Computing & Simulation (HPCS)10.1109/HPCS.2017.21(70-73)Online publication date: Jul-2017
https://doi.org/10.1109/HPCS.2017.21

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents