Answering Imprecise Queries over Autonomous Web Databases
Published 1 January 2006
Ullas Nambiar, Subbarao Kambhampati
Citations64
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
AIMQ, a domain and user independent approach for answering imprecise queries over autonomous Web databases is presented, and methods for query relaxation that use approximate functional dependencies and an approach to automatically estimate the similarity between values of categorical attributes are presented.
Abstract
Current approaches for answering queries with imprecise constraints require user-specific distance metrics and importance measures for attributes of interest- metrics that are hard to elicit from lay users. We present AIMQ, a domain and user independent approach for answering imprecise queries over autonomous Web databases. We developed methods for query relaxation that use approximate functional dependencies. We also present an approach to automatically estimate the similarity between values of categorical attributes. Experimental results demonstrating the robustness, efficiency and effectiveness of AIMQ are presented. Results of a preliminary user study demonstrating the high precision of the AIMQ system is also provided. 1
Keywords
Computer Science
Choice Reviews OnlineArtificial intelligence: a modern approach
22,205 Citations1995Stuart Russell, Peter Norvig +2 more
Modern Information Retrieval
11,544 Citations1999Ricardo Baeza‐Yates, Berthier Ribeiro‐Neto
Program electronic library and information systemsAn algorithm for suffix stripping
8,136 Citations1980Martin Porter
An algorithm for suffix stripping is described, which has been implemented as a short, fast program in BCPL, and performs slightly better than a much more elaborate system with which it has been compared.
Machine LearningA Bayesian Method for the Induction of Probabilistic Networks from Data
3,525 Citations1992Gregory F. Cooper, Edward H. Herskovits
This paper presents a Bayesian method for constructing probabilistic networks from databases, focusing on constructing Bayesian belief networks, and extends the basic method to handle missing data and hidden variables.
arXiv (Cornell University)Using Information Content to Evaluate Semantic Similarity in a Taxonomy
2,147 Citations1995Philip Resnik
Language and Cognitive ProcessesContextual correlates of semantic similarity
1,584 Citations1991George A. Miller, Walter G. Charles
Information SystemsRock: A robust clustering algorithm for categorical attributes
1,482 Citations2000Sudipto Guha, Rajeev Rastogi +1 more
Communications of the ACMContextual correlates of synonymy
1,449 Citations1965Herbert Rubenstein, John B. Goodenough
The shapes of the functions indicate that similarity of context is reliable as criterion only for detecting pairs of words that are very similar in meaning.
Querying Heterogeneous Information Sources Using Source Descriptions
1,120 Citations1996Alon Y. Levy, Anand Rajaraman +1 more
The Information Manifold is described, an implemented system that provides uniform access to a heterogeneous collection of more than 100 information sources, many of them on the WWW, and algorithms that use the source descriptions to prune effciently the set of information sources for a given query are described.
Morgan Kaufmann Publishers Inc. eBooksReadings in information retrieval
1,064 Citations1997Karen Spärck Jones, Peter Willett
Journal of Computer and System SciencesOptimal aggregation algorithms for middleware
941 Citations2003Ronald Fagin, Amnon Lotem +1 more
The TSIMMIS project: Integration of heterogeneous information sources
930 Citations1994Sudarshan S. Chawathe, Héctor García-Molina +5 more
The TREC-8 Question Answering Track Report
857 Citations1999Ellen M. Voorhees
Elsevier eBooksDiscover
787 Citations2002Vagelis Hristidis, Yannis Papakonstantinou
It is proved that DISCOVER finds without redundancy all relevant candidate networks, whose size can be data bound, by exploiting the structure of the schema and the selection of the optimal execution plan (way to reuse common subexpressions) is NP-complete.
ePrints Soton (University of Southampton)Ontology Mapping: The State of the Art
659 Citations2005Yannis Kalfoglou, Marco Schorlemmer
Database and Expert Systems ApplicationsThe INQUERY Retrieval System
526 Citations1992James P. Callan, W. Bruce Croft +1 more
A retrieval system (INQUERY) that is based on a probabilistic retrieval model and provides support for sophisticated indexing and complex query formulation is described.
CACTUS—clustering categorical data using summaries
470 Citations1999Venkatesh Ganti, Johannes Gehrke +1 more
This paper introduces a novel formalization of a cluster for categorical attributes by generalizing a definition of a clusters for numerical attributes and describes a very fast summarizationbased algorithm called CACTUS that discovers exactly such clusters in the data.
Optimizing Queries Across Diverse Data Sources
452 Citations1997Laura M. Haas, Donald Kossmann +2 more
This work presents the design of a query optimizer for Garlic, a middleware system designed to integrate data from a broad range of data sources with very different query capabilities, and describes the design and implementation.
The VLDB JournalClustering categorical data: an approach based on dynamical systems
388 Citations2000David Gibson, Jon Kleinberg +1 more
This work describes a novel approach for clustering collections of sets, and its application to the analysis and mining of categorical data, based on an iterative method for assigning and propagating weights on the categorical values in a table.
The VLDB JournalSupporting top-k join queries in relational databases
387 Citations2004Ihab F. Ilyas, WalidG. Aref +1 more
A new rank-join algorithm that makes use of the individual orders of its inputs to produce join results ordered on a user-specified scoring function is introduced and implemented inside a prototype database engine based on PREDATOR.
AI MagazineThe State of the Art in Ontology Design: A Survey and Comparative Review
381 Citations1997Natalya F. Noy, Carole D. Hafner
A framework for comparing ontologies is developed and a number of the more prominent ontologies, including general ontologies, domain-specific ones, and one knowledge representation system are placed into it.
Integration of heterogeneous databases without common domains using queries based on textual similarity
380 Citations1998William W. Cohen
This paper rejects the assumption that global domains can be easily constructed, and assumes instead that the names are given in natural language text, and proposes a logic called WHIRL which reasons explicitly about the similarity of local names, as measured using the vector-space model commonly adopted in statistical information retrieval.
Query caching and optimization in distributed mediator systems
346 Citations1996Sibel Adalı, K. Selçuk Candan +2 more
A cost-based optimization technique that caches statistics of actual calls to the sources and consequently estimates the cost of the possible execution plans based on the statistics cache is proposed.
ACM SIGMOD RecordStructured databases on the web
344 Citations2004Kevin Chen–Chuan Chang, Bin He +3 more
This paper surveys this relatively unexplored frontier of the deep Web, measuring characteristics pertinent to both exploring and integrating structured Web sources, to conclude with several implications which, while necessarily subjective, might help shape research directions and solutions.
CORDS
318 Citations2004Ihab F. Ilyas, Volker Markl +3 more
ACM Transactions on Information SystemsVAGUE: a user interface to relational databases that permits vague queries
296 Citations1988Amihai Motro
VAGUE incorporates several features that enable it to adapt itself to the individual views and priorities of its users, and is its extension to the relational data model with data metrics, which are definitions of distances between values of the same domain.
Evaluating top-k queries over Web-accessible databases
276 Citations2003Nicolas Bruno, Luis Gravano +1 more
This paper studies how to process top-k queries efficiently in this setting, where the attributes for which users specify target values might be handled by external, autonomous sources with a variety of access interfaces.
Theoretical Computer ScienceApproximate inference of functional dependencies from relations
236 Citations1995Jyrki Kivinen, Heikki Mannila
This work considers approximate dependency inference, and shows how a machine learning algorithm due to Angluin et al. can be applied to give in output-polynomial time an approximately correct cover for the set of dependencies holding in r.
Automated Ranking of Database Query Results
236 Citations2003Sanjay Agrawal, Surajit Chaudhuri +2 more
The challenges and several approaches to enable ranking in databases, including adaptations of known techniques from information retrieval, are discussed and results of preliminary experiments are presented.
Data Mining and Knowledge DiscoveryScalable Techniques for Mining Causal Structures
227 Citations2000Craig Silverstein, Sergey Brin +2 more
The results indicate that the approach proposed here is both computationally feasible and successful in identifying interesting causal structures, and an interesting outcome is that it is perhaps easier to infer the lack of causality than to infer causality, information that is useful in preventing erroneous decision making.
IEEE Transactions on Knowledge and Data EngineeringScaling access to heterogeneous data sources with DISCO
208 Citations1998Anthony Tomasic, Louiqa Raschid +1 more
The distributed mediator architecture of Disco is described; the data model and its modeling of data source connections; the interface to underlying data sources and the query rewriting process; and query processing semantics are described.
Proximity Search in Databases
195 Citations1998Roy Goldman, Narayanan Shivakumar +2 more
This paper implements a prototype search engine that uses a model based on textual proximity of keywords within each document to enable keyword searches over databases, and has found it very effective for quickly finding relevant information.
Evaluating strategies for similarity search on the web
190 Citations2002Taher H. Haveliwala, Aristides Gionis +2 more
A technique for automatically evaluating strategies using Web hierarchies, such as Open Directory, in place of user feedback, is presented, applying this evaluation methodology to a mix of document representation strategies, including the use of text, anchor-text, and links.
Lecture notes in computer scienceTree Pattern Relaxation
190 Citations2002Sihem Amer-Yahia, SungRan Cho +1 more
This paper studies the problem of approximate XML query matching, based on tree pattern relaxations, and devise efficient algorithms to evaluate relaxed tree patterns, and designs data pruning algorithms where intermediate query results are filtered dynamically during the evaluation process.
Communications of the ACMThe Lowell database research self-assessment
169 Citations2005Serge Abiteboul, Rakesh Agrawal +27 more
This article proposes research into several important new directions for database management systems, driven by the Internet and increasing amounts of scientific and sensor data.
Data Mining and Knowledge DiscoveryA Simple Constraint-Based Algorithm for Efficiently Mining Observational Databases for Causal Relationships
169 Citations1997Gregory F. Cooper
This paper presents a simple, efficient computer-based method for discovering causal relationships from databases that contain observational data, and allows interested readers to rapidly program and apply the method to their own databases, as a start toward using more elaborate causal discovery algorithms.
Efficient discovery of functional and approximate dependencies using partitions
164 Citations2002Y. Huhtala, Juha Kärkkäinen +2 more
A new approach for finding functional dependencies from large databases, based on partitioning the set of rows with respect to their attribute values is presented, which makes the discovery of approximate functional dependencies easy and efficient, and the erroneous or exceptional rows can be identified easily.
Elsevier eBooksBANKS
161 Citations2002Bayu Rima Aditya, Gaurav Bhalotia +5 more
Browsing ANd Keyword Searching (BANKS) enables almost effortless Web publishing of relational and eXtensible Markup Language (XML) data that would otherwise remain (at least partially) invisible to the Web.
ACM SIGMOD RecordIntegration of biological sources
153 Citations2004Thomas Hernández, Subbarao Kambhampati
The pros and cons of the current approaches and systems are identified and what an integration system for biologists ought to be are discussed.
IEEE Transactions on Knowledge and Data EngineeringFLEX: a tolerant and cooperative user interface to databases
127 Citations1990A. Motro
FLEX is a user interface to relational databases that is tolerant of incorrect input and salvages incorrect queries if they include enough clues on their intended meaning; suggests educated guesees if it recognizes metadata tokens in the input.
Non-classical lexical semantic relations
127 Citations2004Jane Morris, Graeme Hirst
NLP methods and applications need to take account not only of "classical" lexical relations, as found in WordNet, but the less-structural, more context-dependent "non- classical" relations that readers intuit in text.
IEEE Transactions on Software EngineeringAn Information-Theoretic Analysis of Relational Databases—Part I: Data Dependencies and Information Metric
99 Citations1987T.T. Lee
This paper proves that data dependencies can be formulated in terms of entropies, and uses Shannon entropy as an information metric to quantify the information associated with a set of attributes.
Current Directions in Psychological ScienceLearning and Representing Verbal Meaning
93 Citations1998Thomas K. Landauer
After learning from comparable bodies of text, LSA has scored almost as well as humans on vocabulary and subject-matter tests, accurately simulated many aspects of human judgment and behavior based on verbal meaning, and been successfully applied to measure the coherence and conceptual content of text.
IEEE Transactions on Knowledge and Data EngineeringA structured approach for cooperative query answering
89 Citations1994Wesley W. Chu, Qiming Chen
Preliminary experimental results reveal that the proposed type abstraction hierarchy provides an organized structure representing concepts at different knowledge levels in various domains, and provides a systematic and efficient method for cooperative query answering.
Lecture notes in computer scienceApproximate dependency inference from relations
88 Citations1992Jyrki Kivinen, Heikki Mannila
This work considers approximate dependency inference, and shows how a machine learning algorithm due to Angluin, Frazier and Pitt can be applied to give in output-polynomial time an approximately correct cover for the set of dependencies holding in r.
IEEE ExpertCooperative answering through controlled query relaxation
78 Citations1997Terry Gaasterland
ACM Transactions on Information SystemsImprecise information and uncertainty in information systems
76 Citations1990J.M. Morrissey
Two methods of estimating the uncertainty in the set of objects retrieved in response to every query, based on information theory, are proposed: the measure of uncertainty is used to rank objects for presentation to a user.
Of Objects and Databases: A Decade of Turmoil
73 Citations1996Michael J. Carey, David J. DeWitt
This paper takes a look at where the field was a decade ago and where it is now in terms of database support for objects and identifies a number of research challenges that remain to be addressed in order to ultimately achieve the vision.
Answering Imprecise Queries over Autonomous Web Databases
64 Citations2006Ullas Nambiar, Subbarao Kambhampati
AIMQ, a domain and user independent approach for answering imprecise queries over autonomous Web databases is presented, and methods for query relaxation that use approximate functional dependencies and an approach to automatically estimate the similarity between values of categorical attributes are presented.
Similarity of attributes by external probes
63 Citations1998Gautam Das, Heikki Mannila +1 more
It is described how a similarity notion between attributes can be defined by considering the values of other attributes, and it is shown that the framework produces natural notions of similarity.
Machine learning for online query relaxation
60 Citations2004Ion Muslea
A novel algorithm, loqr, is introduced, which is designed to relax queries that are in the disjunctive normal form and contain a mixture of discrete and continuous attributes.
Information dependencies
60 Citations2000Mehmet Dalkılıç, Edward L. Roberston
This paper uses the tools of information theory to examine and reason about the information content of the attributes within a relation instance, and constructs a relation instance that approximates these constraints within any positive &egr;.
Cooperative Query Answering via Type Abstraction Hierarchy
56 Citations1991Wesley W. Chu, Qiming Chen +1 more
The Type Abstraction Hierarchy is proposed which is characterized by dealing with subtyping from subsumption, composition, and also abstraction views based on the type abstraction feature provided by this model, an inference technique for cooperative query answering is developed.
Optimizing Recursive Information-Gathering Plans
53 Citations1999Eric Lambrecht, Subbarao Kambhampati +1 more
A way of representing the access capabilities of sources, and a greedy algorithm for ordering source calls that respects source limitations, and takes both access costs and traffic costs into account, without requring full source statistics are described.
Mining approximate functional dependencies and concept similarities to answer imprecise queries
48 Citations2004Ullas Nambiar, Subbarao Kambhampati
This paper proposes a query processing framework that integrates techniques from IR and database research to efficiently determine answers for imprecise queries and mine and use approximate functional dependencies between attributes to create precise queries having tuples relevant to the given imprecising query.
Elsevier eBooksDistributed Top-N Query Processing with Possibly Uncooperative Local Systems
48 Citations2003Clement Yu, George Philip +1 more
A method for constructing a facility where a user query is accepted at some site, suitable tuples from appropriate sites are retrieved and the results are merged and then presented to the user.
Evaluating strategies for similarity search on the web
40 Citations2002Taher H. Haveliwala, Aristides Gionis +2 more
Knocking the door to the deep Web
25 Citations2004Bin He, Zhen Zhang +1 more
Journal of Intelligent Information SystemsOptimizing Recursive Information Gathering Plans in EMERAC
24 Citations2004Subbarao Kambhampati, Eric Lambrecht +3 more
A heuristic algorithm for ordering source calls that takes both access costs and traffic costs into account, and is able to operate with very coarse statistics about sources (i.e., without depending on full source statistics).
Elsevier eBooksBibFinder/StatMiner
18 Citations2003Zaiqing Nie, Subbarao Kambhampati +1 more
This paper presents StatMiner, a system for estimating the coverage and overlap statistics while keeping the needed statistics tightly under control, and demonstrates the effectiveness of the learned statistics in BibFinder, a publicly available computer science bibliography mediator the authors developed.
Answering imprecise database queries
14 Citations2003Ullas Nambiar, Subbarao Kambhampati
This paper proposes to support imprecise queries over a database by identifying a set of related precise queries that provide answers that are relevant to the user given query by presenting a domain independent approach based on information retrieval techniques to estimate the distance between queries.
Mining coverage statistics for websource selection in a mediator
13 Citations2002Zaiqing Nie, Ullas Nambiar +2 more
A set of connected techniques that estimate the coverage and overlap statistics while keeping the needed statistics tightly under control and the efficiency of the learning algorithms and the effectiveness of the learned statistics are presented.
Extending the Relational Database Model to Support Goal Queries.
13 Citations1986Amihai Motro
The concept of distance between data values that are from the same domain is defined and how to incorporate it into relational systems is shown and three types of goals are defined: neighborhood goals, optimum goals and priority goals.
Very Large Data BasesAnswering imprecise queries over web databases
12 Citations2005Ullas Nambiar, Subbarao Kambhampati
The rapid expansion of the World Wide Web has made a large number of databases like bibliographies, scientific databases etc. to become accessible to lay users demanding "instant gratification".
University of Illinois at Urbana-Champaign eBooksIntegrating similarity based retrieval and query refinement in databases
11 Citations2002Sharad Mehrotra, Michael Ortega‐Binderberger
This work developed several techniques to efficiently process queries that avoid duplicating work done before and perform only the minimum work needed to return the next answer, resulting in up to an order of magnitude performance improvement over a naive re-execution of a refined query.
Providing ranked relevant results for web database queries
10 Citations2004Ullas Nambiar, Subbarao Kambhampati
This work proposes to provide ranked answers to user queries by identifying a set of queries from the query log whose answers are relevant to the given user query.
The Journal of Object TechnologyOn Database Technology for US Homeland Security.
9 Citations2002Won Kim
In the wake of the September 11 terrorist attacks, the US government has initiated a wide array of measures to forestall replay of such attacks by encouraging development and adoption of information technology to detect and apprehend suspects and security risks, and to manage emergencies should such an attack elude prevention.
Mining source coverage statistics for data integration
7 Citations2001Zaiqing Nie, Subbarao Kambhampati +2 more
This paper presents a set of connected techniques that estimate the coverage and overlap statistics while keeping the needed statistics tightly under control, and presents preliminary experimental results showing the feasibility of the approach.