资源描述：
《Cost-Effective Conceptual Design》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Cost-EffectiveConceptualDesignUsingTaxonomiesAliVakilianvakilian@mit.edu1,YodsawalaiChodpathumwanychodpa@illinois.edu2,ArashTermehchytermehca@oregonstate.edu3andAmirNayyerinayyeria@oregonstate.edu31CSAIL,DepartmentofEECS,MIT,Cambridge,MA,USA2DepartmentofComputerScience,UniversityofIllinois,Urb
2、ana,IL,USA3SchoolofEECS,OregonStateUniversity,Corvallis,OR,USAAbstractItisknownthatannotatingnamedentitiesinunstructuredandsemi-structureddatasetsbytheirconceptsimprovestheeffectivenessofansweringqueriesoverthesedatasets.Ideally,onewouldliketoannotateentitiesofallconceptsinagivendomaininadatas
3、et,however,ittakessubstantialtimeandcomputationalresourcestodosooveralargedataset.Aseveryenterprisehasalimitedbudgetoftimeorcomputationalresources,ithastoannotateasubsetofconceptsinagivendomainwhosecostsofannotationdonotexceedthebudget.Wecallsuchasubsetofconceptsaconceptualdesignfortheannotate
4、ddataset.Wefocusonfindingaconceptualdesignthatprovidesthemosteffectiveanswerstoqueriesovertheannotateddataset,i.e.,acost-effectiveconceptualdesign.Since,itisoftenlesstime-consumingandcostlytoannotatesmallnumberofgeneralconcepts,suchasperson,thanalargenumberofspecificconcepts,suchaspoliticiananda
5、rtist,weuseinformationonsuperclass/subclassrelationshipsbetweenconceptsintaxonomiestofindacost-effectiveconceptualdesign.Wequantifytheamountbywhichaconceptualdesignwithconceptsfromataxonomyimprovestheeffectivenessofansweringqueriesoveranannotateddataset.Ifthetaxonomyisatree,weprovethattheproble
6、misNP-hardandproposeanefficientapproximationalgorithmandanexactpseudo-polynomialtimealgorithmfortheproblem.Wefurtherprovethatifthetaxonomyisadirectedacyclicgraph,givensomegenerallyacceptedhypothesis,itisnotpossibletofindanyapproximationalgorithmwithreasonablysmallapproximationratioorapseudo-poly
7、nomialalgorithmfortheproblem.Ourempiricalstudyusingreal-worlddatasets,taxonomies,andqueryworkloadsshowsthatourframeworkeffectivelyquantifiestheamountbywhichaconceptualdesignimprovestheeffectivenessofansweringqueries.Italsoindicatesthatou
