s1350 nambiar

33 %
67 %
Information about s1350 nambiar
Education

Published on February 6, 2008

Author: Manlio

Source: authorstream.com

Slide1:  Answering Imprecise Queries over Web Databases Ullas Nambiar and Subbarao Kambhampati Department of CS & Engineering Arizona State University VLDB , Aug 30 – Sep 02, 2005, Trondheim, Norway Why Imprecise Queries ?:  Why Imprecise Queries ? The Imprecise Query Answering Problem:  The Imprecise Query Answering Problem Problem Statement: Given a conjunctive query Q over a relation R, find a ranked set of tuples of R that satisfy Q above a threshold of similarity Tsim. Ans(Q) ={x|x Є R, Similarity(Q,x) >Tsim} Constraints: Autonomous Database Data accessible only by querying Data model, operators etc not modifiable Supports boolean model (relation) Existing Approaches:  Existing Approaches Similarity search over Vector space Data must be stored as vectors of text WHIRL, W. Cohen, 1998 Enhanced database model Add ‘similar-to’ operator to SQL. Distances provided by an expert/system designer VAGUE, A. Motro, 1998 Support similarity search and query refinement over abstract data types Binderberger et al, 2003 User guidance Users provide information about objects required and their possible neighborhood Proximity Search, Goldman et al, 1998 Limitations: User/expert must provide similarity measures New operators to use distance measures Not applicable over autonomous databases Motivation & Challenges what we did !:  Motivation & Challenges what we did ! Objectives Minimal burden on the end user No changes to existing database Domain independent Motivation Mimic relevance based ranked retrieval paradigm of IR systems Can we learn relevance statistics from database ? Use the estimated relevance model to improve the querying experience of users Challenges Estimating Query-Tuple Similarity Weighted summation of attribute similarities Syntactic similarity inadequate Need to estimate semantic similarity Not enough Ontologies Measuring Attribute Importance Not all attributes equally important Users cannot quantify importance The AIMQ approach:  The AIMQ approach Query-Tuple Similarity:  Query-Tuple Similarity Tuples in extended set show different levels of relevance Ranked according to their similarity to the corresponding tuples in base set using n = Count(Attributes(R)) and Wimp is the importance weight of the attribute Euclidean distance as similarity for numerical attributes e.g. Price, Year VSim – semantic value similarity estimated by AIMQ for categorical attributes e.g. Make, Model Deciding Attribute Order:  Deciding Attribute Order Mine AFDs and Approximate Keys Create dependence graph using AFDs Strongly connected hence a topological sort not possible Using Approximate Key with highest support partition attributes into Deciding set Dependent set Sort the subsets using dependence and influence weights Measure attribute importance as Attribute relaxation order is all non-keys first then keys Greedy multi-attribute relaxation Empirical Evaluation:  Empirical Evaluation Goal Test robustness of learned dependencies Evaluate the effectiveness of the query relaxation and similarity estimation Database Used car database CarDB based on Yahoo Autos CarDB( Make, Model, Year, Price, Mileage, Location, Color) Populated using 100k tuples from Yahoo Autos Algorithms AIMQ RandomRelax – randomly picks attribute to relax GuidedRelax – uses relaxation order determined using approximate keys and AFDs ROCK: RObust Clustering using linKs (Guha et al, ICDE 1999) Compute Neighbours and Links between every tuple Neighbour – tuples similar to each other Link – Number of common neighbours between two tuples Cluster tuples having common neighbours Robustness of Dependencies:  Robustness of Dependencies Attribute dependence order & Key quality is unaffected by sampling Robustness of Value Similarities:  Robustness of Value Similarities Efficiency of Relaxation:  Efficiency of Relaxation Random Relaxation Guided Relaxation Accuracy over CarDB:  Accuracy over CarDB 14 queries over 100K tuples Similarity learned using 25k sample Mean Reciprocal Rank (MRR) estimated as Overall high MRR shows high relevance of suggested answers AIMQ - Summary:  AIMQ - Summary An approach for answering imprecise queries over Web database Mine and use AFDs to determine attribute order Domain independent semantic similarity estimation technique Automatically compute attribute importance scores Empirical evaluation shows Efficiency and robustness of algorithms Better performance than current approaches High relevance of suggested answers Domain independence

Add a comment

Related presentations

Related pages

The track detection use in internal contamination ...

DOI:10.1016/S1350-4487(97)00099-1 · 1.21 Impact Factor. ... Martha Buchanan, Anthony Hogan, James Lando, Atmaram Nambiar, Lauren Torso, Joseph M Melnic, ...
Read more

Industrial Inspection with Open Eyes: Advance with Machine ...

Industrial Inspection with Open Eyes: ... Infrared Phys Technol 43(35):187–210. doi: 10. 1016/ S1350-4495(02) ... Nambiar AN (2010) Trends in ...
Read more

Industrial Inspection with Open Eyes: Advance with Machine ...

Rogalski A (2002) Infrared detectors: an overview. Infrared Phys Technol 43(35):187–210. doi: 10. 1016/ S1350-4495(02) ... Mahalik NP, Nambiar AN ...
Read more

Is there any proof of UV-sensitivity and its role in king ...

Eye Res 20:675–703. doi:10.1016/S1350-9462(01)00009-X Håstad O ... · Iswarduth Soojhawon · Bhupendra P Doctor · Madhusoodana P Nambiar
Read more

www.vesasc.org

s1350: snehal narendra: deo: sc: 468: 600: 78.00: 8: s1309: sambhaji: prachi: sc: 460: 600: 76.67: 9: ... nambiar: opn: 443: 600: 73.83: 170: s0665: amita ...
Read more

: The AMEDEO Literature Guide

Med Eng Phys. 2012 Oct 30. pii: S1350-4533(12)00280. Abstract Related articles MONJO M , Petzold C, Ramis JM, Lyngstadaas SP, et al In ...
Read more

www.vesasc.org

s1350: snehal narendra: deo: sc: 468: 600: 78.00: 9: s1309: sambhaji: prachi: sc: 460: 600: 76.67: 10: ... nambiar: opn: 443: 600: 73.83: 200: s0665: amita ...
Read more