Group-based active query selection for rapid diagnosis in time-critical situations

Gowtham Bellala, Suresh K. Bhavnani, Clayton Scott

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


In applications such as active learning and disease/fault diagnosis, one often encounters the problem of identifying an unknown object through a minimal number of queries. This problem has been referred to as query learning or object/entity identification. We consider three extensions of this fundamental problem that are motivated by practical considerations in real-world,time- critical identification tasks such as emergency response. First, we consider the problem where the objects are partitioned into groups, and the goal is to identify only the group to which the object belongs. Second, we address the situation where the queries are partitioned into groups, and an algorithm may suggest a group of queries to a human user, who then selects the actual query. Third, we consider the problem of object identification in the presence of persistent query noise, and relate it to group identification. To address these problems we show that a standard algorithm for object identification, known as generalized binary search, may be viewed as a generalization of Shannon-Fano coding. We then extend this result to the group-based settings, leading to new algorithms, whose performance is demonstrated through a logarithmic approximation bound, and through experiments on simulated data and a database used for toxic chemical identification.

Original languageEnglish (US)
Article number6121981
Pages (from-to)459-478
Number of pages20
JournalIEEE Transactions on Information Theory
Issue number1
StatePublished - Jan 2012


  • Active learning
  • Shannon-Fano coding
  • decision trees
  • generalized binary search
  • persistent noise
  • submodularity

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Group-based active query selection for rapid diagnosis in time-critical situations'. Together they form a unique fingerprint.

Cite this